|
Outpaths of all length of an arc in regular multipartite tournaments
GUO Qiao-ping, CUI Li-nan
Applied Mathematics A Journal of Chinese Universities, 2014, 29(3): 288-294.
An $(l-1)$-outpath of an arc $x_1x_2$ in a multipartite tournament is a path $x_1x_2\cdots x_l$ of length $l-1$ starting with $x_1x_2$, such that either $x_l$ and $x_1$ are in the same partite set or $x_l$ dominates $x_1$. Specially, $x_1x_2\cdots x_lx_1$ is a Hamilton cycle when $l=|V(D)|$ and $x_l$ dominates $x_1$. Guo (Discrete Appl Math 95 (1999) 273-277) proved that every arc of a regular $c$-partite tournament with $c\geq 3$ has a $(k-1)$-outpath for each $k\in \{3, 4, \cdots, c\}$. As a generalization, the paper proves that every arc in a regular $c$-partite tournament with $c\geq 5$ has a $(k-1)$-outpath for each $k\in \{3, 4, \cdots, |V(D)|\}$ in this article. Furthermore, using the method of path-contracting, the paper also proves the following result: Let $D$ be a regular $c$-partite tournament. If $c\geq 8$ and there are two vertices in every partite set, then each arc in $D$ is contained in a Hamilton cycle. This result gives a partial support to the conjecture posed by Volkmann and Yeo (Discrete Math 281 (2004) 267-276) that each arc of a regular multipartite tournament is contained in a Hamilton cycle.
|
|
Solutions to six classes of the Oberwolfach problem OP$(4^{a},s^b)$
LI Xiao-fang, CAO Hai-tao
Applied Mathematics A Journal of Chinese Universities, 2014, 29(3): 303-309.
The problem of determining whether $K_n$ (for $n$ odd) or $K_n$ minus a 1-factor (for $n$ even) has a 2-factorization is called Oberwolfach problem. The notation OP$(m_1^{\alpha_1},m_2^{\alpha_2},\cdots,m_t^{\alpha_t})$ represents the case in which each 2-factor consists of exactly $\alpha_i$ cycles of length $m_i$ for $i=1,2,\cdots,t$. Proved that the OP$(4^{a},s^b)$ with $a\geq 0$, $b=2,3$, $s=3,5,6$ and $(a,s,b)\not=(0,3,2)$ have solutions.
|
14 articles
|