خوش فاصله متوازن روی گراف مکعب فولدد
محورهای موضوعی : آمار
سیده مریم حسینی پور
1
(
دانشگاه فردوسی مشهد- دانشکده ریاضی
)
فریدون رهبرنیا
2
(
دانشیار، گروه ریاضی کاربردی، دانشکده علوم ریاضی، دانشگاه فردوسی مشهد، مشهد، ایران
)
مهدی علائیان
3
(
استاد، گروه ریاضی محض، دانشکده علوم ریاضی، دانشگاه علم و صنعت ایران، تهران، ایران
)
احمد عرفانیان
4
(
استاد، گروه ریاضی محض، دانشکده علوم ریاضی، دانشگاه فردوسی مشهد، مشهد، ایران
)
کلید واژه: nicely edge distance-balanced, folded cube, : nicely distance-balanced, hamming graph, hyper cube,
چکیده مقاله :
گراف غیر تهی Γ به ترتیب یک گراف خوش فاصله متوازن (خوش فاصله متوازن یالی) نامیده میشود هرگاه اعداد صحیح مثبت γ_V(γ_E) وجود داشته باشند به طوری که برای هر دو رأس مجاور u و v از V(Γ)، γ_Vرأس از V(Γ) (γ_E یال از E(Γ)) وجود داشته باشند به طوری که به رأس u نزدیکتر از رأس v باشند و بلعکس γ_Vرأس از V(Γ) (γ_E یال از E(Γ)) وجود داشته باشند به طوری که به رأس v نزدیکتر از رأس u باشند در این مقاله نشان میدهیم ابرمکعب Q_n و گراف مکعب فولدد F_n، یک گراف خوش فاصله متوازن بوده و Q_n خوش فاصله متوازن یالی است.
A nontrivial graph is called nicely distance-balanced (nicely edge distance-balanced), whenever there exist positive integers γ_V (γ_E), such that for any adjacent vertices u and v in V(Γ), there are exactly γ_V vertices in V(Γ) (γ_E edges in E(Γ) that are closer to u than v, and exactly γ_V vertices in V(Γ) (γ_E edges in E(Γ)) that are closer to v than u. In this paper, we will prove that hyper cube Q_n and the folded cube F_n are nicely distance-balanced and Q_n is also nicely edge distance-balanced.A nontrivial graph is called nicely distance-balanced (nicely edge distance-balanced), whenever there exist positive integers γ_V (γ_E), such that for any adjacent vertices u and v in V(Γ), there are exactly γ_V vertices in V(Γ) (γ_E edges in E(Γ) that are closer to u than v, and exactly γ_V vertices in V(Γ) (γ_E edges in E(Γ)) that are closer to v than u. In this paper, we will prove that hyper cube Q_n and the folded cube F_n are nicely distance-balanced and Q_n is also nicely edge distance-balanced.
[1] Djoković, D. Ž. Distance-preserving subgraphs of hypercubes. Journal of Combinatorial Theory, Series B, 14(3): 263-267(1973)
[2] Chepoi, V. D. Isometric subgraphs of Hamming graphs and d-convexity. Cybernetics, 24(1):6-11(1988)
[3] Bandelt, H. J., & Chepoi, V. Metric graph theory and geometry: a survey. Contemporary Mathematics, 453:49-86 (2008)
[4] A. Heydari, B. TaeriSzeged index of TUC4C8 (S) nanotubes. European J. Combin., 30:1134-1141 (2009)
[5] M.H. Khalifeh, H. Yousefi-Azari, A.R. AshrafiA matrix method for computing Szeged and vertex PI indices of join and composition of graphs. Linear Algebra Appl., 429: 2702-2709 (2008)
[6] P. Khadikar, N. Deshpande, P. Kale, A. Dobrynin, I. Gutman, G. DömötörThe Szeged index and an analogy with the Wiener Index. J. Chem. Inf. Comput. Sci., 35: 547-550 (1995)
[7] K. Handa, Bipartite graphs with balanced (a, b)-partitions. Ars Combin. 51:113–119(1999)
[8] J. Jerebic, S. Klavžar, D. F. Rall, Distance-balanced graphs, Ann. Comb. 12:71-79 (2008)
[9] A. Iliˇc, S. Klavžar, M. Milanoviˇc, On distance-balanced graphs, European J. Combin. 31:733-737 (2010)
[10] Abedi, A., Alaeiyan, M., Hujdurović, A., & Kutnar, K. Quasi-λ-distance-balanced graphs. Discrete Applied Mathematics, 227:21-28 (2017)
[11] Balakrishnan, K., Changat, M., Peterin, I., Špacapan, S., Šparl, P., & Subhamathi, A. R. Strongly distance-balanced graphs and graph products. European Journal of Combinatorics, 30(5): 10481053(2009)
[12] Faramarzi, H., Rahbarnia, F., & Tavakoli, M. Some results on distanced-balanced and strongly distanced-balanced graphs. Italian Journal of Pure and Applied Mathematics, 9:(2017)
[13] Tavakoli, M., YOUSEFI, A. H., & Ashrafi, A. R. Note on edge distance-balanced graphs, 1-6 (2012)
[14] D. Eppstein, The lattice dimension of a graph, European J. Combin. 26:585–592 (2005)
[15] M. H. Khalifeh, H. Yousefi-Azari, A. R. Ashrafi, A matrix method for computing Szeged and vertex PI indices of join and composition of graphs, Linear Algebra Appl. 429:2702–2709 (2005)
[16] Zeinloo, S., Alaeiyan, M., & Karaj, I. Classification of Nicely Edge-Distance-Balanced Graphs. Computer Science, 14(1): 233-245 (2019)
[17] Faghani, M., Pourhadi, E., & Kharazi, H. On the new extension of distance-balanced graphs. Transactions on Combinatorics, 5(4):21-34 (2016)
[18] Karimi, F., & Mirafzal, S. M. The spectrum of the hyper-star graphs and their line graphs. Journal of New Researches in Mathematics, 5(21): 125-132 (2019)
[19] K. Kutnar, Š. Miklaviˇc, Nicely
distance-balanced graphs, European J. Combin. 39: 57–67(2014)
[20] R. F. Bailey, P. J. Cameron, Base size, metric dimension and other invariants of groups and graphs, Bull. Lond.Math. Soc. 43 (2):209-242 (2011)
[21] A. Hora, N. Obata, Quantum Probability and Spectral Analysis of Graphs, Theoretical and Mathematical Physics. Springer, Berlin, Heidelberg, (2007)
[22] van Bon, J. Finite primitive distance-transitive graphs. European Journal of Combinatorics, 28(2):517-532 (2007)
