Minimal Extremal Graphs for Addition of Algebraic Connectivity and Independence Number of Connected Graphs

Abstract

Let $G=(V,\,E)$ be a simple connected graph. Denote by $D(G)$ the diagonal matrix of its vertex degrees and by $A(G)$ its adjacency matrix. Then the Laplacian matrix of graph $G$ is $L(G)=D(G)-A(G)$. Let $a(G)$ and $\alpha(G)$, respectively, be the second smallest Laplacian eigenvalue
and the independence number of graph $G$. In this paper, we characterize the extremal graph with second minimum value for addition of algebraic connectivity and independence number among all connected graphs with $n\geq 6$ vertices (Actually, we can determine the $p$-th minimum value of $a(G) + \alpha(G)$ under certain condition when $p$ is small). Moreover, we present a lower bound to the addition of algebraic connectivity and radius of connected graphs.