Centers of chordal graphs
Journal
Graphs and Combinatorics
Journal Volume
7
Journal Issue
4
Pages
305-313
Date Issued
1991
Author(s)
Abstract
In a graph G = (V, E), the eccentricity e(S) of a subset S {Mathematical expression} is maxx ∈ Vminy ∈ Sd(x, y); and e(x) stands for e({x}). The diameter of G is maxx ∈ Ve(x), the radius r(G) of G is minx ∈ Ve(x) and the clique radius cr(G) is min e(K) where K runs over all cliques. The center of G is the subgraph induced by C(G), the set of all vertices x with e(x) = r(G). A clique center is a clique K with e(K) = cr(G). In this paper, we study the problem of determining the centers of chordal graphs. It is shown that the center of a connected chordal graph is distance invariant, biconnected and of diameter no more than 5. We also prove that 2cr(G) ≤ d(G) ≤ 2cr(G) + 1 for any connected chordal graph G. This result implies a characterization of a biconnected chordal graph of diameter 2 and radius 1 to be the center of some chordal graph. © 1991 Springer-Verlag.
Type
journal article