Some Properties of Algebraic Connectivity

  • PDF / 275,591 Bytes
  • 6 Pages / 595.276 x 790.866 pts Page_size
  • 73 Downloads / 214 Views

DOWNLOAD

REPORT


SHORT COMMUNICATION

Some Properties of Algebraic Connectivity Muhuo Liu1,2 • Guangliang Zhang3 • Kinkar Chandra Das4

Received: 17 July 2017 / Revised: 9 April 2018 / Accepted: 18 January 2020 Ó The National Academy of Sciences, India 2020

Abstract In this paper, we obtain two methods to compare the algebraic connectivity of two graphs, and we also give some graph operations that increase or decrease the algebraic connectivity of a graph. Keywords Algebraic connectivity  Graph operation  Fiedler vector Mathematics Subject Classification 05C35  05C75  05C05

Introduction Throughout this paper, G is a simple undirected graph. For a vertex v of the graph G, we use N(v) and d(v) to denote the neighbor set and degree of v in G, respectively. If dðuÞ ¼ 1, then we call u a pendant vertex. Suppose that P

& Kinkar Chandra Das [email protected] Muhuo Liu [email protected] Guangliang Zhang [email protected] 1

Department of Mathematics, South China Agricultural University, Guangzhou 510642, People’s Republic of China

2

College of Mathematics and Statistics, Shenzhen University, Shenzhen 518060, People’s Republic of China

3

School of Mathematics and Systems Science, Guangdong Polytechnic Normal University, Guangzhou 510665, People’s Republic of China

4

Department of Mathematics, Sungkyunkwan University, Suwon 16419, Republic of Korea

is a path. If one end vertex of P is a pendant vertex while all the internal vertices of P are vertices with degrees two, then P is called a pendant path. As usual, Cn and Pn define, respectively, the cycle and path on n vertices. Suppose v is a vertex of G, and Ps ¼ w1 w2    ws , where VðPs Þ \ VðGÞ ¼ ;. If we obtain a new graph G0 from G and Ps by adding one edge vw1 , then we say that G0 is obtained from G by attaching the pendant vertex w1 of Ps to v of G. If G is a connected graph with n vertices and n  1 (respectively, n) edges, then G is called a tree (respectively, a unicyclic graph). Hereafter, let PnDþ1 ¼ x1 x2    xnDþ1 and let Bðn; DÞ be a tree with n vertices and maximum degree D obtained from PnDþ1 by attaching D  1 pendent vertices (say xn ; xn1 ; . . .; xnDþ2 ) to the vertex xnDþ1 of PnDþ1 . Let Zxk be the tree with n vertices obtained from Bðn  p; DÞ by attaching p pendant vertices to xk of Bðn  p; DÞ, where p  1. The Laplacian matrix of G is defined as LðGÞ ¼ DðGÞ  AðGÞ, where D(G) and A(G) are the diagonal matrix of vertex degrees and adjacency matrix of G, respectively. Since L(G) is positive semidefinite matrix with all row sums being equal to zero [1], we can use k1 ðGÞ  k2 ðGÞ      kn1 ðGÞ  kn ðGÞ ¼ 0 to denote the eigenvalues of L(G). As early as in 1973, Fiedler [2] revealed the relation between Laplacian spectrum and structure of G via proving that ‘‘G is connected if and only if kn1 ðGÞ [ 0.’’ From then on, kn1 ðGÞ is also called the algebraic connectivity of G. In the following, we always use the symbol aðGÞ in place of kn1 ðGÞ; and call an eigenvector corresponding to aðGÞ a Fiedler vector of G. Eichinger et al. [3, 4] prese

Data Loading...