LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem (Q1962066)

From MaRDI portal
Revision as of 20:39, 29 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
scientific article
Language Label Description Also known as
English
LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem
scientific article

    Statements

    LexBFS-orderings of distance-hereditary graphs with application to the diametral pair problem (English)
    0 references
    0 references
    0 references
    16 July 2000
    0 references
    A graph \(G=(V,E)\) is distance-hereditary if it is connected and every induced path in \(G\) is isometric, i.e., for every connected induced subgraph \(H=(W,F)\) we have \(d_H(u,v) = d_G(u,v)\) for all vertices \(u,v \in W\). In the \(k\)th power \(G^k = (V,E^k)\) of \(G\) two vertices \(u\) and \(v\) are adjacent whenever \(d_G(u,v) \leq k\). All even powers of distance-hereditary graphs are chordal, and all odd powers are HHD-free; see \textit{H.-J. Bandelt, A. Henkmann}, and \textit{F. Nicolai} [Discrete Math. 145, No. 1-3, 37-60 (1995; Zbl 0838.05045)]. The authors prove an extension of this result dealing with common dismantling schemes provided by Lexicographic Breadth-First Search (LexBFS): Every LexBFS-ordering of a distance-hereditary graph \(G\) is both a perfect elimination ordering of all even powers of \(G\) and a semi-simplicial elimination ordering of all powers of \(G\); see \textit{B. Jamison} and \textit{S. Olariu} [Adv. Appl. Math. 9, No. 3, 364-376 (1988; Zbl 0684.05020)] for semi-simplicial elimination and \textit{F. F. Dragan, F. Nicolai}, and \textit{A. Brandstädt} [Int. J. Comput. Math. 69, No. 3-4, 217-242 (1998)] and \textit{F. F. Dragan} and \textit{F. Nicolai} [Int. J. Comput. Math. 71, No. 1, 35-56 (1999; Zbl 0934.05110)] for related results on HHD-free graphs. One forbidden subgraph characterizes the class of all distance-hereditary graphs \(G\) such that every LexBFS-ordering of \(G\) is a perfect elimination ordering of all powers of \(G\). Moreover, the diameter and a diametral pair of a distance-hereditary graph can be computed in linear time.
    0 references
    distance-hereditary graph
    0 references
    lexicographic breadth-first-search
    0 references
    perfect elimination ordering
    0 references
    metric power
    0 references
    diameter
    0 references
    linear time algorithm
    0 references

    Identifiers