Strongly chordal graph
Encyclopedia
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.
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 six or more has a triangular chord, a triangle formed by a chord and two edges of the cycle.
Strongly chordal graphs may also be characterized in terms of the number of complete subgraphs
each edge participates in.
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.
Mathematics
Mathematics is the study of quantity, space, structure, and change. Mathematicians seek out patterns and formulate new conjectures. Mathematicians resolve the truth or falsity of conjectures by mathematical proofs, which are arguments sufficient to convince other mathematicians of their validity...
area of graph theory
Graph theory
In mathematics and computer science, graph theory is the study of graphs, mathematical structures used to model pairwise relations between objects from a certain collection. A "graph" in this context refers to a collection of vertices or 'nodes' and a collection of edges that connect pairs of...
, an undirected graph G is strongly chordal if it is a chordal graph
Chordal graph
In the mathematical area of graph theory, a graph is chordal if each of its cycles of four or more nodes has a chord, which is an edge joining two nodes that are not adjacent in the cycle. An equivalent definition is that any chordless cycles have at most three nodes...
and every cycle
Cycle (graph theory)
In graph theory, the term cycle may refer to a closed path. If repeated vertices are allowed, it is more often called a closed walk. If the path is a simple path, with no repeated vertices or edges other than the starting and ending vertices, it may also be called a simple cycle, circuit, circle,...
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
Clique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
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 six or more has a triangular chord, a triangle formed by a chord and two edges of the cycle.
Strongly chordal graphs may also be characterized in terms of the number of complete subgraphs
Clique (graph theory)
In the mathematical area of graph theory, a clique in an undirected graph is a subset of its vertices such that every two vertices in the subset are connected by an edge. Cliques are one of the basic concepts of graph theory and are used in many other mathematical problems and constructions on graphs...
each edge participates 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 for a graph with n vertices and m edges.