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 dually chordal if the

hypergraph In mathematics, a hypergraph is a generalization of a graph in which an edge can join any number of vertices. In contrast, in an ordinary graph, an edge connects exactly two vertices. Formally, an undirected hypergraph H is a pair H = (X,E) wh ...

of its

maximal clique In the mathematical area of graph theory, a clique ( or ) is a subset of vertices of an undirected graph such that every two distinct vertices in the clique are adjacent. That is, a clique of a graph G is an induced subgraph of G that is comple ...

s is a

hypertree In the mathematical field of graph theory, a hypergraph is called a hypertree if it admits a host graph such that is a tree (graph theory), tree. In other words, is a hypertree if there exists a tree such that every hyperedge of is the set ...

. 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 A neighbourhood (British English, Irish English, Australian English and Canadian English) or neighborhood (American English; see spelling differences) is a geographically localised community within a larger city, town, suburb or rural area, ...

orderings and have a variety of different characterizations. Unlike for chordal graphs, the property of being dually chordal is not hereditary, i.e.,

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

s of a dually chordal graph are not necessarily dually chordal (hereditarily dually chordal graphs are exactly the

strongly chordal graph In the mathematical area of graph theory, an undirected graph is strongly chordal if it is a chordal graph 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 (>1) a ...

s), and a dually chordal graph is in general not a

perfect graph In graph theory, a perfect graph is a graph in which the chromatic number of every induced subgraph equals the order of the largest clique of that subgraph (clique number). Equivalently stated in symbolic terms an arbitrary graph G=(V,E) is perfec ...

. Dually chordal graphs appeared first under the name HT-graphs.

Characterizations

Dually chordal graphs are the

clique graph In graph theory, a clique graph of an undirected graph is another graph that represents the structure of cliques in . Clique graphs were discussed at least as early as 1968, and a characterization of clique graphs was given in 1971. Formal d ...

s of

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

s, i.e., the intersection graphs of maximal cliques of chordal graphs. The following properties are equivalent: *''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

. *The maximal clique hypergraph of ''G'' is a

. *''G'' is the 2-section graph of a

. 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 dually chordal graphs are characterized in terms of separator properties. In 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 . 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.

Complexity of problems

While some basic problems such as maximum independent set, maximum

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

, coloring and

clique cover In graph theory, a clique cover or partition into cliques of a given undirected graph is a partition of the vertices into cliques, subsets of vertices within which every two vertices are adjacent. A minimum clique cover is a clique cover that us ...

remain

NP-complete In computational complexity theory, a problem is NP-complete when: # it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryi ...

for dually chordal graphs, some variants of the minimum

dominating set In graph theory, a dominating set for a graph is a subset of its vertices, such that any vertex of is either in , or has a neighbor in . The domination number is the number of vertices in a smallest dominating set for . The dominating set ...

problem and

Steiner tree In combinatorial mathematics, the Steiner tree problem, or minimum Steiner tree problem, named after Jakob Steiner, is an umbrella term for a class of problems in combinatorial optimization. While Steiner tree problems may be formulated in a n ...

are efficiently solvable on dually chordal graphs (but Independent Domination remains

).; ; See for the use of dually chordal graph properties for tree spanners, and see for a linear time algorithm of

efficient domination Efficiency is the extent to which time or effort is well used for the intended task or purpose. Efficiency may also refer to: * Efficiency (aerodynamics), the amount of lift divided by the aerodynamic drag * Efficiency (apartment), a one-room ...

and

efficient edge domination Efficiency is the extent to which time or effort is well used for the intended task or purpose. Efficiency may also refer to: * Efficiency (aerodynamics), the amount of lift divided by the aerodynamic drag * Efficiency (apartment), a one-room ...

on dually chordal graphs.

Notes

References

*. *. *. *. *. *. *. *. *. *. *. *. *. *. *. {{refend Graph families Perfect graphs