Maxclique and Unit Disk Characterizations of Strongly Chordal Graphs
Pablo De Caria ; Terry A. McKee
Discussiones Mathematicae Graph Theory, Tome 34 (2014), p. 593-602 / Harvested from The Polish Digital Mathematics Library
Access to full text
Full (PDF)

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

Publié le : 2014-01-01
EUDML-ID : urn:eudml:doc:268169 
@article{bwmeta1.element.doi-10_7151_dmgt_1757,
     author = {Pablo De Caria and Terry A. McKee},
     title = {Maxclique and Unit Disk Characterizations of Strongly Chordal Graphs},
     journal = {Discussiones Mathematicae Graph Theory},
     volume = {34},
     year = {2014},
     pages = {593-602},
     zbl = {1305.05200},
     language = {en},
     url = {http://dml.mathdoc.fr/item/bwmeta1.element.doi-10_7151_dmgt_1757}
}

Pablo De Caria; Terry A. McKee. Maxclique and Unit Disk Characterizations of Strongly Chordal Graphs. Discussiones Mathematicae Graph Theory, Tome 34 (2014) pp. 593-602. http://gdmltest.u-ga.fr/item/bwmeta1.element.doi-10_7151_dmgt_1757/

[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] | Zbl 0909.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] | Zbl 1259.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] | Zbl 1288.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. | Zbl 0803.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. | Zbl 1023.05118

[10] T.A. McKee, When fundamental cycles span cliques, Congr. Numer. 191 (2008) 213-218. | Zbl 1168.05037

[11] T.A. McKee, Simplicial and nonsimplicial complete subgraphs, Discuss. Math. | Zbl 1229.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] | Zbl 0945.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.