# 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

## Access Full Article

top## Abstract

top## How to cite

topPablo 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] 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] 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] 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] 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] M. Farber, Characterizations of strongly chordal graphs, Discrete Math. 43 (1983) 173-189. doi:10.1016/0012-365X(83)90154-1[Crossref]
- [6] T.A. McKee, How chordal graphs work, Bull. Inst. Combin. Appl. 9 (1993) 27-39. Zbl0803.05034
- [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] T.A. McKee, Subgraph trees in graph theory, Discrete Math. 270 (2003) 3-12. doi:10.1016/S0012-365X(03)00161-4[Crossref]
- [9] T.A. McKee, The neighborhood characteristic parameter for graphs, Electron. J. Combin. 10 (2003) #R20. Zbl1023.05118
- [10] T.A. McKee, When fundamental cycles span cliques, Congr. Numer. 191 (2008) 213-218. Zbl1168.05037
- [11] T.A. McKee, Simplicial and nonsimplicial complete subgraphs, Discuss. Math. Zbl1229.05237
- Graph Theory 31 (2011) 577-586. doi:10.7151/dmgt.1566[Crossref]
- [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
- [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.