On 2-distance-balanced graphs

Boštjan Frelih, Štefko Miklavič


Let n denote a positive integer. A graph Γ of diameter at least n is said to be n-distance-balanced whenever for any pair of vertices u, v of Γ at distance n, the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u. In this article we consider n = 2 (e.g. we consider 2-distance-balanced graphs). We show that there exist 2-distance-balanced graphs that are not 1-distance-balanced (e.g. distance-balanced). We characterize all connected 2-distance-balanced graphs that are not 2-connected. We also characterize 2-distance-balanced graphs that can be obtained as cartesian product or lexicographic product of two graphs.


n-distance-balanced graph, cartesian product, lexicographic product

Full Text:


DOI: https://doi.org/10.26493/1855-3974.1382.dee

ISSN: 1855-3974

Issues from Vol 6, No 1 onward are partially supported by the Slovenian Research Agency from the Call for co-financing of scientific periodical publications