ISSN:
1572-9125
Keywords:
Non-isomorphism of graphs
;
characteristic polynomial
;
reconstruction conjecture
;
graph perturbation
Source:
Springer Online Journal Archives 1860-2000
Topics:
Mathematics
Notes:
Abstract In this paper we prove an inverted version of A. J. Schwenk's result, which in turn is related to Ulam's reconstruction conjecture. Instead of deleting vertices from an undirected graphG, we add a new vertexv and join it to all other vertices ofG to get a perturbed graphG+v. We derive an expression for the characteristic polynomial of the perturbed graphG+v in terms of the characteristic polynomial of the original graphG. We then show the extent to which the characteristic polynomials of the perturbed graphs can be used in determining whether two graphs are non-isomorphic.
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1007/BF02136028
