Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userA Complete Solution to the Cvetkovi{c}-Rowlinson Conjecture
102
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
In 1990, Cvetkovi{c} and Rowlinson [The largest eigenvalue of a graph: a survey, Linear Multilinear Algebra 28(1-2) (1990), 3--33] conjectured that among all outerplanar graphs on $n$ vertices, $K_1vee P_{n-1}$ attains the maximum spectral radius. In 2017, Tait and Tobin [Three conjectures in extremal spectral graph theory, J. Combin. Theory, Ser. B 126 (2017) 137-161] confirmed the conjecture for sufficiently large values of $n$. In this article, we show the conjecture is true for all $ngeq2$ except for $n=6$.
rate research
Read More
Let $H_{mathrm{WR}}$ be the path on $3$ vertices with a loop at each vertex. D. Galvin conjectured, and E. Cohen, W. Perkins and P. Tetali proved that for any $d$-regular simple graph $G$ on $n$ vertices we have $$hom(G,H_{mathrm{WR}})leq hom(K_{d+1},H_{mathrm{WR}})^{n/(d+1)}.$$ In this paper we give a short proof of this theorem together with the proof of a conjecture of Cohen, Perkins and Tetali. Our main tool is a simple bijection between the Widom-Rowlinson model and the hard-core model on another graph. We also give a large class of graphs $H$ for which we have $$hom(G,H)leq hom(K_{d+1},H)^{n/(d+1)}.$$ In particular, we show that the above inequality holds if $H$ is a path or a cycle of even length at least $6$ with loops at every vertex.
This report formulates a conjectural combinatorial rule that positively expands Grothendieck polynomials into Lascoux polynomials. It generalizes one such formula expanding Schubert polynomials into key polynomials, and refines another one expanding stable Grothendieck polynomials.
For a simple graph $G$, denote by $n$, $Delta(G)$, and $chi(G)$ its order, maximum degree, and chromatic index, respectively. A connected class 2 graph $G$ is edge-chromatic critical if $chi(G-e)<Delta(G)+1$ for every edge $e$ of $G$. Define $G$ to be overfull if $|E(G)|>Delta(G) lfloor n/2 rfloor$. Clearly, overfull graphs are class 2 and any graph obtained from a regular graph of even order by splitting a vertex is overfull. Let $G$ be an $n$-vertex connected regular class 1 graph with $Delta(G) >n/3$. Hilton and Zhao in 1997 conjectured that if $G^*$ is obtained from $G$ by splitting one vertex of $G$ into two vertices, then $G^*$ is edge-chromatic critical, and they verified the conjecture for graphs $G$ with $Delta(G)ge frac{n}{2}(sqrt{7}-1)approx 0.82n$. The graph $G^*$ is easily verified to be overfull, and so the hardness of the conjecture lies in showing that the deletion of every of its edge decreases the chromatic index. Except in 2002, Song showed that the conjecture is true for a special class of graphs $G$ with $Delta(G)ge frac{n}{2}$, no other progress on this conjecture had been made. In this paper, we confirm the conjecture for graphs $G$ with $Delta(G) ge 0.75n$.
We prove the entropy conjecture of M. Barge from 1989: for every $rin [0,infty]$ there exists a pseudo-arc homeomorphism $h$, whose topological entropy is $r$. Until now all pseudo-arc homeomorphisms with known entropy have had entropy $0$ or $infty$.
Label the vertices of the complete graph $K_v$ with the integers ${ 0, 1, ldots, v-1 }$ and define the length of the edge between $x$ and $y$ to be $min( |x-y| , v - |x-y| )$. Let $L$ be a multiset of size $v-1$ with underlying set contained in ${ 1, ldots, lfloor v/2 rfloor }$. The Buratti-Horak-Rosa Conjecture is that there is a Hamiltonian path in $K_v$ whose edge lengths are exactly $L$ if and only if for any divisor $d$ of $v$ the number of multiples of $d$ appearing in $L$ is at most $v-d$. We introduce growable realizations, which enable us to prove many new instances of the conjecture and to reprove known results in a simpler way. As examples of the new method, we give a complete solution when the underlying set is contained in ${ 1,4,5 }$ or in ${ 1,2,3,4 }$ and a partial result when the underlying set has the form ${ 1, x, 2x }$. We believe that for any set $U$ of positive integers there is a finite set of growable realizations that implies the truth of the Buratti-Horak-Rosa Conjecture for all but finitely many multisets with underlying set $U$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
