In the

mathematical Mathematics is an area of knowledge that includes the topics of numbers, formulas and related structures, shapes and the spaces in which they are contained, and quantities and their changes. These topics are represented in modern mathematics ...

area of

graph theory In mathematics, graph theory is the study of ''graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of '' vertices'' (also called ''nodes'' or ''points'') which are conne ...

, an

undirected graph In discrete mathematics, and more specifically in graph theory, a graph is a structure amounting to a set of objects in which some pairs of the objects are in some sense "related". The objects correspond to mathematical abstractions called '' v ...

is strongly chordal if it is a

chordal graph In the mathematical area of graph theory, a chordal graph is one in which all cycles of four or more vertices have a ''chord'', which is an edge that is not part of the cycle but connects two vertices of the cycle. Equivalently, every induced cy ...

and every cycle of even length (≥ 6) in has an ''odd chord'', i.e., an edge that connects two vertices that are an odd

distance Distance is a numerical or occasionally qualitative measurement of how far apart objects or points are. In physics or everyday usage, distance may refer to a physical length or an estimation based on other criteria (e.g. "two counties over"). ...

(>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 In the mathematical field of graph theory, an induced subgraph of a graph is another graph, formed from a subset of the vertices of the graph and ''all'' of the edges (from the original graph) connecting pairs of vertices in that subset. Defini ...

. An ''n''-sun is a chordal graph with 2''n'' vertices, partitioned into two subsets ''U'' = and ''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 A clique ( AusE, CanE, or ), in the social sciences, is a group of individuals who interact with one another and share similar interests. Interacting with cliques is part of normative social development regardless of gender, ethnicity, or popular ...

and such that, for each ''i'' < ''j'' < ''k'' < ''l'', if the ''i''th vertex in the ordering is adjacent to the ''k''th and the ''l''th vertices, and the ''j''th and ''k''th vertices are adjacent, then the ''j''th and ''l''th 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 In the mathematical area of graph theory, an undirected graph is dually chordal if the hypergraph of its maximal cliques is a hypertree. The name comes from the fact that a graph is chordal if and only if the hypergraph of its maximal cliques is ...

. 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 In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by ...

, 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 for a graph with ''n'' vertices and ''m'' edges.

Subclasses

An important subclass (based on

phylogeny A phylogenetic tree (also phylogeny or evolutionary tree Felsenstein J. (2004). ''Inferring Phylogenies'' Sinauer Associates: Sunderland, MA.) is a branching diagram or a tree showing the evolutionary relationships among various biological spec ...

) is the class of -

leaf power In the mathematical area of graph theory, a -leaf power of a tree is a graph whose vertices are the leaves of and whose edges connect pairs of leaves whose distance in is at most . That is, is an induced subgraph of the graph power , induce ...

s, 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 . A leaf power is a graph that is a -leaf power for some . 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 graph In graph theory, a branch of mathematics, a cluster graph is a graph formed from the disjoint union of complete graphs. Equivalently, a graph is a cluster graph if and only if it has no three-vertex induced path; for this reason, the cluster gra ...

s as the 2-leaf powers. Another important subclass of strongly chordal graphs are

interval graph In graph theory, an interval graph is an undirected graph formed from a set of intervals on the real line, with a vertex for each interval and an edge between vertices whose intervals intersect. It is the intersection graph of the intervals. Int ...

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

s and

s, 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 graph In graph theory, a branch of mathematics, a split graph is a graph in which the vertices can be partitioned into a clique and an independent set. Split graphs were first studied by , and independently introduced by . A split graph may have m ...

Notes

References

*. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *. *{{citation , last1 = Uehara , first1 = R. , last2 = Toda , first2 = S. , last3 = Nagoya , first3 = T. , year = 2005 , doi = 10.1016/j.dam.2004.06.008 , issue = 3 , journal =

Discrete Applied Mathematics ''Discrete Applied Mathematics'' is a peer-reviewed scientific journal covering algorithmic and applied areas of discrete mathematics. It is published by Elsevier and the editor-in-chief is Endre Boros (Rutgers University). The journal was split ...

, pages = 479–482 , title = Graph isomorphism completeness for chordal bipartite and strongly chordal graphs , volume = 145. Graph families Perfect graphs