Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSufficient spectral conditions for graphs being $k$-edge-Hamiltonian or $k$-Hamiltonian
108
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A graph $G$ is $k$-edge-Hamiltonian if any collection of vertex-disjoint paths with at most $k$ edges altogether belong to a Hamiltonian cycle in $G$. A graph $G$ is $k$-Hamiltonian if for all $Ssubseteq V(G)$ with $|S|le k$, the subgraph induced by $V(G)setminus S$ has a Hamiltonian cycle. These two concepts are classical extensions for the usual Hamiltonian graphs. In this paper, we present some spectral sufficient conditions for a graph to be $k$-edge-Hamiltonian and $k$-Hamiltonian in terms of the adjacency spectral radius as well as the signless Laplacian spectral radius. Our results extend the recent works proved by Li and Ning [Linear Multilinear Algebra 64 (2016)], Nikiforov [Czechoslovak Math. J. 66 (2016)] and Li, Liu and Peng [Linear Multilinear Algebra 66 (2018)]. Moreover, we shall prove a stability result for graphs being $k$-Hamiltonian, which can be viewed as a complement of two recent results of F{u}redi, Kostochka and Luo [Discrete Math. 340 (2017)] and [Discrete Math. 342 (2019)].
rate research
Read More
We provide a computer-assisted proof that if G is any finite group of order kp, where k < 48 and p is prime, then every connected Cayley graph on G is hamiltonian (unless kp = 2). As part of the proof, it is verified that every connected Cayley graph of order less than 48 is either hamiltonian connected or hamiltonian laceable (or has valence less than three).
Halin showed that every edge minimal, k-vertex connected graph has a vertex of degree k. In this note, we prove the analogue to Halins theorem for edge-minimal, k-edge-connected graphs. We show there are two vertices of degree k in every edge-minimal, k-edge-connected graph.
In the spirit of recent work of Harada-Kaveh and Nishinou-Nohara-Ueda, we study the symplectic geometry of Popovs horospherical degenerations of complex algebraic varieties with the action of a complex linearly reductive group. We formulate an intrinsic symplectic contraction of a Hamiltonian space, which is a surjective, continuous map onto a new Hamiltonian space that is a symplectomorphism on an explicitly defined dense open subspace. This map is given by a precise formula, using techniques from the theory of symplectic reduction and symplectic implosion. We then show, using the Vinberg monoid, that the gradient-Hamiltonian flow for a horospherical degeneration of an algebraic variety gives rise to this contraction from a general fiber to the special fiber. We apply this construction to branching problems in representation theory, and finally we show how the Gelfand-Tsetlin integrable system can be understood to arise this way.
We prove for all $kgeq 4$ and $1leqell<k/2$ the sharp minimum $(k-2)$-degree bound for a $k$-uniform hypergraph $mathcal H$ on $n$ vertices to contain a Hamiltonian $ell$-cycle if $k-ell$ divides $n$ and $n$ is sufficiently large. This extends a result of Han and Zhao for $3$-uniform hypegraphs.
Trotter and Erdos found conditions for when a directed $m times n$ grid graph on a torus is Hamiltonian. We consider the analogous graphs on a two-holed torus, and study their Hamiltonicity. We find an $mathcal{O}(n^4)$ algorithm to determine the Hamiltonicity of one of these graphs and an $mathcal{O}(log(n))$ algorithm to find the number of diagonals, which are sets of vertices that force the directions of edges in any Hamiltonian cycle. We also show that there is a periodicity pattern in the graphs Hamiltonicities if one of the sides of the grid is fixed; and we completely classify which graphs are Hamiltonian in the cases where $n=m$, $n=2$, the $m times n$ graph has $1$ diagonal, or the $frac{m}{2} times frac{n}{2}$ graph has $1$ diagonal.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
