DMGT

Discussiones Mathematicae Graph Theory 31(3) (2011) 577-586
DOI: https://doi.org/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