ArticleslgStudy

science

Strongly chordal graph

Strongly chordal graph is a science topic covered in the lgStudy science library. This page brings together a partial reference excerpt, illustrations, worked examples, real-world applications and a short study plan, so you can understand Strongly chordal graph rather than just read about it. In short: 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 leng…

Strongly chordal graph — main illustration
Strongly chordal graph — illustration

Key takeaways

  • Strongly chordal graph belongs to science; place it in that map before memorising details.
  • Learn the definition first, then one example that makes the definition concrete.
  • Connect Strongly chordal graph to a quantity you can measure, compute or draw — that is where exam questions come from.
  • Reproduce the core statement of Strongly chordal graph from memory before moving on to harder problems.

Reference excerpt

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, ui 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 < 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. 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 Brandstädt, Andreas; Dragan, Feodor; Chepoi, Victor; Voloshin, Vitaly (1998), "Dually Chordal Graphs", SIAM Journal on Discrete Mathematics, 11 (3): 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 (4): 897–910, doi:10.1016/j.disc.2009.10.006. Brandstädt, Andreas; Le, Van Bang (2006), "Structure and linear time recognition of 3-leaf powers", Information Processing Letters, 98 (4): 133–138, doi:10.1016/j.ipl.2006.01.004. Brandstädt, Andreas; Le, Van Bang; Sritharan, R. (2008), "Structure and linear time recognition of 4-leaf powers", ACM Transactions on Algorithms, 5 11, doi:10.1145/1435375.1435386, S2CID 6114466. 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 (3): 593–602, doi:10.7151/dmgt.1757, hdl:11336/32705. 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 (1–3): 291–298, doi:10.1016/0012-365x(95)00057-4. Nishimura, N.; Ragde, P.; Thilikos, D.M. (2002), "On graph powers for leaf-labeled trees", Journal of Algorithms, 42: 69–108, doi:10.1006/jagm.2001.1195. Paige, R.; Tarjan, R. E. (1987), "Three partition refinement algorithms", SIAM Journal on Computing, 16 (6): 973–989, doi:10.1137/0216062, S2CID 33265037. Rautenbach, D. (2006), "Some remarks about leaf roots", Discrete Mathematics, 306 (13): 1456–1461, doi:10.1016/j.disc.2006.03.030. 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, hdl:10119/4896.

Illustrations

Strongly chordal graph: 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 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.

Worked examples

Example 1 — a first encounter with Strongly chordal graph

Start with the simplest possible case. Write down what Strongly chordal graph claims or describes in one sentence, then invent the smallest concrete situation in which that sentence is true. In science, the smallest case is usually a single object, a single equation or a single measurement. Check that every symbol or term in your sentence has a meaning in that case.

Example 2 — changing one variable

Take the situation from Example 1 and change exactly one quantity: double it, halve it, or set it to zero. Predict what should happen to Strongly chordal graph before you calculate. Comparing your prediction with the result is the fastest way to find out whether you understand the idea or only the words.

Example 3 — an exam-style question

Typical questions about Strongly chordal graph ask you to (a) state it precisely, (b) apply it to given data, and (c) explain a limitation. Practise writing all three answers in under five minutes; the third part is what separates a full-mark answer from an average one.

Applications of Strongly chordal graph

In research
Strongly chordal graph appears in science research whenever the underlying quantities have to be modelled precisely. Papers usually cite it as a starting assumption and then explore where it breaks down.
In technology and industry
Engineering practice reuses Strongly chordal graph in design rules, simulations and safety margins. Knowing the idea lets you read a specification sheet and understand why the numbers look the way they do.
In the classroom
Strongly chordal graph is common in secondary-school and first-year university syllabi. It links to neighbouring topics Graph families, Perfect graphs, so understanding it makes those chapters shorter.
In everyday life
Look for Strongly chordal graph outside the textbook — in sport, cooking, traffic, electronics or the sky above you. An example you found yourself is remembered far longer than one you were given.
Ask Teacher Smith questions about this articleOpens your AI tutor with a question about “Strongly chordal graph” →

Affiliate

Preply — study more efficiently by working with a personal tutor. 50% off.

How to study Strongly chordal graph in 20 minutes

  1. Read the reference excerpt below once, without taking notes.
  2. Close the page and write down what Strongly chordal graph means in your own words.
  3. Compare your version with the excerpt and mark what you missed.
  4. Work through the three examples above with pen and paper.
  5. Explain Strongly chordal graph out loud to somebody else — or to Teacher Smith in the lgStudy chat.

Frequently asked questions

What is Strongly chordal graph in simple terms?

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 Stron…

Why does Strongly chordal graph matter?

Because it connects several science ideas at once: it gives you a definition you can apply, a quantity you can calculate, and a way to check whether a result is plausible.

How should I study Strongly chordal graph?

Read the excerpt, restate it from memory, then work through the examples and applications listed on this page. The five-step study plan above takes about twenty minutes.

What does this page cover?

It gives you a compact reference excerpt plus original lgStudy explanations, examples, applications and study material on Strongly chordal graph.

Tags

  • Graph families
  • Perfect graphs

Keep exploring