Maxclique and Unit Disk Characterizations of Strongly Chordal Graphs

• Autorzy: Pablo De Caria , Terry A. McKee
• Języki publikacji: EN

Abstrakty

EN

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

Słowa kluczowe

EN

chordal graph; strongly chordal graph; clique; maxclique; closed neighborhood

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2014
• Tom: 34
• Numer: 3
• Strony: 593-602

Daty

wydano

2014-08-01

otrzymano

2012-01-06

poprawiono

2013-04-15

zaakceptowano

2013-08-22

online

2014-07-16

Twórcy

autor

Pablo De Caria

• Departamento de Matemática Universidad Nacional de La Plata/ CONICET La Plata, Buenos Aires, Argentina,

autor

Terry A. McKee

• Department of Mathematics and Statistics Wright State University Dayton, Ohio 45435 USA,

Bibliografia

• [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]
• [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]
• [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]
• [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.
• [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.
• [10] T.A. McKee, When fundamental cycles span cliques, Congr. Numer. 191 (2008) 213-218.
• [11] T.A. McKee, Simplicial and nonsimplicial complete subgraphs, Discuss. Math.
• 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]
• [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.

Identyfikatory

DOI

10.7151/dmgt.1757