Strongly chordal graph

In the mathematical area of graph theory, an undirected graph G is strongly chordal if it is a chordal graph and every cycle of even length (≥ 6) in G has an odd chord, i.e., an edge that connects two vertices that are an odd distance (>1) apart from each other in the cycle.^[1]

Characterizations

Strongly chordal graphs have a forbidden subgraph characterization as the graphs that do not contain an induced cycle of length greater than three or an n-sun (n ≥ 3) as an induced subgraph.^[2] An n-sun is a chordal graph with 2n vertices, partitioned into two subsets U = {u₁, u₂,...} and W = {w₁, w₂,...}, such that each vertex w_i in W has exactly two neighbors, u_i and u_{(i + 1) mod n}. An n-sun cannot be strongly chordal, because the cycle u₁w₁u₂w₂... has no odd chord.

Strongly chordal graphs may also be characterized as the graphs having a strong perfect elimination ordering, an ordering of the vertices such that the neighbors of any vertex that come later in the ordering form a clique and such that, for each i < j < k < l, if the ith vertex in the ordering is adjacent to the kth and the lth vertices, and the jth and kth vertices are adjacent, then the jth and lth vertices must also be adjacent.^[3]

A graph is strongly chordal if and only if every one of its induced subgraphs has a simple vertex, a vertex whose neighbors have neighborhoods that are linearly ordered by inclusion.^[4] Also, a graph is strongly chordal if and only if it is chordal and every cycle of length five or more has a 2-chord triangle, a triangle formed by two chords and an edge of the cycle.^[5]

A graph is strongly chordal if and only if each of its induced subgraphs is a dually chordal graph.^[6]

Strongly chordal graphs may also be characterized in terms of the number of complete subgraphs each edge participates in.^[7] Yet another characterization is given in.^[8]

Recognition

It is possible to determine whether a graph is strongly chordal in polynomial time, by repeatedly searching for and removing a simple vertex. If this process eliminates all vertices in the graph, the graph must be strongly chordal; otherwise, if this process finds a subgraph without any more simple vertices, the original graph cannot be strongly chordal. For a strongly chordal graph, the order in which the vertices are removed by this process is a strong perfect elimination ordering.^[9]

Alternative algorithms are now known that can determine whether a graph is strongly chordal and, if so, construct a strong perfect elimination ordering more efficiently, in time O(min(n², (n + m) log n)) for a graph with n vertices and m edges.^[10]

Subclasses

An important subclass (based on phylogeny) is the class of leaf powers defined as follows: A tree T is a k-leaf root of a graph G=(V,E) if V is contained in the set of leaves of T and for vertices x,y in V, xy is an edge in E if and only if their distance in T is at most k. Then G is called a k-leaf power. A graph is a leaf power if it is a k-leaf power for some k.^[11]

Since powers of strongly chordal graphs are strongly chordal and trees are strongly chordal, we have: Leaf powers form a (proper) subclass of strongly chordal graphs. It is easy to see that a graph is a 2-leaf power if and only if it is the disjoint union of cliques (i.e., a P₃-free graph). Characterizations of 3- and 4-leaf powers are given in,^[12] which enable linear time recognition. For k > 5 the recognition problem of k-leaf powers is open, and likewise it is an open problem how to recognize leaf powers in polynomial time.

Another important subclass of strongly chordal graphs are interval graphs. In ^[13] it is shown that interval graphs and the larger class of rooted directed path graphs are leaf powers.

Algorithmic problems

Since strongly chordal graphs are both chordal graphs and dually chordal graphs, various NP-complete problems such as Independent Set, Clique, Coloring, Clique Cover, Dominating Set, and Steiner Tree can be solved efficiently for strongly chordal graphs. Graph isomorphism is isomorphism-complete for strongly chordal graphs.^[14] Hamiltonian Circuit remains NP-complete for strongly chordal split graphs.^[15]

Notes

1. Brandstädt, Le & Spinrad (1999), Definition 3.4.1, p. 43.
2. Chang (1982); Farber (1983); Brandstädt, Le & Spinrad (1999), Theorem 7.2.1, p. 112.
3. Farber (1983); Brandstädt, Le & Spinrad (1999), Theorem 5.5.1, p. 77.
4. Farber (1983); Brandstädt, Le & Spinrad (1999), Theorem 5.5.2, p. 78.
5. Dahlhaus, Manuel & Miller (1998).
6. Brandstädt et al. (1998), Corollary 3, p. 444
7. McKee (1999)
8. De Caria & McKee (2014)
9. Farber (1983).
10. Lubiw (1987); Paige & Tarjan (1987); Spinrad (1993).
11. Nishimura, Ragde & Thilikos (2002)
12. Rautenbach (2006),Brandstädt & Le (2006),Brandstädt, Le & Sritharan (2008)
13. Brandstädt et al. (2010)
14. Uehara, Toda & Nagoya (2005)
15. Müller (1996)

References

• Brandstädt, Andreas; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Dually Chordal Graphs", SIAM Journal on Discrete Mathematics 11: 437–455, doi:10.1137/s0895480193253415.
• Brandstädt, Andreas; Hundt, Christian; Mancini, Federico; Wagner, Peter (2010), "Rooted directed path graphs are leaf powers", Discrete Mathematics 310: 897–910.
• Brandstädt, Andreas; Le, Van Bang (2006), "Structure and linear time recognition of 3-leaf powers", Information Processing Letters 98: 133–138.
• Brandstädt, Andreas; Le, Van Bang; Sritharan, R. (2008), "Structure and linear time recognition of 4-leaf powers", ACM Transactions on Algorithms 5: Article 11.
• Brandstädt, Andreas; Le, Van Bang; Spinrad, Jeremy (1999), Graph Classes: A Survey, SIAM Monographs on Discrete Mathematics and Applications, ISBN 0-89871-432-X.
• Chang, G. J. (1982), K-domination and Graph Covering Problems, Ph.D. thesis, Cornell University.
• Dahlhaus, E.; Manuel, P. D.; Miller, M. (1998), "A characterization of strongly chordal graphs", Discrete Mathematics 187 (1–3): 269–271, doi:10.1016/S0012-365X(97)00268-9.
• De Caria, P.; McKee, T.A. (2014), "Maxclique and unit disk characterizations of strongly chordal graphs", Discussiones Mathematicae Graph Theory 34: 593–602, doi:10.7151/dmgt.1757.
• Farber, M. (1983), "Characterizations of strongly chordal graphs", Discrete Mathematics 43 (2–3): 173–189, doi:10.1016/0012-365X(83)90154-1.
• Lubiw, A. (1987), "Doubly lexical orderings of matrices", SIAM Journal on Computing 16 (5): 854–879, doi:10.1137/0216057.
• McKee, T. A. (1999), "A new characterization of strongly chordal graphs", Discrete Mathematics 205 (1–3): 245–247, doi:10.1016/S0012-365X(99)00107-7.
• Müller, H. (1996), "Hamiltonian Circuits in Chordal Bipartite Graphs", Discrete Mathematics 156: 291–298.
• Nishimura, N.; Ragde, P.; Thilikos, D.M. (2002), "On graph powers for leaf-labeled trees", Journal of Algorithms 42: 69–108.
• Paige, R.; Tarjan, R. E. (1987), "Three partition refinement algorithms", SIAM Journal on Computing 16 (6): 973–989, doi:10.1137/0216062.
• Rautenbach, D. (2006), "Some remarks about leaf roots", Discrete Mathematics 306: 1456–1461.
• Spinrad, J. (1993), "Doubly lexical ordering of dense 0–1 matrices", Information Processing Letters 45 (2): 229–235, doi:10.1016/0020-0190(93)90209-R.
• Uehara, R.; Toda, S.; Nagoya, T. (2005), "Graph isomorphism completeness for chordal bipartite and strongly chordal graphs", Discrete Applied Mathematics 145 (3): 479–482, doi:10.1016/j.dam.2004.06.008.