# DECOMPOSITIONS OF A COMPLETE MULTIDIGRAPH INTO ALMOST ARBITRARY PATHS

## Related Articles

- Decomposition of Product Graphs into Paths and Cycles of Length Four. Jeevadoss, S.; Muthusamy, A. // Graphs & Combinatorics;Jan2016, Vol. 32 Issue 1, p199
Let $$P_{k}$$ and $$C_k$$ respectively denote a path and a cycle on $$k$$ vertices. In this paper we give necessary and sufficient conditions for the existence of $$\{P_{5}, C_4\}_{\{p, q\}}$$ -decomposition of tensor product and cartesian product of complete graphs. Further we extent such...

- SYMMETRIC HAMILTON CYCLE DECOMPOSITIONS OF COMPLETE MULTIGRAPHS. CHITRA, V.; MUTHUSAMY, A. // Discussiones Mathematicae: Graph Theory;2013, Vol. 33 Issue 4, p695
Let n â‰¥ 3 and Î» â‰¥ 1 be integers. Let Î»K n denote the complete multi-graph with edge-multiplicity Î». In this paper, we show that there exists a symmetric Hamilton cycle decomposition of Î»K2m for all even Î» â‰¥ 2 and m â‰¥ 2. Also we show that there exists a...

- New Ore's Type Results on Hamiltonicity and Existence of Paths of Given Length in Graphs. Lichiardopol, Nicolas // Graphs & Combinatorics;Jan2013, Vol. 29 Issue 1, p99
The well-known Ore's theorem (see Ore in Am Math Mon 65:55, ), states that a graph G of order n such that d( x) + d( y) â‰¥ n for every pair { x, y} of non-adjacent vertices of G is Hamiltonian. In this paper, we considerably improve this theorem by proving that in a graph G of order n and...

- SOME REMARKS ON THE STRUCTURE OF STRONG k-TRANSITIVE DIGRAPHS. HERNÁNDEZ-CRUZ, CÉSAR; MONTELLANO-BALLESTEROS, JUAN JOSÉ // Discussiones Mathematicae: Graph Theory;2014, Vol. 34 Issue 4, p651
A digraph D is k-transitive if the existence of a directed path (v0, v1, ..., vk), of length k implies that (v0, vk) âˆˆ & A(D). Clearly, a 2-transitive digraph is a transitive digraph in the usual sense. Transitive digraphs have been characterized as compositions of complete digraphs on an...

- Neighborhood Unions for the Existence of Disjoint Chorded Cycles in Graphs. Gao, Yunshu; Li, Guojun; Yan, Jin // Graphs & Combinatorics;Sep2013, Vol. 29 Issue 5, p1337
A chorded cycle is a cycle with at least one chord. We prove that if G is a simple graph with order n â‰¥ 4 k and $${|N_G(x)\cup N_G(y)|\geq 4k+1}$$ for each nonadjacent pair of vertices x and y, then G contains k vertex-disjoint chorded cycles. The degree condition is sharp in general.

- The Existence of an Alternating Sign on a Spanning Tree of Graphs. KIM, DONGSEOK; KWON, YOUNG SOO; LEE, JAEUN // Kyungpook Mathematical Journal;Dec2012, Vol. 52 Issue 4, p513
For a spanning tree T of a connected graph .. and for a labelling Î¦: E(T ) ! {+,-}, Î¦ is called an alternating sign on a spanning tree T of a graph ... if for any cotree edge e âˆˆ E(...)-E(T ), the unique path in T joining both end vertices of e has alternating signs. In the present...

- Proof of a conjecture of Thomassen on Hamilton cycles in highlyÂ connectedÂ tournaments. Kühn, Daniela; Lapinskas, John; Osthus, Deryk; Patel, Viresh // Proceedings of the London Mathematical Society;Sep2014, Vol. 109 Issue 3, p733
A conjecture of Thomassen from 1982 states that, for every $k,$ there is an $f(k)$ so that every strongly $f(k)$-connected tournament contains $k$ edge-disjoint Hamilton cycles. A classical theorem of Camion, that every strongly connected tournament contains a Hamilton cycle, implies that...

- Decomposing Various Graphs into Short Even-Length Cycles. Horsley, Daniel // Annals of Combinatorics;Sep2012, Vol. 16 Issue 3, p571
We prove that a complete bipartite graph can be decomposed into cycles of arbitrary specified lengths provided that the obvious necessary conditions are satisfied, the length of each cycle is at most the size of the smallest part, and the longest cycle is at most three times as long as the...

- On Orthogonal Double Covers of Complete Bipartite Graphs by an Infinite Certain Graph-Path and Graph-Cycle. El-Shanawany, R. A. // British Journal of Mathematics & Computer Science;2014, Vol. 4 Issue 16, p2320
Let F be a certain graph, the graph F-Path denoted by â„™ d+1(F) path of length d with d + 1 vertices (i.e. Every edge of this path is one-to-one corresponding to an isomorphic to the graph F). In the same manner, we define the graph F-Cycle as â„‚d(F) cycle on d vertices. In this...