ISSN:
1089-7658
Source:
AIP Digital Archive
Topics:
Mathematics
,
Physics
Notes:
The paper considers endospectral trees, a special class of graphs associated with the production of numerous isospectral graphs. Endospectral graphs have been considered in the literature sporadically (the name was suggested very recently [M. Randic, SIAM J. Algebraic Discrete Meth. 6, 145 (1985)]). They are characterized by the presence of a pair of special vertices that, if replaced by any fragment, produce an isospectral pair of graphs. Recently Jiang [Y. Jiang, Sci. Sin. 27, 236 (1984)] and Randic and Kleiner (M. Randic and A. F. Kleiner, "On the construction of endospectral trees,'' submitted to Ann. NY Acad. Sci.) considered alternative constructive approaches to endospectral trees and listed numerous such graphs. The listing of all such trees having n=16 or fewer vertices has been undertaken here. It has been found that relatively few endospectral trees have novel structural features and cannot be reduced to some already known endospectral tree. These few have been named "irreducible endospectral trees.'' They are responsible for the occurrence of a large number of isospectral trees, leading to, when one considers trees of increasing size, the situation that led Schwenk [A. J. Schwenk, in New Directions in the Theory of Graphs, edited by F. Harary (Academic, New York, 1973), pp. 275–307] to conclude that "almost all trees are isospectral.''
Type of Medium:
Electronic Resource
URL:
http://dx.doi.org/10.1063/1.527278
Permalink
