Dually chordal graph

Last updated January 16, 2024

In the mathematical area of graph theory, an undirected graph $G$ 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 the dual of a hypertree. Originally, these graphs were defined by maximum neighborhood orderings and have a variety of different characterizations.^[1] Unlike for chordal graphs, the property of being dually chordal is not hereditary, i.e., induced subgraphs of a dually chordal graph are not necessarily dually chordal (hereditarily dually chordal graphs are exactly the strongly chordal graphs), and a dually chordal graph is in general not a perfect graph.

Characterizations

Dually chordal graphs are the clique graphs of chordal graphs,^[3] i.e., the intersection graphs of maximal cliques of chordal graphs.

The following properties are equivalent:^[4]

G has a maximum neighborhood ordering.
There is a spanning tree T of G such that any maximal clique of G induces a subtree in T.
The closed neighborhood hypergraph N(G) of G is a hypertree.
The maximal clique hypergraph of G is a hypertree.
G is the 2-section graph of a hypertree.

The condition on the closed neighborhood hypergraph also implies that a graph is dually chordal if and only if its square is chordal and its closed neighborhood hypergraph has the Helly property.

In De Caria & Gutierrez (2012) dually chordal graphs are characterized in terms of separator properties. In Brešar (2003) it was shown that dually chordal graphs are precisely the intersection graphs of maximal hypercubes of graphs of acyclic cubical complexes.

The structure and algorithmic use of doubly chordal graphs is given by Moscarini (1993). These are graphs which are chordal and dually chordal.

Recognition

Dually chordal graphs can be recognized in linear time, and a maximum neighborhood ordering of a dually chordal graph can be found in linear time.^[5]

Complexity of problems

While some basic problems such as maximum independent set, maximum clique, coloring and clique cover remain NP-complete for dually chordal graphs, some variants of the minimum dominating set problem and Steiner tree are efficiently solvable on dually chordal graphs (but Independent Domination remains NP-complete).^[6] See Brandstädt, Chepoi & Dragan (1999) for the use of dually chordal graph properties for tree spanners, and see Brandstädt, Leitert & Rautenbach (2012) for a linear time algorithm of efficient domination and efficient edge domination on dually chordal graphs.

Related Research Articles

In computer science, the clique problem is the computational problem of finding cliques in a graph. It has several different formulations depending on which cliques, and what information about the cliques, should be found. Common formulations of the clique problem include finding a maximum clique, finding a maximum weight clique in a weighted graph, listing all maximal cliques, and solving the decision problem of testing whether a graph contains a clique larger than a given size.

In graph theory, an outerplanar graph is a graph that has a planar drawing for which all vertices belong to the outer face of the drawing.

<span class="mw-page-title-main">Chordal graph</span> Graph where all long cycles have a chord

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 cycle in the graph should have exactly three vertices. The chordal graphs may also be characterized as the graphs that have perfect elimination orderings, as the graphs in which each minimal separator is a clique, and as the intersection graphs of subtrees of a tree. They are sometimes also called rigid circuit graphs or triangulated graphs.

In graph theory, a cograph, or complement-reducible graph, or P₄-free graph, is a graph that can be generated from the single-vertex graph K₁ by complementation and disjoint union. That is, the family of cographs is the smallest class of graphs that includes K₁ and is closed under complementation and disjoint union.

In graph theory, a circle graph is the intersection graph of a chord diagram. That is, it is an undirected graph whose vertices can be associated with a finite system of chords of a circle such that two vertices are adjacent if and only if the corresponding chords cross each other.

In graph theory, a clique graph of an undirected graph $G$ is another graph $K (G)$ that represents the structure of cliques in $G$ .

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 Földes and Hammer, and independently introduced by Tyshkevich and Chernyak (1979), where they called these graphs "polar graphs".

In graph theory, the clique-width of a graph $G$ is a parameter that describes the structural complexity of the graph; it is closely related to treewidth, but unlike treewidth it can be small for dense graphs. It is defined as the minimum number of labels needed to construct $G$ by means of the following 4 operations :

Creation of a new vertex $v$ with label $i$ (denoted by $i (v)$ )
Disjoint union of two labeled graphs $G$ and $H$ (denoted by $)$
Joining by an edge every vertex labeled $i$ to every vertex labeled $j$ (denoted by $η (i, j)$ ), where $i \neq j$
Renaming label $i$ to label $j$ (denoted by $ρ (i, j)$ )

In graph theory, a division of mathematics, a median graph is an undirected graph in which every three vertices a, b, and c have a unique median: a vertex m(a,b,c) that belongs to shortest paths between each pair of a, b, and c.

In graph theory, a branch of discrete mathematics, a distance-hereditary graph is a graph in which the distances in any connected induced subgraph are the same as they are in the original graph. Thus, any induced subgraph inherits the distances of the larger graph.

In the mathematical field of graph theory, a permutation graph is a graph whose vertices represent the elements of a permutation, and whose edges represent pairs of elements that are reversed by the permutation. Permutation graphs may also be defined geometrically, as the intersection graphs of line segments whose endpoints lie on two parallel lines. Different permutations may give rise to the same permutation graph; a given graph has a unique representation if it is prime with respect to the modular decomposition.

In graph theory, a trivially perfect graph is a graph with the property that in each of its induced subgraphs the size of the maximum independent set equals the number of maximal cliques. Trivially perfect graphs were first studied by but were named by Golumbic (1978); Golumbic writes that "the name was chosen since it is trivial to show that such a graph is perfect." Trivially perfect graphs are also known as comparability graphs of trees, arborescent comparability graphs, and quasi-threshold graphs.

<span class="mw-page-title-main">Hypertree</span> Generalization of tree graphs to hypergraphs

In the mathematical field of graph theory, a hypergraph $H$ is called a hypertree if it admits a host graph $T$ such that $T$ is a tree. In other words, $H$ is a hypertree if there exists a tree $T$ such that every hyperedge of $H$ is the set of vertices of a connected subtree of $T$ . Hypertrees have also been called arboreal hypergraphs or tree hypergraphs.

<span class="mw-page-title-main">Squaregraph</span> Planar graph with quadrilateral faces

In graph theory, a branch of mathematics, a squaregraph is a type of undirected graph that can be drawn in the plane in such a way that every bounded face is a quadrilateral and every vertex with three or fewer neighbors is incident to an unbounded face.

In graph theory, a perfectly orderable graph is a graph whose vertices can be ordered in such a way that a greedy coloring algorithm with that ordering optimally colors every induced subgraph of the given graph. Perfectly orderable graphs form a special case of the perfect graphs, and they include the chordal graphs, comparability graphs, and distance-hereditary graphs. However, testing whether a graph is perfectly orderable is NP-complete.

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

In graph theory, a branch of mathematics, an indifference graph is an undirected graph constructed by assigning a real number to each vertex and connecting two vertices by an edge when their numbers are within one unit of each other. Indifference graphs are also the intersection graphs of sets of unit intervals, or of properly nested intervals. Based on these two types of interval representations, these graphs are also called unit interval graphs or proper interval graphs; they form a subclass of the interval graphs.

In the mathematical area of graph theory, a chordal bipartite graph is a bipartite graph B = (X,Y,E) in which every cycle of length at least 6 in B has a chord, i.e., an edge that connects two vertices that are a distance > 1 apart from each other in the cycle. A better name would be weakly chordal and bipartite since chordal bipartite graphs are in general not chordal as the induced cycle of length 4 shows.

Andreas Brandstädt is a German mathematician and computer scientist.

In the mathematical area of graph theory, a $k$ -leaf power of a tree $T$ is a graph $G$ whose vertices are the leaves of $T$ and whose edges connect pairs of leaves whose distance in $T$ is at most $k$ . That is, $G$ is an induced subgraph of the graph power , induced by the leaves of $T$ . For a graph $G$ constructed in this way, $T$ is called a $k$ -leaf root of $G$ .

References

Brandstädt, Andreas; Chepoi, Victor; Dragan, Feodor (1998), "The algorithmic use of hypertree structure and maximum neighborhood orderings", Discrete Applied Mathematics , 82 (1–3): 43–77, doi: 10.1016/s0166-218x(97)00125-x .
Brandstädt, Andreas; Chepoi, Victor; Dragan, Feodor (1999), "Distance approximating trees for chordal and dually chordal graphs", Journal of Algorithms , 30: 166–184, doi:10.1006/jagm.1998.0962 .
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, MR 1628114 .
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 .
Brandstädt, Andreas; Leitert, Arne; Rautenbach, Dieter (2012), "Efficient dominating and edge dominating sets for graphs and hypergraphs", in Chao, Kun-Mao; Hsu, Tsan-sheng; Lee, Der-Tsai (eds.), Algorithms and Computation – 23rd International Symposium, ISAAC 2012, Taipei, Taiwan, December 19–21, 2012. Proceedings, Lecture Notes in Computer Science, vol. 7676, Springer, pp. 267–277, arXiv: 1207.0953 , doi:10.1007/978-3-642-35261-4_30 .
Brešar, Boštjan (2003), "Intersection graphs of maximal hypercubes", European Journal of Combinatorics , 24 (2): 195–209, doi: 10.1016/s0195-6698(02)00142-7 .
De Caria, Pablo; Gutierrez, Marisa (2012), "On Minimal Vertex Separators of Dually Chordal Graphs: Properties and Characterizations", Discrete Applied Mathematics , 160 (18): 2627–2635, doi: 10.1016/j.dam.2012.02.022 , hdl: 11336/190841 .
Dragan, Feodor (1989), Centers of Graphs and the Helly Property (in Russian), Ph.D. thesis, Moldova State University, Moldova.
Dragan, Feodor; Prisacaru, Chiril; Chepoi, Victor (1992), "Location problems in graphs and the Helly property (in Russian)", Discrete Math. (Moscow) , 4: 67–73.
Dragan, Feodor (1993), "HT-graphs: centers, connected r-domination and Steiner trees", Comput. Sci. J. of Moldova (Kishinev) , 1: 64–83.
Gutierrez, Marisa; Oubina, L. (1996), "Metric Characterizations of proper Interval Graphs and Tree-Clique Graphs", Journal of Graph Theory , 21 (2): 199–205, doi:10.1002/(sici)1097-0118(199602)21:2<199::aid-jgt9>3.0.co;2-m .
McKee, Terry A.; McMorris, FR. (1999), Topics in Intersection Graph Theory, SIAM Monographs on Discrete Mathematics and Applications.
Moscarini, Marina (1993), "Doubly Chordal Graphs, Steiner trees and connected domination", Networks, 23: 59–69, doi:10.1002/net.3230230108 .
Szwarcfiter, Jayme L.; Bornstein, Claudson F. (1994), "Clique Graphs of Chordal and Path Graphs", SIAM Journal on Discrete Mathematics , 7 (2): 331–336, CiteSeerX 10.1.1.52.521 , doi:10.1137/s0895480191223191 .

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.

[1] Brandstädt et al. (1998); Brandstädt, Le & Spinrad (1999)

[2] Dragan (1989); Dragan, Prisacaru & Chepoi (1992); Dragan (1993)

[3] Gutierrez & Oubina (1996); Szwarcfiter & Bornstein (1994)

[4] Brandstädt, Chepoi & Dragan (1998);Brandstädt et al. (1998); Dragan, Prisacaru & Chepoi (1992); Dragan (1993)

[5] Brandstädt, Chepoi & Dragan (1998);Dragan (1989)

[6] Brandstädt, Chepoi & Dragan (1998); Dragan, Prisacaru & Chepoi (1992); Dragan (1993)

[1]

[2]

[3]

[4]

[5]

[6]