No Access

WHEN ALL MINIMAL VERTEX SEPARATORS INDUCE COMPLETE OR EDGELESS SUBGRAPHS

TERRY A. McKEE

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

https://doi.org/10.1142/S1793830913500158Cited by:0 (Source: Crossref)

Abstract

The graphs in which every minimal vertex separator induces a complete or an edgeless subgraph are shown to be the edge sums of graphs of the two extreme types: (i) when every minimal vertex separator induces a complete subgraph — these are precisely the well-studied chordal graphs — and (ii) when every minimal vertex separator induces an edgeless subgraph — these have appeared in several recent papers.

Keywords:

AMSC: 05C75, 05C40

References

A. Brandstädt , V.-B. Le and J. P. Spinrad , Graph Classes; A Survey ( Society for Industrial and Applied Mathematics , 1999 ) . Crossref, Google Scholar
R. C. S. Machado and C. M. H. de Figueiredo , Discrete Appl. Math. 159 , 1851 ( 2011 ) . Crossref, Google Scholar
R. C. S. Machado , C. M. H. de Figueiredo and K. Vušković , Theor. Comp. Sci. 411 , 1221 ( 2010 ) . Crossref, Google Scholar
T. A. McKee , Util. Math. 73 , 217 ( 2007 ) . Google Scholar
T. A. McKee and F. R. McMorris , Topics in Intersection Graph Theory ( Society for Industrial and Applied Mathematics , 1999 ) . Crossref, Google Scholar
N. Trotignon and K. Vušković , J. Graph Theory 63 , 31 ( 2010 ) . Crossref, Google Scholar