Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe spectral radius of graphs with no $K_{2,t}$ minor
123
0
0.0
(
0
)
Authors
V. Nikiforov
Ask ChatGPT about the research
No Arabic abstract
Let $tgeq3$ and $G$ be a graph of order $n,$ with no $K_{2,t}$ minor. If $n>400t^{6}$, then the spectral radius $muleft( Gright) $ satisfies [ muleft( Gright) leqfrac{t-1}{2}+sqrt{n+frac{t^{2}-2t-3}{4}}, ] with equality if and only if $nequiv1$ $(operatorname{mod}$ $t)$ and $G=K_{1}veeleftlfloor n/trightrfloor K_{t}$. For $t=3$ the maximum $muleft( Gright) $ is found exactly for any $n>40000$.
rate research
Read More
For a graph $H$, a graph $G$ is $H$-saturated if $G$ does not contain $H$ as a subgraph but for any $e in E(overline{G})$, $G+e$ contains $H$. In this note, we prove a sharp lower bound for the number of paths and walks on length $2$ in $n$-vertex $K_{r+1}$-saturated graphs. We then use this bound to give a lower bound on the spectral radii of such graphs which is asymptotically tight for each fixed $r$ and $ntoinfty$.
The odd wheel $W_{2k+1}$ is the graph formed by joining a vertex to a cycle of length $2k$. In this paper, we investigate the largest value of the spectral radius of the adjacency matrix of an $n$-vertex graph that does not contain $W_{2k+1}$. We determine the structure of the spectral extremal graphs for all $kgeq 2, k otin {4,5}$. When $k=2$, we show that these spectral extremal graphs are among the Tur{a}n-extremal graphs on $n$ vertices that do not contain $W_{2k+1}$ and have the maximum number of edges, but when $kgeq 9$, we show that the family of spectral extremal graphs and the family of Tur{a}n-extremal graphs are disjoint.
Write $rholeft( Gright) $ for the spectral radius of a graph $G$ and $S_{n,r}$ for the join $K_{r}veeoverline{K}_{n-r}.$ Let $n>rgeq2$ and $G$ be a $K_{r+1}$-saturated graph of order $n.$ Recently Kim, Kim, Kostochka, and O determined exactly the minimum value of $rholeft( Gright) $ for $r=2$, and found an asymptotically tight bound on $rholeft( Gright) $ for $rgeq3.$ They also conjectured that [ rholeft( Gright) >rholeft( S_{n,r-1}right) , ] unless $G=S_{n,r-1}.$ In this note their conjecture is proved.
Let k, p, q be positive integers with k < p < q+1. We prove that the maximum spectral radius of a simple bipartite graph obtained from the complete bipartite graph Kp,q of bipartition orders p and q by deleting k edges is attained when the deleting edges are all incident on a common vertex which is located in the partite set of order q. Our method is based on new sharp upper bounds on the spectral radius of bipartite graphs in terms of their degree sequences.
Let $G$ be a simple graph with vertex set $V(G) = {v_1 ,v_2 ,cdots ,v_n}$. The Harary matrix $RD(G)$ of $G$, which is initially called the reciprocal distance matrix, is an $n times n$ matrix whose $(i,j)$-entry is equal to $frac{1}{d_{ij}}$ if $i ot=j$ and $0$ otherwise, where $d_{ij}$ is the distance of $v_i$ and $v_j$ in $G$. In this paper, we characterize graphs with maximum spectral radius of Harary matrix in three classes of simple connected graphs with $n$ vertices: graphs with fixed matching number, bipartite graphs with fixed matching number, and graphs with given number of cut edges, respectively.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
