Maximizing algebraic connectivity over unicyclic graphs

被引:22
作者
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
    CVETKOVIC, D
    ROWLINSON, P
    [J]. 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
    Fallat, SM
    Kirkland, S
    Pati, S
    [J]. 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
    GRONE, R
    MERRIS, R
    SUNDER, VS
    [J]. 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
    Kirkland, S
    [J]. LINEAR & MULTILINEAR ALGEBRA, 2000, 47 (01) : 93 - 103