On nicely distance-balanced of folded cube graphs

Subject Areas : Statistics

Seyedeh Maryam Hosseini pour ¹ , Freydoon Rahbarnia ² , Mehdi Alaeiyan ³ , Ahmad Erfanian ⁴

1 - Department of Pure Mathematics, Ferdowsi University of Mashhad,
2 - Department of Applied Mathematics, Ferdowsi University ofMashhad,
3 - School of Mathematic, Iran University of Science and Technology, Tehran, Iran.
4 - Department of Mathematics and Center of Excellence in Analysis onAlgebraic Structure

Received: 2019-12-18 Accepted : 2020-04-19 Published : 2021-03-01

Keywords: گراف همینگ, خوش فاصله متوازن یالی, مکعب فولدد, ابرمکعب, خوش فاصله متوازن,

Abstract :

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.

References:

[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)