Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userHamilton decompositions of line graphs
164
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
It is proved that if a graph is regular of even degree and contains a Hamilton cycle, or regular of odd degree and contains a Hamiltonian $3$-factor, then its line graph is Hamilton decomposable. This result partially extends Kotzigs result that a $3$-regular graph is Hamiltonian if and only if its line graph is Hamilton decomposable, and proves the conjecture of Bermond that the line graph of a Hamilton decomposable graph is Hamilton decomposable.
rate research
Read More
Let $G$ be a graph whose edges are coloured with $k$ colours, and $mathcal H=(H_1,dots , H_k)$ be a $k$-tuple of graphs. A monochromatic $mathcal H$-decomposition of $G$ is a partition of the edge set of $G$ such that each part is either a single edge or forms a monochromatic copy of $H_i$ in colour $i$, for some $1le ile k$. Let $phi_{k}(n,mathcal H)$ be the smallest number $phi$, such that, for every order-$n$ graph and every $k$-edge-colouring, there is a monochromatic $mathcal H$-decomposition with at most $phi$ elements. Extending the previous results of Liu and Sousa [Monochromatic $K_r$-decompositions of graphs, Journal of Graph Theory}, 76:89--100, 2014], we solve this problem when each graph in $mathcal H$ is a clique and $nge n_0(mathcal H)$ is sufficiently large.
This paper is motivated by the following question: what are the unavoidable induced subgraphs of graphs with large treewidth? Aboulker et al. made a conjecture which answers this question in graphs of bounded maximum degree, asserting that for all $k$ and $Delta$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a subdivision of the $(ktimes k)$-wall or the line graph of a subdivision of the $(ktimes k)$-wall as an induced subgraph. We prove two theorems supporting this conjecture, as follows. 1. For $tgeq 2$, a $t$-theta is a graph consisting of two nonadjacent vertices and three internally disjoint paths between them, each of length at least $t$. A $t$-pyramid is a graph consisting of a vertex $v$, a triangle $B$ disjoint from $v$ and three paths starting at $v$ and disjoint otherwise, each joining $v$ to a vertex of $B$, and each of length at least $t$. We prove that for all $k,t$ and $Delta$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a $t$-theta, or a $t$-pyramid, or the line graph of a subdivision of the $(ktimes k)$-wall as an induced subgraph. This affirmatively answers a question of Pilipczuk et al. asking whether every graph of bounded maximum degree and sufficiently large treewidth contains either a theta or a triangle as an induced subgraph (where a theta means a $t$-theta for some $tgeq 2$). 2. A subcubic subdivided caterpillar is a tree of maximum degree at most three whose all vertices of degree three lie on a path. We prove that for every $Delta$ and subcubic subdivided caterpillar $T$, every graph with maximum degree at most $Delta$ and sufficiently large treewidth contains either a subdivision of $T$ or the line graph of a subdivision of $T$ as an induced subgraph.
P. J. Kelly conjectured in 1968 that every diregular tournament on (2n+1) points can be decomposed in directed Hamilton circuits [1]. We define so called leading diregular tournament on (2n+1) points and show that it can be decomposed in directed Hamilton circuits when (2n+1) is a prime number. When (2n+1) is not a prime number this method does not work and we will need to devise some another method. We also propose a general method to find Hamilton decomposition of certain tournament for all sizes.
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
Given an $n$ vertex graph whose edges have colored from one of $r$ colors $C={c_1,c_2,ldots,c_r}$, we define the Hamilton cycle color profile $hcp(G)$ to be the set of vectors $(m_1,m_2,ldots,m_r)in [0,n]^r$ such that there exists a Hamilton cycle that is the concatenation of $r$ paths $P_1,P_2,ldots,P_r$, where $P_i$ contains $m_i$ edges. We study $hcp(G_{n,p})$ when the edges are randomly colored. We discuss the profile close to the threshold for the existence of a Hamilton cycle and the threshold for when $hcp(G_{n,p})={(m_1,m_2,ldots,m_r)in [0,n]^r:m_1+m_2+cdots+m_r=n}$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
