Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCayley graphs of order kp are hamiltonian for k < 48
80
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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).
rate research
Read More
We show that if G is a finite group whose commutator subgroup [G,G] has order 2p, where p is an odd prime, then every connected Cayley graph on G has a hamiltonian cycle.
Let $G$ be a finite group. We show that if $|G| = pqrs$, where $p$, $q$, $r$, and $s$ are distinct odd primes, then every connected Cayley graph on $G$ has a hamiltonian cycle.
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)].
A graph is said to be {em vertex-transitive non-Cayley} if its full automorphism group acts transitively on its vertices and contains no subgroups acting regularly on its vertices. In this paper, a complete classification of cubic vertex-transitive non-Cayley graphs of order $12p$, where $p$ is a prime, is given. As a result, there are $11$ sporadic and one infinite family of such graphs, of which the sporadic ones occur when $p=5$, $7$ or $17$, and the infinite family exists if and only if $pequiv1 (mod 4)$, and in this family there is a unique graph for a given order.
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
