آمار
| تعداد نشریات | 39 |
| تعداد شماره‌ها | 1,169 |
| تعداد مقالات | 8,429 |
| تعداد مشاهده مقاله | 6,294,608 |
| تعداد دریافت فایل اصل مقاله | 3,541,665 |
احاطه گر k-مجاورت در گراف‌ها | ||
| پدافند الکترونیکی و سایبری | ||
| دوره 9، شماره 3 - شماره پیاپی 35، آذر 1400، صفحه 125-131 اصل مقاله (610.79 K) | ||
| نوع مقاله: مقاله پژوهشی | ||
| نویسنده | ||
| داود بخشش* | ||
| استدیار، گروه علوم کامپیوتر، دانشگاه بجنورد، بجنورد، ایران | ||
| تاریخ دریافت: 26 آذر 1399، تاریخ بازنگری: 13 بهمن 1399، تاریخ پذیرش: 07 اسفند 1399 | ||
| چکیده | ||
| فرض کنید G یک گراف ساده و بدون دور با مجموعه رئوس V باشد. یک مجموعه S که زیرمجموعه V است را احاطه‌گر گویند هرگاه هر رأسی که خارج از S است با حداقل یک رأس در S همجوار باشد. فرض کنید k≥1 عددی صحیح باشد. مجموعه احاطه‌گر S را یک مجموعه احاطه‌گر k-مجاورت می‌نامیم هرگاه زیرگراف القائی G[S] شامل رأسی از درجه حداکثر k-1 باشد. کمترین تعداد عناصر یک مجموعه احاطه‌گر k-مجاورت برای گراف G عدد احاطه k-مجاورت آن گراف نامیده می‌شود و با نماد γ_k^a (G) نمایش داده می‌شود. در این مقاله، مطالعه احاطه‌گر k-مجاورت آغاز می‌شود. سپس مقادیر دقیق و کران‌هایی برای عدد احاطه k-مجاورت یک گراف داده شده ارائه می‌شود. همچنین، نشان داده می‌شود که یک الگوریتم با زمان چندجمله‌ای برای محاسبه عدد احاطه k-مجاورت یک درخت داده شده وجود دارد. علاوه بر این، ثابت می‌شود که مسئله تصمیم‌گیری مرتبط با احاطه‌گر k-مجاورت برای گراف‌های دوبخشی NP-کامل است. | ||
| کلیدواژه‌ها | ||
| مجموعه احاطه‌گر؛ گراف؛ عدد احاطه | ||
| مراجع | ||
|
[1]. T. W. Haynes, S. Hedetniemi, and P. Slater, “Fundamentals of dominationin graphs,” CRC Press, 1998.## [2]. M. Rajaati Bavil Olyaei and M. R. Hooshmandasl, “Generating Tree Decomposition of Graphs with Imperialist Competitive Algorithm for Use in Secret Sharing Scheme,” Jourrnal of Electronical & Cyber Defence, vol. 7, no. 3, pp. 105-111, 2019. (In Persian).## [3]. N. Biggs, “Perfect codes in graphs,” J. Comb. Theory. B., vol. 15, no. 3, pp. 289-296, 1973.## [4]. S. Hamid and S. Balamurugan, “Isolate domination in graphs,” Arab Journal of Mathematical Sciences, vol. 22, no. 2, pp. 232- 241, 2016.## [5]. N. J. Rad, “Some notes on the isolate domination in graphs,” AKCE International Journal of Graphs and Combinatorics, vol. 14, no. 2, pp. 112-117, 2017.## [6]. G. Rajasekar and A. Jeslet Kani Bala, “𝑘-Isolate domination number of simple graphs,” Malaya Journal of Matematik, vol. S, no. 1, pp. 113-115, 2019.## [7]. E. Cockayne, S. Goodman, S. Hedetniemi, “A linear algorithm for the domination number of a tree,” Inform. Process. Lett., vol. 4, no. 2, pp. 41-44, 1975.## [8]. M. R. Garey and D. S. Johnson, “Computers and Intractability: A Guide to the Theory of NP-## | ||
|
آمار تعداد مشاهده مقاله: 251 تعداد دریافت فایل اصل مقاله: 178 |
||