8
$\begingroup$

Let $G = (V, E)$ be a simple, undirected, unweighted graph on $n$ nodes (all uses of the word "graph" in this question refer only to graphs with these properties). Define its Laplacian as \begin{equation} L(G) = D(G) - A(G), \end{equation} where $D(G)$ and $A(G)$ are, respectively, the degree and adjacency matrices associated with $G$.

The second-smallest eigenvalue of $L(G)$, often denoted $\lambda_2(L(G))$ or simply $\lambda_2$ when $G$ is understood, was termed its algebraic connectivity by Fiedler in seminal work $[1]$ which showed that a graph $G$ is connected if and only if $\lambda_2 > 0$.

For any fixed $n \in \mathbb{N}$, there are a finite number of graphs on $n$ nodes (without worrying about exactly how many distinct possible graphs there are, this number is clearly bounded above by $2^n$), and there are likewise a finite number of connected graphs on $n$ nodes. My question is the following.

Which simple, undirected, unweighted, connected graph on $n$ nodes minimizes the algebraic connectivity among all such graphs on $n$ nodes?

My suspicion is that the answer to this question is the path graph, thought I haven't been able to confirm this. It is known (e.g., from $[1]$) that the path graph on $n$ nodes has algebraic connectivity $\lambda_2 = 2\left(1 - \cos\frac{\pi}{n}\right)$, and I've done quite a few numerical experiments in generating graphs and trying to find one with a smaller value of $\lambda_2$, though I have not yet found such a graph for any value of $n$.

I've looked in Godsil and Royle, and while there was obviously plenty on connectivity of graphs, I couldn't seem to find the answer to this question. I've also done some Googling with search terms like "least connected graph" and "minimum algebraic connectivity of graphs," but that didn't turn anything up either.

[1] M. Fiedler, "Algebraic Connectivity of Graphs," Czechoslovak Mathematical Journal, 1973, vol. 23, no. 2, pp. 298-305.

$\endgroup$
6
+300
$\begingroup$

The fact that the path graph $P_n$ minimizes algebraic connectivity among all connected graphs with $n$ vertices follows from proposition 4.3 in Fiedler's paper.

This proposition states (among other things) that the algebraic connectivity of a graph $G$ is at least $2 e(G) (1-\cos(\pi/n))$, where $e(G)$ is the edge-connectivity of $G$, i.e. the minimum number of edges that must be removed to disconnect the graph.

This fact is also stated more explicitly (with a reference to Fiedler) as Proposition 1.12 in Belhaiza et al's Variable Neighborhood Search for Extremal Graphs. XI. Bounds on Algebraic Connectivity.

$\endgroup$
  • $\begingroup$ It seems like I need to read more carefully! Thanks for the answer and the reference to Belhaiza. $\endgroup$ – yoknapatawpha Aug 13 '17 at 12:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.