Advanced Search

Query:

Fill in the form and click »Search«...

Format:

Display: entries per page entries

Zbl 1033.05070
Haemers, Willem H.; Spence, Edward
Enumeration of cospectral graphs. (English)
[J] Eur. J. Comb. 25, No. 2, 199-211 (2004). ISSN 0195-6698

Summary: We have enumerated all graphs on at most 11 vertices and determined their spectra with respect to various matrices, such as the adjacency matrix and the Laplacian matrix. We have also counted the numbers for which there is at least one other graph with the same spectrum (a cospectral mate). In addition we consider a construction for pairs of cospectral graphs due to Godsil and McKay, which we call GM switching; see {\it C. D. Godsil} and {\it B. D. McKay} [Aequations Math. 25, 257--268 (1982; Zbl 0527.05051)]. It turns out that for the enumerated cases a large part of all cospectral graphs comes from GM switching, and that the fraction of graphs on $n$ vertices with a cospectral mate starts to decrease at some value of $n < 11$ (depending on the matrix). Since the fraction of cospectral graphs on $n$ vertices constructible by GM switching tends to 0 if $n \to \infty$, the present data give some indication that possibly almost no graph has a cospectral mate. We also derive asymptotic lower bounds for the number of graphs with a cospectral mate from GM switching.

MSC 2000:: *05C50 Graphs and matrices
05C30 Enumeration of graphs and maps

Keywords: Graph; Eigenvalue; Enumeration

Citations: Zbl 0527.05051

Cited in: Zbl 1239.05116 Zbl 1194.05085

Comment on this Item PDF MathML XML ASCII DVI PS BibTeX Online Ordering Article Journal

	Scientific prize winners of the ICM 2010
	Overhang
	Lie groups, physics and geometry. An introduction for physicists, engineers and chemists.

Advanced Search

Zentralblatt MATH Berlin [Germany]