Minimizing algebraic connectivity over connected graphs with fixed girth

被引：34

作者：

Fallat, SM ^{[1
]}

Kirkland, S ^{[1
]}

Pati, S ^{[1
]}

机构：

[1] Univ Regina, Dept Math & Stat, Regina, SK S4S 0A2, Canada

来源：

DISCRETE MATHEMATICS | 2002年 / 254卷 / 1-3期

基金：

加拿大自然科学与工程研究理事会;

关键词：

Laplacian matrix; algebraic connectivity; girth; unicyclic graph; Perron value; characteristic set;

D O I：

10.1016/S0012-365X(01)00355-7

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G,g denote the class of all connected graphs on n vertices with fixed girth g. We prove that if n greater than or equal to 3g-1, then the graph which uniquely minimizes the algebraic connectivity over G,g is the unicyclic "lollipop" graph C-n,C-g obtained by appending a g cycle to a pendant vertex of a path on n - g vertices. The characteristic set of C-n,C-g is also discussed. Throughout both algebraic and combinatorial techniques are used. (C) 2002 Elsevier Science B.V. All rights reserved.

引用

页码：115 / 142

页数：28

共 21 条

[1]

[Anonymous], LINEAR ALGEBRA APPL

[2]

Bapat R.B., 1997, ENCY MATH, V64

[3]

Bapat R. B., 1998, LINEAR MULTILINEAR A, V45, P247

[4]

Bondy J.A., 2008, GRAD TEXTS MATH

[5]

Fallat S, 1998, ELECTRON J LINEAR AL, V3, P48, DOI DOI 10.13001/1081-3810.10140913.05073

[6]

FIEDLER M, 1975, CZECH MATH J, V25, P607

[7]

FIEDLER M, 1975, CZECH MATH J, V25, P619

[8]

Fiedler M., 1989, Comb. Graph Theory, V25, P57, DOI [DOI 10.4064/-25-1-57-70, 10.4064/-25-1-57-70]

[9]

FIELDER M, 1973, CZECH MATH J, V23, P298

[10]

GRADSHETEYN IS, 1965, TABLES INTEGRAL SERI

← 1 2 3 →