Requiring that Minimal Separators Induce Complete Multipartite Subgraphs

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

Abstrakty

EN

Complete multipartite graphs range from complete graphs (with every partite set a singleton) to edgeless graphs (with a unique partite set). Requiring minimal separators to all induce one or the other of these extremes characterizes, respectively, the classical chordal graphs and the emergent unichord-free graphs. New theorems characterize several subclasses of the graphs whose minimal separators induce complete multipartite subgraphs, in particular the graphs that are 2-clique sums of complete, cycle, wheel, and octahedron graphs.

Słowa kluczowe

EN

minimal separator; complete multipartite graph; chordal graph; unichord-free graph

Kategorie tematyczne

• 05C62: Graph representations (geometric and intersection representations, etc.) {For graph drawing, see also }
• 05C75: Structural characterization of families of graphs
• 05C69: Dominating sets, independent sets, cliques

• Wydawca: De Gruyter Open
• Czasopismo: Discussiones Mathematicae Graph Theory
• Rocznik: 2017
• Tom: 38
• Numer: 1
• Strony: 263-273

Daty

wydano

2018-02-01

otrzymano

2016-06-28

poprawiono

2016-11-09

zaakceptowano

2016-11-09

online

2017-12-30

Twórcy

autor

Terry A. McKee

• , , , Ohio USA,

Identyfikatory

DOI

10.7151/dmgt.1988