On diameters and radii of bridged graphs (Q1117245)
From MaRDI portal
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | On diameters and radii of bridged graphs |
scientific article |
Statements
On diameters and radii of bridged graphs (English)
0 references
1989
0 references
A subgraph H of a graph G is isometric if the distance between any pair of vertices in H is the same as that in G. A graph is bridged if it contains no isometric cycles of length greater than 3. This class includes, as a proper subclass, the class of chordal graphs, i.e., graphs with no induced cycle of length greater than 3. Denoting the diameter and radius of a graph G by d(G) and r(G), respectively, it follows immediately that \(\lceil d(G)\rceil \leq r(G)\leq d(G)\). Let \(T_ p\) be the graph obtained by triangulating an equilateral triangle of side p with equilateral triangles of side 1. \textit{G. J. Chang} and \textit{G. L. Newhauser} [SIAM J. Algebraic Discrete Methods 5, 332-345 (1984; Zbl 0576.05054)] showed that if G is chordal then \(2r(g)\leq d(G)+2\) and if, furthermore, G contains no induced \(T_ 2\), then \(2r(G)\leq d(G)+1.\) Generalizing this, the author shows that if G is a bridged graph containing no isometric \(T_ p\), then \(6r(G)\leq 3d(G)+p+3.\)
0 references
chordal graphs
0 references
bridged graph
0 references