w
GT 31/3
Discussiones Mathematicae Graph Theory 31(3) (2011)
577-586

doi: 10.7151/dmgt.1566

## Simplicial and Nonsimplicial Complete Subgraphs

Terry A. McKee
Department of Mathematics *&* Statistics Wright State University Dayton, Ohio 45435, USA |

## Abstract

Define a complete subgraph Q to be simplicial in a graph G when Q is
contained in exactly one maximal complete subgraph (`maxclique') of G;
otherwise, Q is nonsimplicial. Several graph classes-including strong
p-Helly graphs and strongly chordal graphs-are shown to have pairs of
peculiarly related new characterizations: (i) for every k ≤ 2,
a certain property holds for the complete subgraphs that are in k or more
maxcliques of G, and (ii) in every induced subgraph H of G,
that same property holds for the nonsimplicial complete subgraphs of H.
One example: G is shown to be hereditary clique-Helly if and only if,
for every k ≤ 2, every triangle whose edges are each in k or more
maxcliques is itself in k or more maxcliques; equivalently, in every
induced subgraph H of G, if each edge of a triangle is nonsimplicial
in H, then the triangle itself is nonsimplicial in H.

**Keywords:** simplicial clique, strongly chordal graph, trivially perfect graph, hereditary clique-Helly graph, strong p-Helly graph

**2010 Mathematics Subject Classification:** 05C75 (05C69).

## References

[1] | A. Brandstadt, V.B. Le and J.P. Spinrad, Graph Classes: A Survey, Society for Industrial and Applied Mathematics (Philadelphia, 1999), doi: 10.1137/1.9780898719796. |

[2] | M.C. Dourado, F. Protti and J.L. Szwarcfiter, * On the strong **p*-Helly property, Discrete Appl. Math. ** 156** (2008) 1053--1057, doi: 10.1016/j.dam.2007.05.047. |

[3] | M. Farber, * Characterizations of strongly chordal graphs*, Discrete Math. ** 43** (1983) 173--189, doi: 10.1016/0012-365X(83)90154-1. |

[4] | R.E. Jamison, * On the null-homotopy of bridged graphs*, European J. Combin. ** 8** (1987) 421--428. |

[5] | T.A. McKee, * A new characterization of strongly chordal graphs*, Discrete Math. ** 205** (1999) 245--247, doi: 10.1016/S0012-365X(99)00107-7. |

[6] | T.A. McKee, * Requiring chords in cycles*, Discrete Math. ** 297** (2005) 182--189, doi: 10.1016/j.disc.2005.04.009. |

[7] | T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory, Society for Industrial and Applied Mathematics (Philadelphia, 1999). |

[8] | E. Prisner, * Hereditary clique-Helly graphs*, J. Combin. Math. Combin. Comput. ** 14** (1993) 216--220. |

Received 30 March 2010

Accepted 2 September 2010