Lexbfs-orderings and powers of hhd-free graphs<sup>∗</sup> (Q4254590)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 1310665
Language Label Description Also known as
default for all languages
No label defined
    English
    Lexbfs-orderings and powers of hhd-free graphs<sup>∗</sup>
    scientific article; zbMATH DE number 1310665

      Statements

      Lexbfs-orderings and powers of hhd-free graphs<sup>∗</sup> (English)
      0 references
      0 references
      0 references
      10 April 2000
      0 references
      lexicographic breadth-first search
      0 references
      semisimplicial ordering
      0 references
      HHD-free graph
      0 references
      power
      0 references
      LexBFS ordering
      0 references
      perfect elimination ordering
      0 references
      Let \(G\) be a finite simple undirected graph. By \(P_k\) we denote a path of \(k\) vertices and \(k-1\) edges, and by \(C_k\) we denote a cycle of \(k\) vertices and \(k\) edges. A vertex of \(G\) is semisimplicial if it is no midpoint of a \(P_4\). A vertex ordering \((v_1,\dots, v_n)\) of \(G\) is a semisimplicial ordering if for all \(i\), \(1\leq i\leq n\), \(v_i\) is semisimplicial in \(G_i:= G(\{v_i,\dots, v_n\})\). These notions generalize the well-known notion of simplicial vertex (i.e. the neighborhood is a clique) and perfect elimination ordering. A graph is HHD-free if it contains no induced subgraph isomorphic to a house (i.e. the complement of a \(P_5\)), a hole (i.e. a \(C_k\), \(k\geq 5\)), and a domino (i.e. a cycle of length 6 with one chord creating two cycles of length 4). B. Jamison and S. Olarius have shown that every Lexicographic Breadth-First Search (LexBFS) ordering of a HHD-free graph is a semisimplicial ordering. The \(k\)th power of a graph \(G\) is the graph \(G^k\) with the same vertex set, and two vertices are adjacent in \(G^k\) if their distance in \(G\) is at most \(k\). In this paper, it is shown that every LexBFS ordering of a HHD-free graph is a common semisimplicial ordering of all its odd powers (implying that all odd powers of a HHD-free graph are HHD-free). Moreover those graphs are characterized by forbidden subgraphs for which every LexBFS ordering is a common perfect elimination ordering of all powers, and of all even powers, respectively.
      0 references

      Identifiers