Minimizing algebraic connectivity over connected graphs with fixed girth

被引：33

作者：

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

共 50 条

[21] Attainable bounds for algebraic connectivity and maximally connected regular graphs
Exoo, Geoffrey
Kolokolnikov, Theodore
Janssen, Jeanette
Salamon, Timothy
JOURNAL OF GRAPH THEORY, 2024, 107 (03) : 522 - 549
[22] The ordering of unicyclic graphs with the smallest algebraic connectivity
Liu, Ying
Liu, Yue
DISCRETE MATHEMATICS, 2009, 309 (13) : 4315 - 4325
[23] On algebraic connectivity and spectral integral variations of graphs
Barik, S
Pati, S
LINEAR ALGEBRA AND ITS APPLICATIONS, 2005, 397 : 209 - 222
[24] A CONJECTURE ON ALGEBRAIC CONNECTIVITY OF GRAPHS
Das, Kinkar Ch.
TAIWANESE JOURNAL OF MATHEMATICS, 2015, 19 (05): : 1317 - 1323
[25] The Algebraic Connectivity of Circulant Graphs
Zhou, Houqing
2012 2ND INTERNATIONAL CONFERENCE ON APPLIED ROBOTICS FOR THE POWER INDUSTRY (CARPI), 2012, : 831 - 834
[26] On the maximal nullity of unicyclic graphs with fixed girth
Wang, Qingwen
Yu, Guihai
UTILITAS MATHEMATICA, 2011, 86 : 217 - 223
[27] On the spectral radius of unicyclic graphs with fixed girth
Li, Jianxi
Guo, Ji-Ming
Shiu, Wai Chee
ARS COMBINATORIA, 2013, 108 : 65 - 80
[28] Connectivity and eigenvalues of graphs with given girth or clique number
Hong, Zhen-Mu
Lai, Hong-Jian
Xia, Zheng-Jiang
LINEAR ALGEBRA AND ITS APPLICATIONS, 2020, 607 : 319 - 340
[29] On graphs with equal algebraic and vertex connectivity
Kirkland, SJ
Molitierno, JJ
Neumann, M
Shader, BL
LINEAR ALGEBRA AND ITS APPLICATIONS, 2002, 341 (1-3) : 45 - 56
[30] The algebraic connectivity of graphs under perturbation
Guo, Ji-Ming
LINEAR ALGEBRA AND ITS APPLICATIONS, 2010, 433 (06) : 1148 - 1153

← 1 2 3 4 5 →