𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Euler cycles in the complete graph K2m+1

✍ Scribed by Tomáš Dvořák; Ivan Havel; Petr Liebl

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
661 KB
Volume
171
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We analyze the freedom one has when walking along an Euler cycle through a complete graph of an odd order: Is it possible, for any cycle C of (2~+1) vertices, 2m + 1 of them being black, to find an edge monomorphism of C onto K2m+~, that would be injective on the set of black vertices of C? It is shown that the answer is positive for all but two cases. Our proof is constructive, however, we relied on computers to verify approximately 37 000 cases needed for the induction basis. Our theorem generalizes a previous result on the decomposition of K2m+I into edge-disjoint trails of given lengths. In addition, a relation to the concept of harmonious chromatic number is mentioned.

📜 SIMILAR VOLUMES

Maximum packings of the complete graph w
Maximum packings of the complete graph with uniform length cycles
✍ Daniel Horsley 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 86 KB

In this paper we find the maximum number of pairwise edgedisjoint m-cycles which exist in a complete graph with n vertices, for all values of n and m with 3 ≤ m ≤ n.

Decomposition of the complete graph plus
Decomposition of the complete graph plus a 1-factor into cycles of equal length
✍ Mateja Šajna 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 354 KB 👁 1 views

## Abstract We determine the necessary and sufficient conditions for the existence of a decomposition of the complete graph of even order with a 1‐factor added into cycles of equal length. © 2003 Wiley Periodicals, Inc. J Combin Designs 11: 170–207, 2003; Published online in Wiley InterScience (www

Note on the existence of directed (k + 1
Note on the existence of directed (k + 1)-cycles in diconnected complete k-partite digraphs
✍ R. Balakrishnan; P. Paulraja 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 150 KB 👁 1 views

A graph is constructed to provide a negative answer to the following question of Bondy: Does every diconnected orientation of a complete k-partite (k 2 5) graph with each part of size at least 2 yield a directed (k + 1)-cycle?