A characterization of block graphs |
| |
Authors: | Ali Behtoei Bijan Taeri |
| |
Affiliation: | Department of Mathematical Sciences, Isfahan University of Technology, Isfahan 84156-8311, Iran |
| |
Abstract: | A block graph is a graph whose blocks are cliques. For each edge e=uv of a graph G, let Ne(u) denote the set of all vertices in G which are closer to u than v. In this paper we prove that a graph G is a block graph if and only if it satisfies two conditions: (a) The shortest path between any two vertices of G is unique; and (b) For each edge e=uv∈E(G), if x∈Ne(u) and y∈Ne(v), then, and only then, the shortest path between x and y contains the edge e. This confirms a conjecture of Dobrynin and Gutman [A.A. Dobrynin, I. Gutman, On a graph invariant related to the sum of all distances in a graph, Publ. Inst. Math., Beograd. 56 (1994) 18-22]. |
| |
Keywords: | Block graphs 2-connected graphs Graph invariants Wiener index |
本文献已被 ScienceDirect 等数据库收录! |
|