Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA spectral condition for odd cycles in graphs
134
0
0.0
(
0
)
Authors
Vladimir Nikiforov
Ask ChatGPT about the research
No Arabic abstract
We give a sharp spectral condition for the existence of odd cycles in a graph of given order. We also prove a related stability result.
rate research
Read More
Let $F_{a_1,dots,a_k}$ be a graph consisting of $k$ cycles of odd length $2a_1+1,dots, 2a_k+1$, respectively which intersect in exactly a common vertex, where $kgeq1$ and $a_1ge a_2ge cdotsge a_kge 1$. In this paper, we present a sharp upper bound for the signless Laplacian spectral radius of all $F_{a_1,dots,a_k}$-free graphs and characterize all extremal graphs which attain the bound. The stability methods and structure of graphs associated with the eigenvalue are adapted for the proof.
We consider extremal problems for subgraphs of pseudorandom graphs. For graphs $F$ and $Gamma$ the generalized Turan density $pi_F(Gamma)$ denotes the density of a maximum subgraph of $Gamma$, which contains no copy of~$F$. Extending classical Turan type results for odd cycles, we show that $pi_{F}(Gamma)=1/2$ provided $F$ is an odd cycle and $Gamma$ is a sufficiently pseudorandom graph. In particular, for $(n,d,lambda)$-graphs $Gamma$, i.e., $n$-vertex, $d$-regular graphs with all non-trivial eigenvalues in the interval $[-lambda,lambda]$, our result holds for odd cycles of length $ell$, provided [ lambda^{ell-2}ll frac{d^{ell-1}}nlog(n)^{-(ell-2)(ell-3)},. ] Up to the polylog-factor this verifies a conjecture of Krivelevich, Lee, and Sudakov. For triangles the condition is best possible and was proven previously by Sudakov, Szabo, and Vu, who addressed the case when $F$ is a complete graph. A construction of Alon and Kahale (based on an earlier construction of Alon for triangle-free $(n,d,lambda)$-graphs) shows that our assumption on $Gamma$ is best possible up to the polylog-factor for every odd $ellgeq 5$.
Let $G = (V, E)$ be an $n$-vertex edge-colored graph. In 2013, H. Li proved that if every vertex $v in V$ is incident to at least $(n+1)/2$ distinctly colored edges, then $G$ admits a rainbow triangle. We prove that the same hypothesis ensures a rainbow $ell$-cycle $C_{ell}$ whenever $n ge 432 ell$. This result is sharp for all odd integers $ell geq 3$, and extends earlier work of the authors for when $ell$ is even.
Graham and Pollak showed that the vertices of any graph $G$ can be addressed with $N$-tuples of three symbols, such that the distance between any two vertices may be easily determined from their addresses. An addressing is optimal if its length $N$ is minimum possible. In this paper, we determine an addressing of length $k(n-k)$ for the Johnson graphs $J(n,k)$ and we show that our addressing is optimal when $k=1$ or when $k=2, n=4,5,6$, but not when $n=6$ and $k=3$. We study the addressing problem as well as a variation of it in which the alphabet used has more than three symbols, for other graphs such as complete multipartite graphs and odd cycles. We also present computations describing the distribution of the minimum length of addressings for connected graphs with up to $10$ vertices. Motivated by these computations we settle a problem of Graham, showing that most graphs on $n$ vertices have an addressing of length at most $n-(2-o(1))log_2 n$.
It is well known that spectral Tur{a}n type problem is one of the most classical {problems} in graph theory. In this paper, we consider the spectral Tur{a}n type problem. Let $G$ be a graph and let $mathcal{G}$ be a set of graphs, we say $G$ is textit{$mathcal{G}$-free} if $G$ does not contain any element of $mathcal{G}$ as a subgraph. Denote by $lambda_1$ and $lambda_2$ the largest and the second largest eigenvalues of the adjacency matrix $A(G)$ of $G,$ respectively. In this paper we focus on the characterization of graphs without short odd cycles according to the adjacency eigenvalues of the graphs. Firstly, an upper bound on $lambda_1^{2k}+lambda_2^{2k}$ of $n$-vertex ${C_3,C_5,ldots,C_{2k+1}}$-free graphs is established, where $k$ is a positive integer. All the corresponding extremal graphs are identified. Secondly, a sufficient condition for non-bipartite graphs containing an odd cycle of length at most $2k+1$ in terms of its spectral radius is given. At last, we characterize the unique graph having the maximum spectral radius among the set of $n$-vertex non-bipartite graphs with odd girth at least $2k+3,$ which solves an open problem proposed by Lin, Ning and Wu [Eigenvalues and triangles in graphs, Combin. Probab. Comput. 30 (2) (2021) 258-270].
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
