scientific article; zbMATH DE number 1230485
Let \(G\) be an undirected, connected simple graph which does not form a clique. It is known that \(G\) is chordal if every cycle of length greater than three has a chord. It is also known that many optimization problems are NP-complete on chordal graphs which have a perfect elimination ordering \(v_1,v_2,\dots,v_n\) of vertices such that for each \(1\leq i\leq n\), \(v_i\) is simplicial, i.e., the neighbors of \(v_i\) form a clique in the subgraph induced by \(\{v_i,\dots,v_n\}\). In the present paper the class of doubly chordal graphs is investigated. It is a subclass of the class of chordal graphs which probably can be used to solve the above-mentioned problems in polynomial time. \(G\) is doubly chordal if it admits a doubly perfect elimination ordering \(v_1,v_2,\dots,v_n\) of vertices such that, for each \(i\) with \(1\leq i\leq n\), \(v_i\) is doubly simplicial, i.e., it is simplicial and has a maximum neighbor in the subgraph induced by \(\{v_i, \dots, v_n\}\). Here a vertex \(u\) from the neighborhood \(N[v_i]\) is a maximum neighbor of \(v_i\) if \(N[w] \subseteq N[u]\) for any \(w\in N[v_i]\). Investigating these graphs, characterizations and properties are derived based on the neighborhood and on the clique matrices of a graph known to be 0-1 matrices. Moreover additional concepts are introduced, for example, a doubly lexical ordering of a matrix which is an ordering of the rows and of the columns of the matrix so that both rows and columns, as vectors, are lexically increasing. With the help of a lot of lemmas the authors get, for example, the following characterization for chordal graphs: \(G\) is chordal if and only if a doubly lexical ordering of a clique matrix of \(G\) admits a perfect elimination ordering (Theorem 5). In a similar manner they get, using analogously restricted concepts, necessary and sufficient conditions for \(G\) to be a doubly chordal graph (Theorems 8 and 11). Finally, it is mentioned that a doubly perfect elimination ordering of a doubly chordal graph can be computed by an \(O(n^2)\) time algorithm.
- Dualizing chordal graphs
- Doubly lexical ordering of dense 0--1 matrices
- New proofs about the number of empty convex 4-gons and 5-gons in a planar point set
- Efficient parallel algorithm to compute a doubly perfect elimination ordering of a doubly chordal graph
- Double-crossed chords and distance-hereditary graphs
- Comparing trees characteristic to chordal and dually chordal graphs
- Doubly Lexical Orderings of Matrices
- scientific article; zbMATH DE number 1234609 (Why is no real title available?)
- Fast algorithms of hereditary doubly chordal graphs
- Dually and strongly chordal graphs
- A characterization of the odd graphs and the doubled odd graphs with a few of their intersection numbers
This page was built for publication:
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4222497)