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
    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

    Identifiers