文档下载 文档下载导航
设为首页 | 加入收藏
搜索 请输入内容:  
 导航当前位置: 文档下载 > 所有分类 > 人文社科 > 哲学/历史 > Spectra of unicyclic graphs
侵权投诉

Spectra of unicyclic graphs

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.

Spectra of unicyclic graphs

第1页

你可能喜欢

热门文档

相关文档

站点地图 | 文档上传 | 侵权投诉 | 手机版
本站所有资源均来自互联网,本站只负责收集和整理,均不承担任何法律责任,如有侵权等其它行为请联系我们.
文档下载 Copyright 2013 doc.guandang.net All Rights Reserved.  -  email