Article ID Journal Published Year Pages File Type
4647835 Discrete Mathematics 2012 6 Pages PDF
Abstract

A 2-switch is an edge addition/deletion operation that changes adjacencies in the graph while preserving the degree of each vertex. A well-known result states that graphs with the same degree sequence may be changed into each other via sequences of 2-switches. We show that if a 2-switch changes the isomorphism class of a graph, then it must take place in one of four configurations. We also present a sufficient condition for a 2-switch to change the isomorphism class of a graph. As consequences, we give a new characterization of matrogenic graphs and determine the largest hereditary graph family whose members are all the unique realizations (up to isomorphism) of their respective degree sequences.

Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
,