2022/01/07 by Blas Fernández, Fernandez, Blas, Ademir Hujdurović +1
Computer Science · Engineering · Mathematics · #05C12 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.2201.02430
openalex publication_date 2022/01/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A graph Γ is said to be distance-balanced if for any edge uv of Γ, the number of vertices closer to u than to v is equal to the number of vertices closer to v than to u, and it is called nicely distance-balanced if in addition this number is independent of the chosen edge uv. A graph Γ is said to be strongly distance-balanced if for any edge uv of Γ 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. In this paper we answer an open problem posed by Kutnar and Miklavič [European J. Combin. 39 (2014), 57-67] by constructing several infinite families of nonbipartite nicely distance-balanced graphs which are not strongly distance-balanced. We disprove a conjecture regarding characterization of strongly distance-balanced graphs posed by Balakrishnan et al. [European J. Combin. 30 (2009), 1048-1053] by providing infinitely many counterexamples, and answer an open question posed by Kutnar et al. in [Discrete Math. 306 (2006), 1881-1894] regarding existence of semisymmetric distance-balanced graphs which are not strongly distance-balanced by providing an infinite family of such examples. We also show that for a graph Γ with n vertices and m edges it can be checked in O(mn) time if Γ is strongly-distance balanced and if Γ is nicely distance-balanced.