Diameters of Graphs with Spectral Radius at most $3/2\sqrt{2}$

Details Diameters of Graphs with Spectral Radius at most $3/2\sqrt{2}$ Diameters of Graphs with Spectral Radius at most $3/2\sqrt{2}$

2011-12-21

arxiv.org/abs/1112.4947v1

Mathematics

Combinatorics

18 pages

Scientific paper

The spectral radius $\rho(G)$ of a graph $G$ is the largest eigenvalue of its adjacency matrix. Woo and Neumaier discovered that a connected graph $G$ with $\rho(G)\leq 3/2{\sqrt{2}}$ is either a dagger, an open quipu, or a closed quipu. The reverse statement is not true. Many open quipus and closed quipus have spectral radius greater than $3/2{\sqrt{2}}$. In this paper we proved the following results. For any open quipu $G$ on $n$ vertices ($n\geq 6$) with spectral radius less than $3/2{\sqrt{2}}$, its diameter $D(G)$ satisfies $D(G)\geq (2n-4)/3$. This bound is tight. For any closed quipu $G$ on $n$ vertices ($n\geq 13$) with spectral radius less than $3/2{\sqrt{2}}$, its diameter $D(G)$ satisfies $\frac{n}{3}< D(G)\leq \frac{2n-2}{3}$. The upper bound is tight while the lower bound is asymptotically tight. Let $G^{min}_{n,D}$ be a graph with minimal spectral radius among all connected graphs on $n$ vertices with diameter $D$. We applied the results and found $G^{min}_{n,D}$ for some range of $D$. For $n\geq 13$ and $D\in [\frac{n}{2}, \frac{2n-7}{3}]$, we proved that $G^{min}_{n,D}$ is the graph obtained by attaching two paths of length $D-\lfloor\frac{n}{2}\rfloor$ and $D-\lceil\frac{n}{2}\rceil$ to a pair of antipodal vertices of the even cycle $C_{2(n-D)}$. Thus we settled a conjecture of Cioab-van Dam-Koolen-Lee, who previously proved a special case $D=\frac{n+e}{2}$ for $e=1,2,3,4$.

Affiliated with

Also associated with

No associations

Rating

Diameters of Graphs with Spectral Radius at most $3/2\sqrt{2}$ does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Diameters of Graphs with Spectral Radius at most $3/2\sqrt{2}$, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Diameters of Graphs with Spectral Radius at most $3/2\sqrt{2}$ will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-191418