0
$\begingroup$

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?

Improve this question
$\endgroup$
4
  • 2
    $\begingroup$ The algebraic connectivity of $P_n$ is equal to $2(1-\cos\frac{\pi}{n})$ and immediately the bound follows. $\endgroup$
    – Mahdi - Free Palestine
    Commented Apr 24, 2018 at 6:55
  • $\begingroup$ any easy trick to calculate algebraic connectivity pf $P_n$? @Mahdi $\endgroup$
    – User8976
    Commented Apr 24, 2018 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$
    – User8976
    Commented Apr 24, 2018 at 10:31
  • $\begingroup$ $\frac{\pi^2}{n^2} < \frac{12}{n^2} <\frac{12}{n^2-1}$. $\endgroup$
    – Mahdi - Free Palestine
    Commented Apr 24, 2018 at 10:56

0

Reset to default

You must log in to answer this question.