Simplicial and nonsimplicial complete subgraphs

Terry A. McKee

Discussiones Mathematicae Graph Theory (2011)

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

Abstract

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

How to cite

top

Terry 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. [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. [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. [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. [4] R.E. Jamison, On the null-homotopy of bridged graphs, European J. Combin. 8 (1987) 421-428. Zbl0638.05033
  5. [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. [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. [7] T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory, Society for Industrial and Applied Mathematics (Philadelphia, 1999). Zbl0945.05003
  8. [8] E. Prisner, Hereditary clique-Helly graphs, J. Combin. Math. Combin. Comput. 14 (1993) 216-220. Zbl0794.05113
  9. [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 ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.