A characterization of block graphs

作者：Behtoei Ali; Jannesari Mohsen; Taeri Bijan^*

来源：Discrete Applied Mathematics, 2010, 158(3): 219-221.

DOI：10.1016/j.dam.2009.09.024

• Block graphs
• 2-connected graphs
• Graph invariants
• Wiener index

A block graph is a graph whose blocks are cliques. For each edge e = uv of a graph G, let N(e)(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 is an element of E(G), if x is an element of N(e)(u) and y is an element of N(e)(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].

• 出版日期2010-2-6