Journal of Combinatorics

Volume 5 (2014)

Number 4

Characterizing graph classes using twin vertices of regular induced subgraphs

Pages: 435 – 444



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


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.


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

2010 Mathematics Subject Classification


Full Text (PDF format)