Maxclique and Unit Disk Characterizations of Strongly Chordal Graphs

Pablo De Caria; Terry A. McKee

Discussiones Mathematicae Graph Theory (2014)

  • Volume: 34, Issue: 3, page 593-602
  • ISSN: 2083-5892

Abstract

top
Maxcliques (maximal complete subgraphs) and unit disks (closed neighborhoods of vertices) sometime play almost interchangeable roles in graph theory. For instance, interchanging them makes two existing characterizations of chordal graphs into two new characterizations. More intriguingly, these characterizations of chordal graphs can be naturally strengthened to new characterizations of strongly chordal graphs

How to cite

top

Pablo De Caria, and Terry A. McKee. "Maxclique and Unit Disk Characterizations of Strongly Chordal Graphs." Discussiones Mathematicae Graph Theory 34.3 (2014): 593-602. <http://eudml.org/doc/268169>.

@article{PabloDeCaria2014,
abstract = {Maxcliques (maximal complete subgraphs) and unit disks (closed neighborhoods of vertices) sometime play almost interchangeable roles in graph theory. For instance, interchanging them makes two existing characterizations of chordal graphs into two new characterizations. More intriguingly, these characterizations of chordal graphs can be naturally strengthened to new characterizations of strongly chordal graphs},
author = {Pablo De Caria, Terry A. McKee},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {chordal graph; strongly chordal graph; clique; maxclique; closed neighborhood},
language = {eng},
number = {3},
pages = {593-602},
title = {Maxclique and Unit Disk Characterizations of Strongly Chordal Graphs},
url = {http://eudml.org/doc/268169},
volume = {34},
year = {2014},
}

TY - JOUR
AU - Pablo De Caria
AU - Terry A. McKee
TI - Maxclique and Unit Disk Characterizations of Strongly Chordal Graphs
JO - Discussiones Mathematicae Graph Theory
PY - 2014
VL - 34
IS - 3
SP - 593
EP - 602
AB - Maxcliques (maximal complete subgraphs) and unit disks (closed neighborhoods of vertices) sometime play almost interchangeable roles in graph theory. For instance, interchanging them makes two existing characterizations of chordal graphs into two new characterizations. More intriguingly, these characterizations of chordal graphs can be naturally strengthened to new characterizations of strongly chordal graphs
LA - eng
KW - chordal graph; strongly chordal graph; clique; maxclique; closed neighborhood
UR - http://eudml.org/doc/268169
ER -

References

top
  1. [1] A. Brandstädt, F. Dragan, V. Chepoi, and V. Voloshin, Dually chordal graphs, SIAM J. Discrete Math. 11 (1998) 437-455. doi:10.1137/S0895480193253415[Crossref] Zbl0909.05037
  2. [2] A. Brandstädt, V.B. Le, and J.P. Spinrad, Graph Classes: A Survey (Society for Industrial and Applied Mathematics, Philadelphia, 1999). doi:10.1137/1.9780898719796[Crossref] 
  3. [3] P. De Caria and M. Gutierrez, On minimal vertex separators of dually chordal graphs: properties and characterizations, Discrete Appl. Math. 160 (2012) 2627-2635. doi:10.1016/j.dam.2012.02.022[WoS][Crossref] Zbl1259.05096
  4. [4] P. De Caria and M. Gutierrez, On the correspondence between tree representations of chordal and dually chordal graphs, Discrete Appl. Math. 164 (2014) 500-511. doi:10.1016/j.dam.2013.07.011[Crossref][WoS] Zbl1288.05052
  5. [5] M. Farber, Characterizations of strongly chordal graphs, Discrete Math. 43 (1983) 173-189. doi:10.1016/0012-365X(83)90154-1[Crossref] 
  6. [6] T.A. McKee, How chordal graphs work, Bull. Inst. Combin. Appl. 9 (1993) 27-39. Zbl0803.05034
  7. [7] T.A. McKee, A new characterization of strongly chordal graphs, Discrete Math. 205 (1999) 245-247. doi:10.1016/S0012-365X(99)00107-7[Crossref] 
  8. [8] T.A. McKee, Subgraph trees in graph theory, Discrete Math. 270 (2003) 3-12. doi:10.1016/S0012-365X(03)00161-4[Crossref] 
  9. [9] T.A. McKee, The neighborhood characteristic parameter for graphs, Electron. J. Combin. 10 (2003) #R20. Zbl1023.05118
  10. [10] T.A. McKee, When fundamental cycles span cliques, Congr. Numer. 191 (2008) 213-218. Zbl1168.05037
  11. [11] T.A. McKee, Simplicial and nonsimplicial complete subgraphs, Discuss. Math. Zbl1229.05237
  12. Graph Theory 31 (2011) 577-586. doi:10.7151/dmgt.1566[Crossref] 
  13. [12] T.A. McKee and F.R. McMorris, Topics in Intersection Graph Theory (Society for Industrial and Applied Mathematics, Philadelphia, 1999). doi:10.1137/1.9780898719802[Crossref] Zbl0945.05003
  14. [13] T.A. McKee and E. Prisner, An approach to graph-theoretic homology, Combinatorics, Graph Theory and Algorithms Y. Alavi, et al. Eds, New Issues Press, Kalamazoo, MI (1999) 2 631-640. 

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.