In the

mathematical Mathematics is a field of study that discovers and organizes methods, Mathematical theory, theories and theorems that are developed and Mathematical proof, proved for the needs of empirical sciences and mathematics itself. There are many ar ...

area of

graph theory In mathematics and computer science, graph theory is the study of ''graph (discrete mathematics), graphs'', which are mathematical structures used to model pairwise relations between objects. A graph in this context is made up of ''Vertex (graph ...

, an

undirected graph In discrete mathematics, particularly in graph theory, a graph is a structure consisting of a set of objects where some pairs of the objects are in some sense "related". The objects are represented by abstractions called '' vertices'' (also call ...

is dually chordal if the

hypergraph In mathematics, a hypergraph is a generalization of a Graph (discrete mathematics), graph in which an graph theory, edge can join any number of vertex (graph theory), vertices. In contrast, in an ordinary graph, an edge connects exactly two vert ...

of its

maximal clique In 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 complete. Cliques are one of t ...

s 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 Dual or Duals may refer to: Paired/two things * Dual (mathematics), a notion of paired concepts that mirror one another ** Dual (category theory), a formalization of mathematical duality *** see more cases in :Duality theories * Dual number, a nu ...

of a hypertree. Originally, these graphs were defined by maximum

neighborhood A neighbourhood (Commonwealth English) or neighborhood (American English) is a geographically localized community within a larger town, city, suburb or rural area, sometimes consisting of a single street and the buildings lining it. Neigh ...

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 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. Definition Formally, let G=(V,E) ...

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

strongly chordal graph In the mathematics, mathematical area of graph theory, an undirected graph is strongly chordal if it is a chordal graph and every cycle (graph theory), cycle of even length (≥ 6) in has an ''odd chord'', i.e., an edge that connects two Vertex ...

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

perfect graph In graph theory, a perfect graph is a Graph (discrete mathematics), graph in which the Graph coloring, chromatic number equals the size of the maximum clique, both in the graph itself and in every induced subgraph. In all graphs, the chromatic nu ...

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

s of chordal graphs, 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 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 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 small group of individuals who interact with one another and share similar interests rather than include others. Interacting with cliques is part of normative social development regardles ...

, coloring and

clique cover In graph theory, a clique cover or partition into cliques of a given undirected graph is a collection of cliques that cover the whole graph. A minimum clique cover is a clique cover that uses as few cliques as possible. The minimum for which a cl ...

remain

NP-complete In computational complexity theory, NP-complete problems are the hardest of the problems to which ''solutions'' can be verified ''quickly''. Somewhat more precisely, a problem is NP-complete when: # It is a decision problem, meaning that for any ...

for dually chordal graphs, some variants of the minimum

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

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 and efficient edge domination on dually chordal graphs.

Notes

References

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