Lexbfs-orderings and powers of hhd-free graphs∗

From MaRDI portal
Publication:4254590





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.











This page was built for publication: Lexbfs-orderings and powers of hhd-free graphs∗

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4254590)