<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 12 Issue 1" %>
Distance-Balanced Graphs
Janja Jerebic1, Sandi Klavžar1, and Douglas F. Rall2
1Department of Mathematics and Computer Science FNM, University of Maribor, Koroška cesta 160, 2000 Maribor, Slovenia
{janja.jerebic, sandi.klavzar}@uni-mb.si
2Department of Mathematics, Furman University, Greenville, SC 29613, USA
Annals of Combinatorics 12 (1) p.71-79 March, 2008
AMS Subject Classification:05C12, 05C40
Distance-balanced graphs are introduced as graphs in which every edge uv has the following property: The number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. Basic properties of these graphs are obtained. The new concept is connected with symmetry conditions in graphs and local operations on graphs are studied with respect to it. Distance-balanced Cartesian and lexicographic products of graphs are also characterized. Several open problems are posed along the way.
Keywords: graph distance, distance-balanced graphs, graph products, connectivity


1. A.R. Ashrafi and A. Loghman, PI index of armchair polyhex nanotubes, Ars Combin. 80 (2006) 193-199.

2. H.-J. Bandelt and V. Chepoi, Metric graph theory and geometry: a survey, Contemp. Math. 453 (2008) 49-86.

3. V. Chepoi, Isometric subgraphs of Hamming graphs and d-convexity, Cybernetics 24 (1) (1988) 6-11.

4. D.Ž. Djoković, Distance-preserving subgraphs of hypercubes, J. Combin. Theory Ser. B 14 (1973) 263-267.

5. R. Frucht, J.E. Graver, and M.E. Watkins, The groups of the generalized Petersen graphs, Proc. Cambridge Philos. Soc. 70 (1971) 211-218.

6. K. Fukuda and K. Handa, Antipodal graphs and oriented matroids, Discrete Math. 111 (1-3) (1993) 245-256.

7. A. Graovac, M. Juvan, M. Petkovšek, A. Vesel, and J. Žerovnik, The Szeged index of fasciagraphs, MATCH Commun. Math. Comput. Chem. 49 (2003) 47-66.

8. I. Gutman and A.A. Dobrynin, The Szeged index―a success story, Graph Theory Notes N. Y. 34 (1998) 37-44.

9. K. Handa, Bipartite graphs with balanced (a; b)-partitions, Ars Combin. 51 (1999) 113-119.

10. W. Imrich and S. Klavžar, Product Graphs: Structure and Recognition, Wiley Interscience, New York, 2000.

11. P.V. Khadikar, On a novel structural descriptor PI, Nat. Acad. Sci. Lett. 23 (2000) 113-118.

12. S. Klavžar, On the PI index: PI-partitions and Cartesian product graphs, MATCH Commun. Math. Comput. Chem. 57 (3) (2007) 573-586.

13. A. Malnič and D. Marušič, personal communication.