×

Maxclique and unit disk characterizations of strongly chordal graphs. (English) Zbl 1305.05200

Summary: 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.

MSC:

05C75 Structural characterization of families of graphs
PDFBibTeX XMLCite
Full Text: DOI

References:

[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; · 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; · Zbl 0919.05001
[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; · 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; · 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;
[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; · Zbl 0942.05060
[8] T.A. McKee, Subgraph trees in graph theory, Discrete Math. 270 (2003) 3-12. doi:10.1016/S0012-365X(03)00161-4; · Zbl 1023.05033
[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
[12] Graph Theory 31 (2011) 577-586. doi:10.7151/dmgt.1566;
[13] 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; · Zbl 0945.05003
[14] 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.;
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.