✦ LIBER ✦

Hamiltonian decompositions of complete regular s-partite graphs

✍ Scribed by A.J.W. Hilton; C.A. Rodger

Publisher: Elsevier Science
Year: 1986
Tongue: English
Weight: 962 KB
Volume: 58
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(86)90186-x

No coin nor oath required. For personal study only.

✦ Synopsis

In this paper we give a procedure by which Hamiltonian decompositions of the s-partite graph K~.....,~, where (s-1)n is even, can be constructed. For 2t<~s, l<~al<~...<~a~n, we find conditions which are necessary and sufficient for a decomposition of the edge-set of Kal.a2..... ~ into (s-1)n/2 classes, each class consisting of disjoint paths, to be extendible to a Hamiltonian decomposition of the complete s-partite graph K,~ ..... so that each of the classes forms part of a Hamiltonian cycle.

📜 SIMILAR VOLUMES

On biclique decompositions of complete t

On biclique decompositions of complete t-partite graphs

✍ Elizabeth D. Boyer; Bryan L. Shader 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 704 KB

Almost regular edge colorings and regula

Almost regular edge colorings and regular decompositions of complete graphs

✍ Darryn Bryant; Barbara Maenhaut 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 127 KB

## Abstract For __k__ = 1 and __k__ = 2, we prove that the obvious necessary numerical conditions for packing __t__ pairwise edge‐disjoint __k__‐regular subgraphs of specified orders __m__~1~,__m__~2~,… ,__m__~t~ in the complete graph of order __n__ are also sufficient. To do so, we present an edge

r-Regular, r-connected decompositions of

r-Regular, r-connected decompositions of complete graphs

✍ H. Fleischner; W. R. Johnstone; A. J. W. Hilton 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 139 KB 👁 2 views

If rjn À 1 and rn is even, then K n can be expressed as the union of t nÀ1 r edgedisjoint isomorphic r-regular r-connected factors.

Decompositions of complete graphs into r

Decompositions of complete graphs into regular bichromatic factors

✍ Anton Kotzig 📂 Article 📅 1973 🏛 Elsevier Science 🌐 English ⚖ 517 KB

The proof of the following theorem is given: A complete graph with n vertkes can he decomposed into r regular bichromatic factors if and only if n is even and greater thl;iirl 4 and there exists $1 natural number k with the properties that k < r anu. ak-l < n 5 Zk.

Decompositions of complete graphs into r

Decompositions of complete graphs into regular bichromatic factors

✍ Anton Kotzig 📂 Article 📅 1972 🏛 Elsevier Science 🌐 English ⚖ 425 KB

Abstxact. The purpose of this paper is to find iI nccessar) and sufficient condition fltr the euis-trn~~ of ;L decoillposi!ion of a ~omplcte graph with given number of vc;tices into regular bichro-ma% ticfor ;uld v.1 artswcr thy' question what is the possible number of factors in such a de-c~?rnp~~i

Decompositions of regular bipartite grap

Decompositions of regular bipartite graphs

✍ Michael S. Jacobson; Miroslaw Truszczyński; Zsolt Tuza 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 692 KB

In this paper we discuss isomorphic decompositions of regular bipartite graphs into trees and forests. We prove that: (1) there is a wide class of r-regular bipartite graphs that are decomposable into any tree of size r, (2) every r-regular bipartite graph decomposes into any double star of size r,