Characterizing Atoms that Result from Decomposition by Clique Separators

• Autorzy: Terry A. McKee
• Języki publikacji: EN

Abstrakty

EN

A graph is defined to be an atom if no minimal vertex separator induces a complete subgraph; thus, atoms are the graphs that are immune to clique separator decomposition. Atoms are characterized here in two ways: first using generalized vertex elimination schemes, and then as generalizations of 2-connected unichord-free graphs (the graphs in which every minimal vertex separator induces an edgeless subgraph).

Słowa kluczowe

EN

clique separator; minimal separator; unichord-free graph

Kategorie tematyczne

• 05C75: Structural characterization of families of graphs
• 05C69: Dominating sets, independent sets, cliques
• 05C40: Connectivity

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 37
• Numer: 3
• Strony: 587-594

Daty

wydano

2017-08-01

otrzymano

2016-01-14

poprawiono

2016-05-26

zaakceptowano

2016-05-26

online

2017-07-06

Twórcy

autor

Terry A. McKee

• , , , Ohio

Identyfikatory

DOI

10.7151/dmgt.1944