Surf Wiki
Save to docs
general/graph-families

From Surf Wiki (app.surf) — the open knowledge base

Strongly chordal graph

Chordal graph where all cycles of even length have odd chords

Strongly chordal graph
Summary

Chordal graph where all cycles of even length have odd chords

In the first graph, the 8-cycle has odd edges 3-6 and 2-7, and the 6-cycles each also have one of those two edges as an odd edge.

In the second graph, although the graph without the red edge is chordal, the red edge must be added to make an odd chord for the 6-cycle formed by all vertices excluding 4 and 5.]]

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.

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. An n-sun is a chordal graph with 2n vertices, partitioned into two subsets U = {u1, u2,...} and W = {w1, w2,...}, such that each vertex wi in W has exactly two neighbors, u**i and u(i + 1) mod n. An n-sun cannot be strongly chordal, because the cycle u1w1u2w2... 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

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. 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.

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

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

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.

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(n2, (n + m) log n)) for a graph with n vertices and m edges.

Subclasses

An important subclass (based on phylogeny) is the class of k-leaf powers, the graphs formed from the leaves of a tree by connecting two leaves by an edge when their distance in the tree is at most k. A leaf power is a graph that is a k-leaf power for some k. Since powers of strongly chordal graphs are strongly chordal and trees are strongly chordal, it follows that leaf powers are strongly chordal. They form a proper subclass of strongly chordal graphs, which in turn includes the cluster graphs as the 2-leaf powers. Another important subclass of strongly chordal graphs are interval graphs. In 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. Hamiltonian Circuit remains NP-complete for strongly chordal split graphs.

Notes

References

  • {{citation
  • {{citation | doi-access = free
  • {{citation
  • {{citation | article-number = 11
  • {{citation | author1-link = Andreas Brandstädt | url-access = registration
  • {{citation
  • {{citation
  • {{citation | doi-access = free | hdl-access = free
  • {{citation
  • {{citation
  • {{citation
  • {{citation
  • {{citation
  • {{citation
  • {{citation
  • {{citation
  • {{citation

References

  1. {{harvtxt. Brandstädt. Le. Spinrad. 1999, Definition 3.4.1, p. 43.
  2. {{harvtxt. Chang. 1982; {{harvtxt. Farber. 1983; {{harvtxt. Brandstädt. Le. Spinrad. 1999, Theorem 7.2.1, p. 112.
  3. {{harvtxt. Farber. 1983; {{harvtxt. Brandstädt. Le. Spinrad. 1999, Theorem 5.5.1, p. 77.
  4. {{harvtxt. Farber. 1983; {{harvtxt. Brandstädt. Le. Spinrad. 1999, Theorem 5.5.2, p. 78.
  5. {{harvtxt. Dahlhaus. Manuel. Miller. 1998.
  6. {{harvtxt. Brandstädt. Dragan. Chepoi. Voloshin. 1998, Corollary 3, p. 444
  7. {{harvtxt. McKee. 1999
  8. {{harvtxt. De Caria. McKee. 2014
  9. {{harvtxt. Farber. 1983.
  10. {{harvtxt. Lubiw. 1987; {{harvtxt. Paige. Tarjan. 1987; {{harvtxt. Spinrad. 1993.
  11. {{harvtxt. Nishimura. Ragde. Thilikos. 2002
  12. {{harvtxt. Brandstädt. Hundt. Mancini. Wagner. 2010
  13. {{harvtxt. Uehara. Toda. Nagoya. 2005
  14. {{harvtxt. Müller. 1996
Wikipedia Source

This article was imported from Wikipedia and is available under the Creative Commons Attribution-ShareAlike 4.0 License. Content has been adapted to SurfDoc format. Original contributors can be found on the article history page.

graph-families perfect-graphs
Want to explore this topic further?

Ask Mako anything about Strongly chordal graph — get instant answers, deeper analysis, and related topics.

Research with Mako

Free with your Surf account

Content sourced from Wikipedia, available under CC BY-SA 4.0.

This content may have been generated or modified by AI. CloudSurf Software LLC is not responsible for the accuracy, completeness, or reliability of AI-generated content. Always verify important information from primary sources.

Report