The algebraic connectivity of barbell graphs

被引：0

作者：

Song, Xiaodi ^{[1
,2
]}

Zhang, Shenggui ^{[1
,2
]}

Chen, Xinzhuang ^{[3
]}

Gao, Shanshan ^{[4
]}

机构：

[1] Northwestern Polytech Univ, Sch Math & Stat, Xian 710129, Shaanxi, Peoples R China

[2] Northwestern Polytech Univ, Xian Budapest Joint Res Ctr Combinator, Xian 710129, Shaanxi, Peoples R China

[3] Yanan Univ, Sch Math & Comp Sci, Yanan 716000, Shaanxi, Peoples R China

[4] Shanghai Univ Elect Power, Coll Econ & Management, Shanghai 201306, Peoples R China

来源：

DISCRETE MATHEMATICS | 2024年 / 347卷 / 07期

基金：

中国国家自然科学基金;

关键词：

Algebraic connectivity; Fiedler vector; Barbell graph; Graph perturbation; ORDERING TREES; FIXED NUMBER; NETWORKS; CONSENSUS; TOPOLOGY; TERMS;

D O I：

10.1016/j.disc.2024.114027

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

The algebraic connectivity of a graph is the second smallest eigenvalue of its Laplacian matrix. An eigenvector affording the algebraic connectivity is called a Fiedler vector. The barbell graph B-p,B-q;l is the graph obtained by joining a vertex in a cycle C-p (p not equal 2) and a vertex in a cycle C-q (q not equal 2) by a path P-l with p >= 3 or q >= 3, and l >= 2 if p = 1 or q = 1. In this paper, we determine the graphs minimizing the algebraic connectivity among all barbell graphs and the graphs containing a barbell graph as a spanning subgraph of given order, respectively. Moreover, we investigate how the algebraic connectivity behaves under some graph perturbations, and compare the algebraic connectivities of barbell graphs, cycles, and theta-graphs. (c) 2024 Elsevier B.V. All rights reserved.

引用

页数：10

共 34 条

[1] Ordering trees and graphs with few cycles by algebraic connectivity [J].

Abreu, Nair ;

Justel, Claudia Marcela ;

Rojo, Oscar ;

Trevisan, Vilmar .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2014, 458 :429-453

[2] Graphs of given order and size and minimum algebraic connectivity [J].

Biyikoglu, Turker ;

Leydold, Josef .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2012, 436 (07) :2067-2077

[3]

Bondy JA, 2008, GRAPH THEORY

[4]

Boulet R, 2008, ELECTRON J COMB, V15

[5]

Cvetkovic D. M., 1980, Spectra of Graphs. Theory and Application

[6] Old and new results on algebraic connectivity of graphs [J].

de Abreu, Nair Maria Maia .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2007, 423 (01) :53-73

[7]

Fallat S., 1998, ELECTRON J LINEAR AL, V3, P48, DOI [10.13001/1081-3810.1014, DOI 10.13001/1081-3810.1014]

[8] Minimizing algebraic connectivity over connected graphs with fixed girth [J].

Fallat, SM ;

Kirkland, S ;

Pati, S .

DISCRETE MATHEMATICS, 2002, 254 (1-3) :115-142

[9] A Lower Bound for the Algebraic Connectivity of a Graph in Terms of the Domination Number [J].

Fan, Yi-Zheng ;

Tan, Ying-Ying .

ACTA MATHEMATICAE APPLICATAE SINICA-ENGLISH SERIES, 2018, 34 (04) :752-760

[10]

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

← 1 2 3 4 →