×
Kutnar, Klavdija; Malnič, Aleksander; Marušič, Dragan; Miklavič, Štefko

Distance-balanced graphs: symmetry conditions. (English) Zbl 1100.05029

Discrete Math. 306, No. 16, 1881-1894 (2006).
Summary: A graph \(X\) is said to be distance-balanced if for any edge \(uv\) of \(X\), the number of vertices closer to \(u\) than to \(v\) is equal to the number of vertices closer to \(v\) than to \(u\). A graph \(X\) is said to be strongly distance-balanced if for any edge \(uv\) of \(X\) and any integer \(k\), the number of vertices at distance \(k\) from \(u\) and at distance \(k+1\) from \(v\) is equal to the number of vertices at distance \(k+1\) from \(u\) and at distance \(k\) from \(v\). Exploring the connection between symmetry properties of graphs and the metric property of being (strongly) distance-balanced is the main theme of this article. That a vertex-transitive graph is necessarily strongly distance-balanced and thus also distance-balanced is an easy observation. With only a slight relaxation of the transitivity condition, the situation changes drastically: there are infinite families of semisymmetric graphs (that is, graphs which are edge-transitive, but not vertex-transitive) which are distance-balanced, but there are also infinite families of semisymmetric graphs which are not distance-balanced. Results on the distance-balanced property in product graphs prove helpful in obtaining these constructions. Finally, a complete classification of strongly distance-balanced graphs is given for the following infinite families of generalized Petersen graphs: GP\((n,2)\), GP\((5k+1,k)\), GP\((3k\pm 3,k)\), and GP\((2k+2,k)\).

Cited in 1 Review
Cited in 29 Documents

MSC:

05C12 Distance in graphs

Keywords:

vextex-transitive; semisymmetric; generalized Petersen graph

Software:

Magma
Cite Review PDF
Full Text: DOI arXiv

References:

[1] Alspach, B., The classification of hamiltonian generalized Petersen graphs, J. Combin. Theory B, 34, 293-312 (1983) · Zbl 0516.05034
[2] Biggs, N., Algebraic Graph Theory (1974), Cambridge University Press: Cambridge University Press London · Zbl 0284.05101
[3] Boben, M.; Pisanski, T.; Žitnik, A., \(I\)-graphs and the corresponding configurations, J. Combin. Design, 13, 406-424 (2005) · Zbl 1076.05065
[4] Bosma, W.; Cannon, J.; Playoust, C., The MAGMA Algebra system I: the user language, J. Symbolic Comput., 24, 235-265 (1997) · Zbl 0898.68039
[5] Brouwer, A. E.; Cohen, A. M.; Neumaier, A., Distance-Regular Graphs (1989), Springer: Springer Berlin, Heidelberg · Zbl 0747.05073
[6] Comellas, F.; Sampels, M., Deterministic small-world networks, Physica A, 309, 231-235 (2002) · Zbl 0995.60103
[7] M.D.E. Conder, A. Malnič, D. Marušič, P. Potočnik, A census of semisymmetric cubic graphs on up to 768 vertices, J. Algebraic Combin. 23 (2006) 255-294.; M.D.E. Conder, A. Malnič, D. Marušič, P. Potočnik, A census of semisymmetric cubic graphs on up to 768 vertices, J. Algebraic Combin. 23 (2006) 255-294. · Zbl 1089.05032
[8] Diudea, M. V., Toroidal graphenes from 4-valent tori, Bull. Chem. Soc. Japan, 75, 487-492 (2002)
[9] Diudea, M. V.; Nagy, C. L.; Silaghi-Dumitrescu, I.; Graovac, A.; Janežič, D.; Vikić-Topić, D., Periodic cages, J. Chem. Inform. Comput. Sci., 45, 293-299 (2005)
[10] Du, S. F.; Marušič, D., An infinite family of biprimitive semisymmetric graphs, J. Graph Theory, 32, 217-228 (1999) · Zbl 0943.05043
[11] Du, S. F.; Marušič, D., Biprimitive graphs of smallest order, J. Algebraic Combin., 9, 151-156 (1999) · Zbl 0937.05049
[12] Du, S. F.; Xu, M. Y., A classification of semisymmetric graphs of order \(2 pq\), Comm. Algebra, 28, 2685-2715 (2000) · Zbl 0944.05051
[13] Exoo, G.; Harary, F.; Kabell, J., The crossing numbers of some generalized Petersen graphs, Math. Scand., 48, 184-188 (1981) · Zbl 0442.05021
[14] Folkman, J., Regular line-symmetric graphs, J. Combin. Theory, 3, 215-232 (1967) · Zbl 0158.42501
[15] Frucht, R.; Graver, J. E.; Watkins, M., The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc., 70, 211-218 (1971) · Zbl 0221.05069
[16] Graovac, A.; Plavšić, D.; Kaufman, M.; Kirby, E. C.; Pisanski, T., Application of the adjacency matrix eigenvectors method to geometry determination of toroidal carbon molecules, J. Chem. Phys., 113, 1925-1931 (2000)
[17] Handa, K., Bipartite graphs with balanced \((a, b)\)-partitions, Ars Combin., 51, 113-119 (1999) · Zbl 0977.05039
[18] Heydemann, M. C.; Peters, J. G.; Sotteau, D., Spanners of hypercube-derived networks, SIAM J. Discrete Math., 9, 37-54 (1996) · Zbl 0841.68008
[19] Hilano, T.; Nomura, K., Distance degree regular graphs, J. Combin. Theory Ser. B, 37, 96-100 (1984) · Zbl 0567.05028
[20] Imrich, W.; Klavžar, S., Product Graphs: Structure and Recognition (2000), Wiley: Wiley New York · Zbl 0963.05002
[21] Ivanov, A. V., On edge but not vertex transitive regular graphs, Ann. Discrete Math., 34, 273-286 (1987) · Zbl 0629.05040
[22] J. Jerebic, S. Klavžar, D.F. Rall, Distance-balanced graphs, Ann. Combin., submitted for publication.; J. Jerebic, S. Klavžar, D.F. Rall, Distance-balanced graphs, Ann. Combin., submitted for publication.
[23] Klavžar, S.; Lipovac, A., Partial cubes as subdivision graphs and as generalized Petersen graphs, Discrete Math., 263, 157-165 (2003) · Zbl 1014.05064
[24] Kutnar, K.; Malnič, A.; Marušič, D., Chirality of toroidal molecular graphs, J. Chem. Inform. Modeling, 45, 1527-1535 (2005)
[25] Lazebnik, F.; Viglione, R., An infinite series of regular edge- but not vertex-transitive graphs, J. Graph Theory, 41, 249-258 (2002) · Zbl 1012.05083
[26] Lijnen, E.; Ceulemans, A., Oriented 2-cell embeddings of a graph and their symmetry classification: generating algorithms and case study of the Moebius-Kantor graph, J. Chem. Inform. Comput. Sci., 44, 1552-1564 (2004)
[27] Lipschutz, S.; Xu, M. Y., Note on infinite families of trivalent semisymmetric graphs, European J. Combin., 23, 707-711 (2002) · Zbl 1014.05032
[28] Lu, Z.; Xu, M. Y.; Wang, C., On semisymmetric cubic graphs of order \(6 p^2\), Sci. China Ser. A, 47, 1-17 (2004) · Zbl 1217.05107
[29] Malnič, A.; Marušič, D.; Wang, C. Q., Cubic edge-transitive graphs of order \(2 p^3\), Discrete Math., 274, 187-198 (2004) · Zbl 1032.05063
[30] Marušič, D., Constructing cubic edge- but not vertex-transitive graphs, J. Graph Theory, 35, 152-160 (2000) · Zbl 1021.05050
[31] Marušič, D.; Pisanski, T., Symmetries of hexagonal molecular graphs, on the torus, Croat. Chem. Acta, 73, 969-981 (2000)
[32] Marušič, D.; Potočnik, P., Semisymmetry of generalized Folkman graphs, European J. Combin., 22, 333-349 (2001) · Zbl 0979.05056
[33] C.W. Parker, Semisymmetric cubic graphs of twice odd order, European J. Combin., to appear.; C.W. Parker, Semisymmetric cubic graphs of twice odd order, European J. Combin., to appear. · Zbl 1109.05054
[34] P. Potočnik, S. Wilson, A census of edge-transitive tetravalent graphs. \( \langle;\) http://jan.ucc.nau.edu/swilson/C4Site/index.html \(\rangle;\); P. Potočnik, S. Wilson, A census of edge-transitive tetravalent graphs. \( \langle;\) http://jan.ucc.nau.edu/swilson/C4Site/index.html \(\rangle;\)
[35] Sabidussi, G., The composition of graphs, Duke Math. J., 26, 693-696 (1959) · Zbl 0095.37802
[36] Salazar, G., On the crossing numbers of loop networks and generalized Petersen graphs, Discrete Math., 302, 243-253 (2005) · Zbl 1080.05026
[37] Sampels, M., Vertex-symmetric generalized Moore graphs, Discrete Appl. Math., 138, 195-202 (2004) · Zbl 1034.05019
[38] Wilson, S., A worthy family of semisymmetric graphs, Discrete Math., 271, 283-294 (2003) · Zbl 1021.05048
[39] Wilson, S., Semi-transitive graphs, J. Graph Theory, 45, 1-27 (2004) · Zbl 1031.05065
[40] Xiao, W.; Parhami, B., Cayley graphs as models of deterministic small-world networks, Inform. Process. Lett., 97, 115-117 (2006) · Zbl 1184.68060
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.