Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userOres condition for hamiltonicity in tough graphs
112
0
0.0
(
0
)
Authors
Songling Shan
Ask ChatGPT about the research
No Arabic abstract
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.
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.
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.
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.
The toughness of a noncomplete graph $G$ is the maximum real number $t$ such that the ratio of $|S|$ to the number of components of $G-S$ is at least $t$ for every cutset $S$ of $G$, and the toughness of a complete graph is defined to be $infty$. Determining the toughness for a given graph is NP-hard. Chv{a}tals toughness conjecture, stating that there exists a constant $t_0$ such that every graph with toughness at least $t_0$ is hamiltonian, is still open for general graphs. A graph is called $(P_3cup 2P_1)$-free if it does not contain any induced subgraph isomorphic to $P_3cup 2P_1$, the disjoint union of $P_3$ and two isolated vertices. In this paper, we confirm Chv{a}tals toughness conjecture for $(P_3cup 2P_1)$-free graphs by showing that every 7-tough $(P_3cup 2P_1)$-free graph on at least three vertices is hamiltonian.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
