Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
4647835 | Discrete Mathematics | 2012 | 6 Pages |
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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Michael D. Barrus,