BZPEERPapers, people, evidence and research pathsDiscover
Research tools
Network
Opportunities
Account
Source author record
Theodore Molla appears in the imported research catalog. Authorship, coauthor and topic links are available while profile ownership is still unclaimed.
Catalog footprint
Research graph
Inspect adjacent papers, topics, institutions and collaborators without losing the researcher page.
BZPEER is loading the nearby papers, people, topics and institutions for this page.
Published work
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
Let $G = (V, E)$ be an $n$-vertex edge-colored graph. In 2013, H. Li proved that if every vertex $v \in V$ is incident to at least $(n+1)/2$ distinctly colored edges, then $G$ admits a rainbow triangle. We prove that the same hypothesis ensures a rainbow $\ell$-cycle $C_{\ell}$ whenever $n \ge 432 \ell$. This result is sharp for all odd integers $\ell \geq 3$, and extends earlier work of the authors for when $\ell$ is even.
Let $\vec{T}_k$ be the transitive tournament on $k$ vertices. We show that every oriented graph on $n=4m$ vertices with minimum total degree $(11/12+o(1))n$ can be partitioned into vertex disjoint $\vec{T}_4$'s, and this bound is asymptotically tight. We also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint $\vec{T}_k$'s.
The Hajnal--Szemerédi theorem states that for any integer $r \ge 1$ and any multiple $n$ of $r$, if $G$ is a graph on $n$ vertices and $δ(G) \ge (1 - 1/r)n$, then $G$ can be partitioned into $n/r$ vertex-disjoint copies of the complete graph on $r$ vertices. We prove a very general analogue of this result for directed graphs: for any integer $r \ge 4$ and any sufficiently large multiple $n$ of $r$, if $G$ is a directed graph on $n$ vertices and every vertex is incident to at least $2(1 - 1/r)n - 1$ directed edges, then $G$ can be partitioned into $n/r$ vertex-disjoint subgraphs of size $r$ each of which contain every tournament on $r$ vertices. A related Turán-type result is also proven.
We study the minimum degree necessary to guarantee the existence of perfect and almost-perfect triangle-tilings in an $n$-vertex graph $G$ with sublinear independence number. In this setting, we show that if $δ(G) \ge n/3 + o(n)$ then $G$ has a triangle-tiling covering all but at most four vertices. Also, for every $r \ge 5$, we asymptotically determine the minimum degree threshold for a perfect triangle-tiling under the additional assumptions that $G$ is $K_r$-free and $n$ is divisible by $3$.
In 1963, Corrádi and Hajnal settled a conjecture of Erdős by proving that, for all $k \geq 1$, any graph $G$ with $|G| \geq 3k$ and minimum degree at least $2k$ contains $k$ vertex-disjoint cycles. In 2008, Finkel proved that for all $k \geq 1$, any graph $G$ with $|G| \geq 4k$ and minimum degree at least $3k$ contains $k$ vertex-disjoint chorded cycles. Finkel's result was strengthened by Chiba, Fujita, Gao, and Li in 2010, who showed, among other results, that for all $k \geq 1$, any graph $G$ with $|G| \geq 4k$ and minimum Ore-degree at least $6k-1$ contains $k$ vertex-disjoint cycles. We refine this result, characterizing the graphs $G$ with $|G| \geq 4k$ and minimum Ore-degree at least $6k-2$ that do not have $k$ disjoint chorded cycles.
Let $n$ be sufficiently large and suppose that $G$ is a digraph on $n$ vertices where every vertex has in- and outdegree at least $n/2$. We show that $G$ contains every orientation of a Hamilton cycle except, possibly, the antidirected one. The antidirected case was settled by DeBiasio and Molla, where the threshold is $n/2+1$. Our result is best possible and improves on an approximate result by Häggkvist and Thomason.
An edge-ordering of a graph $G=(V,E)$ is a bijection $ϕ:E\to\{1,2,...,|E|\}$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,...,e_k$ is an increasing path if it is a path in $G$ which satisfies $ϕ(e_i)<ϕ(e_j)$ for all $i<j$. For a graph $G$, let $f(G)$ be the largest integer $\ell$ such that every edge-ordering of $G$ contains an increasing path of length $\ell$. The parameter $f(G)$ was first studied for $G=K_n$ and has subsequently been studied for other families of graphs. This paper gives bounds on $f$ for the hypercube and the random graph $G(n,p)$.
In 1960, Ghouila-Houri extended Dirac's theorem to directed graphs by proving that if D is a directed graph on n vertices with minimum out-degree and in-degree at least n/2 (i.e. minimum semi-degree at least n/2), then D contains a directed Hamiltonian cycle. Of course there are other orientations of a cycle in a directed graph and it is not clear that the semi-degree threshold for the directed Hamiltonian cycle is the same as the semi-degree threshold for some other orientation. In 1980, Grant initiated the problem of determining the minimum semi-degree threshold for the anti-directed Hamiltonian cycle (an orientation in which consecutive edges alternate direction). We prove that for sufficiently large even n, if D is a directed graph on n vertices with minimum semi-degree at least n/2+1, then D contains an anti-directed Hamiltonian cycle. This result is sharp.
Hajnal and Szemeredi proved that every graph G with |G|=ks and minimum degree at least k(s-1) contains k vertex disjoint s-cliques; moreover this degree bound is optimal. We extend their theorem to directed graphs by showing that every directed graph D with |D|=ks and minimum (total) degree at least 2k(s-1)-1 contains k vertex disjoint transitive tournaments on s vertices. Our result implies the Hajnal-Szemeredi Theorem, and the degree bound is optimal. We also make some conjectures regarding even more general results for multigraphs and partitioning into other tournaments. One of these conjectures is supported by an asymptotic result.
For $k \in \mathbb N$, Corrádi and Hajnal proved that every graph $G$ on $3k$ vertices with minimum degree $δ(G) \ge 2k$ has a $C_3$-factor, i.e., a partitioning of the vertex set so that each part induces the 3-cycle $C_3$. Wang proved that every directed graph $\overrightarrow G$ on $3k$ vertices with minimum total degree $δ_t(\overrightarrow G):=\min_{v\in V}(deg^-(v)+deg^+(v)) \ge 3(3k-1)/2$ has a $\overrightarrow C_3$-factor, where $\overrightarrow C_3$ is the directed 3-cycle. The degree bound in Wang's result is tight. However, our main result implies that for all integers $a \ge 1$ and $b \ge 0$ with $a+b=k$, every directed graph $\overrightarrow G$ on $3k$ vertices with minimum total degree $δ_t(\overrightarrow G)\ge 4k-1$ has a factor consisting of $a$ copies of $\overrightarrow T_3$ and $b$ copies of $\overrightarrow C_3$, where $\overrightarrow T_3$ is the transitive tournament on three vertices. In particular, using $b=0$, there is a $\overrightarrow T_3$-factor of $\overrightarrow G $, and using $a=1$, it is possible to obtain a $\overrightarrow C_3$-factor of $\overrightarrow G$ by reversing just one edge of $\overrightarrow G$. All these results are phrased and proved more generally in terms of undirected multigraphs. We conjecture that every directed graph $\overrightarrow G$ on $3k$ vertices with minimum semidegree $δ_0(\overrightarrow G):=\min_{v\in V}\min(deg^-(v),deg^+(v)) \ge 2k$ has a $\overrightarrow C_3$-factor, and prove that this is asymptotically correct.
In 2006, Kühn and Osthus showed that if a 3-graph H on n vertices has minimum co-degree at least (1/4 +o(1))n and n is even then H has a loose Hamilton cycle. In this paper, we prove that the minimum co-degree of n/4 suffices. The result is tight.