# Simplicial and nonsimplicial complete subgraphs

Discussiones Mathematicae Graph Theory (2011)

- Volume: 31, Issue: 3, page 577-586
- ISSN: 2083-5892

## Access Full Article

top## Abstract

top## How to cite

topTerry A. McKee. "Simplicial and nonsimplicial complete subgraphs." Discussiones Mathematicae Graph Theory 31.3 (2011): 577-586. <http://eudml.org/doc/271014>.

@article{TerryA2011,

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

author = {Terry A. McKee},

journal = {Discussiones Mathematicae Graph Theory},

keywords = {simplicial clique; strongly chordal graph; trivially perfect graph; hereditary clique-Helly graph; strong p-Helly graph; strong -Helly graph},

language = {eng},

number = {3},

pages = {577-586},

title = {Simplicial and nonsimplicial complete subgraphs},

url = {http://eudml.org/doc/271014},

volume = {31},

year = {2011},

}

TY - JOUR

AU - Terry A. McKee

TI - Simplicial and nonsimplicial complete subgraphs

JO - Discussiones Mathematicae Graph Theory

PY - 2011

VL - 31

IS - 3

SP - 577

EP - 586

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

LA - eng

KW - simplicial clique; strongly chordal graph; trivially perfect graph; hereditary clique-Helly graph; strong p-Helly graph; strong -Helly graph

UR - http://eudml.org/doc/271014

ER -

## References

top- [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. Zbl0919.05001
- [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. Zbl1140.05046
- [3] M. Farber, Characterizations of strongly chordal graphs, Discrete Math. 43 (1983) 173-189, doi: 10.1016/0012-365X(83)90154-1. Zbl0514.05048
- [4] R.E. Jamison, On the null-homotopy of bridged graphs, European J. Combin. 8 (1987) 421-428. Zbl0638.05033
- [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. Zbl1070.05056
- [7] T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory, Society for Industrial and Applied Mathematics (Philadelphia, 1999). Zbl0945.05003
- [8] E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput. 14 (1993) 216-220. Zbl0794.05113
- [9] W.D. Wallis and G.-H. Zhang, On maximal clique irreducible graphs, J. Combin. Math. Combin. Comput. 8 (1993) 187-193. Zbl0735.05052

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.