Graphs and Combinatorics 3, 7-23 (1987)
Graphs and Combinatorics ~c) Springer-Verlag1987
Spectra of Unicyclic Graphs Drago~ Cvetkovi~ x* and Peter Rowlinson 2 1 University of Belgrade, Belgrade, Yugoslavia 2 University of Stirling, Stirling, Scotland
Several theorems involving lexicographical ordering by spectral moments as well as the ordering by the largest eigenvalue are proved. An appendix contains a table of the 89 unicyclic graphs on eight vertices together with their spectra, spectral moments and characteristic polynomials.
Abstract. Unicyclic graphs are discussed in the context of graph orderings related to eigenvalues.
1. Introduction
Connected graphs in which the number of edges equals the number of vertices are called unicyclic graphs. A unicyclic graph is either a cycle or a cycle with trees attached. The set of unicyclic graphs on e+ f vertices which, contain a cycle Ce of length e will be denoted by Uel- The subset of Uey consisting of those graphs in which exactly 9 trees are attached to Ce will be denoted by U~°I; and the set of all unicyclic graphs on n vertices will be denoted by U(n). Unicyclic graphs resemble trees in many respects. Yet while some results on the spectra of trees are known, very little about the spectra of unicyclic graphs can be found in the literature. Isolated observations apart, the only paper dealing with spectra of unicyclic graphs is a Chinese paper[13], a detailed review of which appears in Mathematical Reviews[80k: 05079]. A result and a conjecture from this paper concerning a spectral order of unicyclic graphs, together with some empirical ' observations about a similar spectral order of unicyclic graphs in the tables[9], represent the starting point of the present investigation. A counterexample to the conjecture was found by comp~ ter[4]. First we give some definitions concerning orderings of graphs. Let B -- (bl(G),bz(G),...,bs(G)) be a (finite)sequence of invariants of a graph G which are real numbers. For two graphs G~, G2 we shall write G~=B G2 if bi(G1)= bi(G2) for i= 1, 2 . . . . . s. Similarly, we have G 1<B G2 ("G1 comes before G2 in B-order") if for some k (k= 1,2 . . . . . s) we have bi(G1)= bi(G2)(i= 1,2 ....,k - 1) and bk(Ga)< bk(G2). We shall also write G 1 ___. G2 if G~<B G2 o r a 1=B G2.
*
Carnegie Research Fellow, University of Stirling, 1985-86.

o c a t e / l a a On the spectral moments of unicyclic graphs with...Many results on the spectra of graphs can be found in the literature (...
Spectra of regular quantum graphs Yu. Dabaghian, R. V. Jensen, and R. Bl¨ mel u Department of Physics, Wesleyan University, Middletown, CT 06459-01...
Products of graphs and their spectra In this paper some new methods of constructing infinite families of cospeetral graphs are presented. As an esampIe of...
Degeneracies in the length spectra of metric graphs The spectral theory of quantum graphs is related via an exact trace formula with the spectrum of the ...
[6] Y. Hong, A bound on the spectral radius of graphs, Linear Algebra...[8] Y. Hong, On the spectra of unicyclic graph, J. East China Norm....
Matching Energy of Unicyclic and Bicyclic Graphs with a Given Diameter_电子/...In contrast, we put the emphasis on analyzing properties of spectra-based ...
Classi?cation: Physical Sciences, Mathematics The spectra of random graphs with given expected degrees by Fan Chung Linyuan Lu Van Vu Department of Mathemat...
In this paper, we show that some unicyclic graphs are determined by their Laplacian spectrum. Keywords- Laplacian spectra of graphs; Cospectral graphs; ...
Laplacian Spectra Characterization of Some Special θ-Graphs_专业资料 暂无评价
Upper Hamiltonian Numbers and Hamiltonian Spectra of Graphs, manuscript If π is a cyclic order of the vertices of a graph G, the number h(π) is ...
热门文档