مجموعه‌های تفکیک‌کننده رأس‌ها در گراف‌ها با کوچکترین اندازه

ظفری, علی; حبیبی, نادر; علیخانی, سعید

doi:10.22108/msci.2023.138631.1599

تعداد نشریات	43
تعداد شماره‌ها	1,706
تعداد مقالات	13,973
تعداد مشاهده مقاله	33,630,452
تعداد دریافت فایل اصل مقاله	13,340,554

	مجموعه‌های تفکیک‌کننده رأس‌ها در گراف‌ها با کوچکترین اندازه
نشریه ریاضی و جامعه
مقاله 4، دوره 8، شماره 3، آذر 1402، صفحه 41-54 اصل مقاله (1.85 M)
نوع مقاله: مقاله پژوهشی
شناسه دیجیتال (DOI): 10.22108/msci.2023.138631.1599
نویسندگان
علی ظفری^* ¹؛ نادر حبیبی²؛ سعید علیخانی³
¹گروه ریاضی، دانشکده علوم‌پایه، دانشگاه پیام‌نور، تهران، ایران
²گروه ریاضی، دانشکده علوم‌پایه، دانشگاه آیت الله العظمی بروجردی (ره)، بروجرد، ایران
³دانشکده علوم ریاضی، دانشگاه یزد، یزد، ایران
چکیده
فرض کنیم $G$ یک گراف ساده همبند با مجموعه رأس‌های $V(G)$ و مجموعه یال‌های $E(G)\ $ باشد. زیرمجموعه $ S=\{s_1, s_2,\ldots,s_l \}$ از رأس‌های گراف $G$ یک مجموعه تفکیک‌کننده دوگانه برای گراف $G$ نامیده می‌شود، هرگاه برای هر دو رأس متمایز $u$ و $v$ از گراف $G$، عضوهای $x$ و $y$ از $S$ موجود باشند که $.d\left(u,\ x\right)-d\left(u,\ y\right)\neq \ d\left(v,\ x\right)\mathrm{-}d\left(v,\ y\right)$ اندازه کوچک‌ترین مجموعه تفکیک‌کننده دوگانه در گراف $G$ را با ${\psi} (G)$ نشان می‌دهند. در این مقاله، ضمن آشنایی با مفهوم و خواص ${\psi} (G)$, برخی مجموعه‌های تفکیک‌کننده رأس‌ها با کوچکترین اندازه را برای گراف یالی $L(C_n\circ{\overline{K}}_m)$ و گراف $(C_n\circ{\overline{K}}_m)\square P_k$ محاسبه می‌کنیم، که در آن نمادهای $\circ$ و $\square$ به‌ترتیب حاصل‌ضرب کرونا و حاصل‌ضرب دکارتی بین دو گراف را مشخص می‌کنند. به‌ویژه، در پاسخ به مسأله مشخص نمودن گراف‌های $G$ و $H$، که برای آن‌ها تساوی ${\psi}(G\square H)={\psi}(G)+{\psi}(H)-1$ برقرار است \cite{15}، ما نشان می‌دهیم که اگر $ n\ge 3$ و $m,k\ge 2$ عددهای صحیح باشند، آن‌گاه ${\psi} \left((C_n\circ{\overline{K}}_m)\square P_k\right)$ برابر است با $.{\psi} \left(C_n\circ{\overline{K}}_m)+{\psi} (P_k\right)-1$
کلیدواژه‌ها
مجموعه تفکیک کننده دوگانه؛ حاصل ضرب دکارتی؛ حاصل ضرب کرونا؛ گراف یالی
سایر فایل های مرتبط با مقاله Extended MSCI-2308-1599,ev.pdf
مراجع
[1] W. Abidin, A. N. M. Salman and S. W. Saputro, The non-isolated resolving number of some corona graphs, Published under licence by IOP Publishing Ltd, J. Phys. Conf. Ser. , 1097 (2018). [2] A. Ahmad, M. Baca and S. Sultan, Minimal doubly resolving sets of necklace graph, Math. Reports., 20 (2018) 123–129. [3] R. F. Bailey, The metric dimension of small distance-regular and strongly regular graphs, Australas. J. Combin., 62 (2015) 18–34. [4] J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo,M. L.Puertas, C. Serra and D. R. Wood, On the metric dimension of Cartesian products of graphs, SIAM J. Discrete Math., 21 (2007) 423–441. [5] G. Chartrand, L. Eroh, M. A. Johnson and O. R. Oellermann, Resolvability in graphs and the metric dimension of a graph, Discrete Appl. Math., 105 (2000) 99–113. [6] C. Godsil and G. Royle, Algebraic graph theory, Graduate Texts in Mathematics, 207, Springer-Verlag, New York, 2001. [7] F. Harary and R. A. Melter, On the metric dimension of a graph, Combin., 2 (1976) 191–195. [8] M. Jannesari and B. Omoomi, The metric dimension of the lexicographic product of graphs, Discrete Math., 312 (2012) 3349–3356. [9] M. Jannesari, On doubly resolving sets in graphs, Bull. Malays. Math. Sci. Soc., 45 (2022) 2041–2052. [10] S. Khuller, B. Raghavachari and A. Rosenfeld, Localization in graphs,Technical Report CS-TR-3326, University of Maryland at College Park, 1994. [11] D. Kuziak, I. Peterin and I. G. Yero, Resolvability and strong resolvability in the direct product of graphs, Results Math., 71 (2017) 509–526. [12] J. B. Liu, A. Zafari and H. Zarei, Metric Dimension, Minimal Doubly Resolving Sets, and the Strong Metric Dimension for Jellyfish Graph and Cocktail Party Graph, Complexity, 2020 (2020) 1–7. [13] J. B. Liu and A. Zafari, Computing minimal doubly resolving sets and the strong metric dimension of the layer Sun graph and the line graph of the layer Sun graph, Complexity, 2020 (2020) 1–8. [14] K. Nie and K. Xu, The doubly metric dimension of corona product graphs, Filomat, 37 (2023) 4375–4386. [15] K. Nie and K. Xu, The doubly metric dimension of cylinder graphs and torus graphs, Bull. Malays. Math. Sci. Soc., 46 (2023) 19 pp. [16] O. R. Oellermann and J. Peters-Fransen, The strong metric dimension of graphs and digraphs, Discrete Appl. Math., 155 (2007) 356–364. [17] A. Sebö and E. Tannier, On metric generators of graphs, Math. Oper. Res., 29 (2004) 383–393. [18] P. J. Slater, Leaves of trees, Proceedings of the Sixth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic Univ., Boca Raton, Fla.), Congress. Numer., No. XIV, Utilitas Math., Winnipeg, MB, (1975) 549–559. [19] I. G. Yero, D. Kuziak and J. A. Rodrı́guez-Velázquez, On the metric dimension of corona product graphs, Comput. Math. Appl., 61 (2011) 2793–2798.
آمار تعداد مشاهده مقاله: 465 تعداد دریافت فایل اصل مقاله: 364

سامانه مدیریت نشریات علمی. طراحی و پیاده سازی از سیناوب

پیوندهای مفید

اخبار و اعلانات

آمار

مجموعه‌های تفکیک‌کننده رأس‌ها در گراف‌ها با کوچکترین اندازه