Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHamiltonicity in Cherry-quasirandom 3-graphs
87
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We show that for any fixed $alpha>0$, cherry-quasirandom 3-graphs of positive density and sufficiently large order $n$ with minimum vertex degree $alpha binom n2$ have a tight Hamilton cycle. This solves a conjecture of Aigner-Horev and Levy.
rate research
Read More
Chv{a}tal conjectured in 1973 the existence of some constant $t$ such that all $t$-tough graphs with at least three vertices are hamiltonian. While the conjecture has been proven for some special classes of graphs, it remains open in general. We say that a graph is $(K_2 cup 3K_1)$-free if it contains no induced subgraph isomorphic to $K_2 cup 3K_1$, where $K_2 cup 3K_1$ is the disjoint union of an edge and three isolated vertices. In this paper, we show that every 3-tough $(K_2 cup 3K_1)$-free graph with at least three vertices is hamiltonian.
Following a problem posed by Lovasz in 1969, it is believed that every connected vertex-transitive graph has a Hamilton path. This is shown here to be true for cubic Cayley graphs arising from groups having a $(2,s,3)$-presentation, that is, for groups $G=la a,b| a^2=1, b^s=1, (ab)^3=1, etc. ra$ generated by an involution $a$ and an element $b$ of order $sgeq3$ such that their product $ab$ has order 3. More precisely, it is shown that the Cayley graph $X=Cay(G,{a,b,b^{-1}})$ has a Hamilton cycle when $|G|$ (and thus $s$) is congruent to 2 modulo 4, and has a long cycle missing only two vertices (and thus necessarily a Hamilton path) when $|G|$ is congruent to 0 modulo 4.
Let $G$ be a $t$-tough graph on $nge 3$ vertices for some $t>0$. It was shown by Bauer et al. in 1995 that if the minimum degree of $G$ is greater than $frac{n}{t+1}-1$, then $G$ is hamiltonian. In terms of Ores conditions in this direction, the problem was only studied when $t$ is between 1 and 2. In this paper, we show that if the degree sum of any two nonadjacent vertices of $G$ is greater than $frac{2n}{t+1}+t-2$, then $G$ is hamiltonian.
We prove that any quasirandom graph with $n$ vertices and $rn$ edges can be decomposed into $n$ copies of any fixed tree with $r$ edges. The case of decomposing a complete graph establishes a conjecture of Ringel from 1963.
Let $G$ be a simple graph with maximum degree $Delta(G)$. A subgraph $H$ of $G$ is overfull if $|E(H)|>Delta(G)lfloor |V(H)|/2 rfloor$. Chetwynd and Hilton in 1985 conjectured that a graph $G$ on $n$ vertices with $Delta(G)>n/3$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph. Glock, K{u}hn and Osthus in 2016 showed that the conjecture is true for dense quasirandom graphs with even order, and they conjectured that the same should hold for such graphs with odd order. In this paper, we show that the conjecture of Glock, K{u}hn and Osthus is affirmative.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
