A CONJECTURE ON ALGEBRAIC CONNECTIVITY OF GRAPHS

作者：Das Kinkar Ch^*

来源：Taiwanese Journal of Mathematics, 2015, 19(5): 1317-1323.

DOI：10.11650/tjm.19.2015.5285

• Graph
• Laplacian matrix
• Laplacian spectral radius
• Algebraic connectivity
• Independence number

Let G = (V, E) be a simple graph with vertex set V (G) = {v(1), v(2), ..., v(n)} and edge set E(G). Let A(G) be the adjacency matrix of graph G and also let D(G) be the diagonal matrix with degrees of the vertices on the main diagonal. The Laplacian matrix of G is L(G) = D(G) - A(G). Among all eigenvalues of the Laplacian matrix L(G) of a graph G, the most studied is the second smallest, called the algebraic connectivity (a(G)) of a graph G [9]. Let alpha(G) be the independence number of graph G. Recently, it was conjectured that (see, [1]):
a(G) + alpha(G)
is minimum for (K-p,K-q\{e}) over bar, where e is any edge in K-p,K- (q) and p = left perpendicularn/2right perpendicular, q = inverted right perpendicularn/2inverted left perpendicular (K-p,K- q is a complete bipartite graph). The aim of this paper is to show that this conjecture is true.

• 出版日期2015