Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPowers of Hamiltonian cycles in multipartite graphs
127
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We prove that if $G$ is a $k$-partite graph on $n$ vertices in which all of the parts have order at most $n/r$ and every vertex is adjacent to at least a $1-1/r+o(1)$ proportion of the vertices in every other part, then $G$ contains the $(r-1)$-st power of a Hamiltonian cycle
rate research
Read More
We study the appearance of powers of Hamilton cycles in pseudorandom graphs, using the following comparatively weak pseudorandomness notion. A graph $G$ is $(varepsilon,p,k,ell)$-pseudorandom if for all disjoint $X$ and $Ysubset V(G)$ with $|X|gevarepsilon p^kn$ and $|Y|gevarepsilon p^ell n$ we have $e(X,Y)=(1pmvarepsilon)p|X||Y|$. We prove that for all $beta>0$ there is an $varepsilon>0$ such that an $(varepsilon,p,1,2)$-pseudorandom graph on $n$ vertices with minimum degree at least $beta pn$ contains the square of a Hamilton cycle. In particular, this implies that $(n,d,lambda)$-graphs with $lambdall d^{5/2 }n^{-3/2}$ contain the square of a Hamilton cycle, and thus a triangle factor if $n$ is a multiple of $3$. This improves on a result of Krivelevich, Sudakov and Szabo [Triangle factors in sparse pseudo-random graphs, Combinatorica 24 (2004), no. 3, 403--426]. We also extend our result to higher powers of Hamilton cycles and establish corresponding counti
In 1930, Kuratowski showed that $K_{3,3}$ and $K_5$ are the only two minor-minimal non-planar graphs. Robertson and Seymour extended finiteness of the set of forbidden minors for any surface. v{S}ir{a}v{n} and Kochol showed that there are infinitely many $k$-crossing-critical graphs for any $kge 2$, even if restricted to simple $3$-connected graphs. Recently, $2$-crossing-critical graphs have been completely characterized by Bokal, Oporowski, Richter, and Salazar. We present a simplified description of large 2-crossing-critical graphs and use this simplification to count Hamiltonian cycles in such graphs. We generalize this approach to an algorithm counting Hamiltonian cycles in all 2-tiled graphs, thus extending the results of Bodrov{z}a-Pantic, Kwong, Doroslovav{c}ki, and Pantic for $n = 2$.
Barnettes conjecture is an unsolved problem in graph theory. The problem states that every 3-regular (cubic), 3-connected, planar, bipartite (Barnette) graph is Hamiltonian. Partial results have been derived with restrictions on number of vertices, several properties of face-partitions and dual graphs of Barnette graphs while some studies focus just on structural characterizations of Barnette graphs. Noting that Spider web graphs are a subclass of Annular Decomposable Barnette (ADB graphs) graphs and are Hamiltonian, we study ADB graphs and their annular-connected subclass (ADB-AC graphs). We show that ADB-AC graphs can be generated from the smallest Barnette graph using recursive edge operations. We derive several conditions assuring the existence of Hamiltonian cycles in ADB-AC graphs without imposing restrictions on number of vertices, face size or any other constraints on the face partitions. We show that there can be two types of annuli in ADB-AC graphs, ring annuli and block annuli. Our main result is, ADB-AC graphs having non singular sequences of ring annuli are Hamiltonian.
Graham and Pollak showed that the vertices of any graph $G$ can be addressed with $N$-tuples of three symbols, such that the distance between any two vertices may be easily determined from their addresses. An addressing is optimal if its length $N$ is minimum possible. In this paper, we determine an addressing of length $k(n-k)$ for the Johnson graphs $J(n,k)$ and we show that our addressing is optimal when $k=1$ or when $k=2, n=4,5,6$, but not when $n=6$ and $k=3$. We study the addressing problem as well as a variation of it in which the alphabet used has more than three symbols, for other graphs such as complete multipartite graphs and odd cycles. We also present computations describing the distribution of the minimum length of addressings for connected graphs with up to $10$ vertices. Motivated by these computations we settle a problem of Graham, showing that most graphs on $n$ vertices have an addressing of length at most $n-(2-o(1))log_2 n$.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
