标题: | CENTERS OF CHORDAL GRAPHS |
作者: | CHANG, GJ 应用数学系 Department of Applied Mathematics |
公开日期: | 1991 |
摘要: | In a graph G = (V, E), the eccentricity e(S) of a subset S is contained in or equal to V is max(x is-an-element-of V) min(y is-an-element-of S) d(x, y); and e(x) stands for e({x}). The diameter of G is max(x is-an-element-of V) e(x), the radius r(G) of G is min(x is-an-element-of V) e(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) less-than-or-equal-to d(G) less-than-or-equal-to 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. |
URI: | http://hdl.handle.net/11536/3921 http://dx.doi.org/10.1007/BF01787637 |
ISSN: | 0911-0119 |
DOI: | 10.1007/BF01787637 |
期刊: | GRAPHS AND COMBINATORICS |
Volume: | 7 |
Issue: | 4 |
起始页: | 305 |
结束页: | 313 |
显示于类别: | Articles |
文件中的档案:
If it is a zip file, please download the file and unzip it, then open index.html in a browser to view the full text content.