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

نوع مقاله : مقاله پژوهشی

نویسندگان

1 گروه ریاضی، دانشکده علوم‌پایه، دانشگاه پیام‌نور، تهران، ایران

2 گروه ریاضی، دانشکده علوم‌پایه، دانشگاه آیت الله العظمی بروجردی (ره)، بروجرد، ایران

3 دانشکده علوم ریاضی، دانشگاه یزد، یزد، ایران

چکیده

فرض کنیم $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$

کلیدواژه‌ها

مراجع

[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. Cá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. Sebö 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-Velázquez, On the metric dimension of corona product graphs, Comput. Math. Appl., 61 (2011) 2793–2798.

فایل ها

سابقه مقاله

  • تاریخ دریافت: 15 مرداد 1402
  • تاریخ بازنگری: 22 شهریور 1402
  • تاریخ پذیرش: 15 مهر 1402
  • تاریخ انتشار آنلاین: 06 آبان 1402

هم رسانی

ارجاع به این مقاله

آمار