Journal of Combinatorics
Volume 5 (2014)
Characterizing graph classes using twin vertices of regular induced subgraphs
Pages: 435 – 444
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