Journal of Combinatorics

Volume 5 (2014)

Number 4

Characterizing graph classes using twin vertices of regular induced subgraphs

Pages: 435 – 444

DOI: http://dx.doi.org/10.4310/JOC.2014.v5.n4.a2

Author

Terry A. McKee (Wright State University, Dayton, Ohio, U.S.A.)

Abstract

Being a weakly chordal graph is conjectured to be equivalent to twin vertices existing in every nontrivial regular induced subgraph. Being a split graph is easily characterized by every two vertices being twins in every regular induced subgraph (and this characterizes being chordal if the regular induced subgraphs are required to be connected). The new, intermediate graph class that consists of the graphs in which every vertex has a twin in every nontrivial regular induced subgraph is introduced and explored.

Keywords

twin vertices, induced regular subgraph, chordal graph, weakly chordal graph, split graph

2010 Mathematics Subject Classification

05C75

Full Text (PDF format)