Determinant families for dually chordal graphs

PABLO DE CARIA

Río de Janeiro

Congreso; VIII Latin American Workshop on cliques in Graphs; 2018

A graph is dually chordal if it is the clique graph of some chordal graph.One characterization of dually chordal graphs is by means of the compatibletree. A spanning tree T of a graph G is a compatible tree if every maximalclique of G induces a subtree of T. A graph is dually chordal if and only ifit has a compatible tree.It is not difficult to see that compatible trees can also be characterizedas those spanning trees for which every closed neighborhood of the graphinduces a subtree.The goal of this presentation is a generalization of the previous propertiesby the introduction of the concept of determinant families. Given a duallychordal graph G and a family F of subsets of V(G), we say that F is determinant if the compatible trees of G are just those spanning trees for whichevery F ∈ F induces a subtree of T.We find conditions to decide whether a family is determinant and weobserve that some determinant families are stronger in the sense that thecondition that T is a spanning tree in the definition can be dropped.Finally, we apply this theory to generalize some characterizations of duallychordal graphs, like the ones that involve maximum weight spanning treesand the one that says that a graph G is dually chordal if and only if G isclique-Helly and K(G) is chordal.