Maximizing algebraic connectivity over unicyclic graphs

被引:24
作者
Fallat, SM [1 ]
Kirkland, S
Pati, S
机构
[1] Univ Regina, Dept Math & Stat, Regina, SK S4S 0A2, Canada
[2] Indian Inst Technol Guwahati, Dept Math, N Guwahati 781039, Assam, India
基金
加拿大自然科学与工程研究理事会;
关键词
Laplacian matrix; algebraic connectivity; unicyclic graph; Perron value;
D O I
10.1080/0308108031000069182
中图分类号
O1 [数学];
学科分类号
0701 ; 070101 ;
摘要
We consider the class of unicyclic graphs on n vertices with girth g, and over that class, we attempt to determine which graph maximizes the algebraic connectivity. When g is fixed, we show that there is an N such that for each n>N, the maximizing graph consists of a g cycle with n-g pendant vertices adjacent to a common vertex on the cycle. We also provide a bound on N. On the other hand, when g is large relative to n, we show that this graph does not maximize the algebraic connectivity, and we give a partial discussion of the nature of the maximizing graph in that situation.
引用
收藏
页码:221 / 241
页数:21
相关论文
共 14 条
[1]  
[Anonymous], LINEAR ALGEBRA APPL
[2]  
Bapat R. B., 1998, LINEAR MULTILINEAR A, V45, P247
[3]   SPECTRA OF UNICYCLIC GRAPHS [J].
CVETKOVIC, D ;
ROWLINSON, P .
GRAPHS AND COMBINATORICS, 1987, 3 (01) :7-23
[4]  
Fallat S, 1998, ELECTRON J LINEAR AL, V3, P48, DOI DOI 10.13001/1081-3810.10140913.05073
[5]   Minimizing algebraic connectivity over connected graphs with fixed girth [J].
Fallat, SM ;
Kirkland, S ;
Pati, S .
DISCRETE MATHEMATICS, 2002, 254 (1-3) :115-142
[6]  
FIEDLER M, 1973, CZECH MATH J, V23, P298
[7]  
Fiedler M., 1989, Comb. Graph Theory, V25, P57, DOI [DOI 10.4064/-25-1-57-70, 10.4064/-25-1-57-70]
[8]   THE LAPLACIAN SPECTRUM OF A GRAPH [J].
GRONE, R ;
MERRIS, R ;
SUNDER, VS .
SIAM JOURNAL ON MATRIX ANALYSIS AND APPLICATIONS, 1990, 11 (02) :218-238
[9]  
GRONE R, 1987, CZECH MATH J, V37, P660
[10]   A bound on the algebraic connectivity of a graph in terms of the number of cutpoints [J].
Kirkland, S .
LINEAR & MULTILINEAR ALGEBRA, 2000, 47 (01) :93-103