The algebraic connectivity of $P_n$, the path on $n$ vertices does not exceed $\frac{12}{n^2-1}$.

Let algebraic connectivity of $P_n$ be denoted by $\mu$. I have proved a result that if $G$ is a connected graph then if $\delta$ denotes the the minimum vertex degree in $G$ then $\mu \leq \frac{n \delta}{n-1}$.

Using this result for $P_n$ we have $\mu \leq \frac{n }{n-1}$.

We also have the following result:

Let $G$ be a connected graph with $V(G) = \{1, . . . , n\}$. Let $V_1$ and $V_2$ be nonempty disjoint subsets of $V(G)$, and let $G_1$ and $G_2$ be the subgraphs induced by $V_1$ and $V_2$, respectively. Let $L$ be the Laplacian of $G$ and $\mu$ the algebraic connectivity. Then

$$\mu \leq \frac{1}{d(V_1,V_2)^2}(\frac{1}{|V_1|} + \frac{1}{|V_2|}) (|E(G)| − |E(G_1)| − |E(G_2)|).$$

But how to get the desired inequality?

  • 2
    $\begingroup$ The algebraic connectivity of $P_n$ is equal to $2(1-\cos\frac{\pi}{n})$ and immediately the bound follows. $\endgroup$ – Mahdi Apr 24 '18 at 6:55
  • $\begingroup$ any easy trick to calculate algebraic connectivity pf $P_n$? @Mahdi $\endgroup$ – user8795 Apr 24 '18 at 7:49
  • $\begingroup$ @Mahdi suppose assume that algebraic connectivity of $P_n$ is equal to $2(1− \cos \pi /n)$, then $2(1− \cos \pi /n)< \frac{\pi ^2}{n^2}$, how will $\frac{12}{n^2-1}$ come? $\endgroup$ – user8795 Apr 24 '18 at 10:31
  • $\begingroup$ $\frac{\pi^2}{n^2} < \frac{12}{n^2} <\frac{12}{n^2-1}$. $\endgroup$ – Mahdi Apr 24 '18 at 10:56

Your Answer

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

Browse other questions tagged or ask your own question.