Characterizing graph classes using twin vertices of regular induced subgraphs

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)

Published 11 March 2015