On 2-distance-balanced graphs

Authors

  • Boštjan Frelih University of Primorska, Slovenia
  • Štefko Miklavič University of Primorska, Slovenia

DOI:

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

Keywords:

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

Abstract

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.

Published

2018-01-26

Issue

Section

Articles