✦ LIBER ✦

Complete bipartite factorisations by complete bipartite graphs

✍ Scribed by N. Martin

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 887 KB
Volume: 167-168
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(97)00248-3

No coin nor oath required. For personal study only.

✦ Synopsis

We study complete Kp,q-factorisations of Kin, n, Simple necessary conditions are found and we conjecture that these conditions are also sufficient. A general construction is given to find infinite families of factorisations proving the conjecture in many cases. The conjecture is proved for Kl,q-factorisations of Kn, n except for q = 4k + 1. The conjecture is also proved for a further family of Kl, 3-factorisations.

📜 SIMILAR VOLUMES

A Family of Perfect Factorisations of Co

A Family of Perfect Factorisations of Complete Bipartite Graphs

✍ Darryn Bryant; Barbara M. Maenhaut; Ian M. Wanless 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 493 KB

A 1-factorisation of a graph is perfect if the union of any two of its 1-factors is a Hamiltonian cycle. Let n=p 2 for an odd prime p. We construct a family of ( p -1)/2 non-isomorphic perfect 1-factorisations of K n, n . Equivalently, we construct pan-Hamiltonian Latin squares of order n. A Latin s

Packing two bipartite graphs into a comp

Packing two bipartite graphs into a complete bipartite graph

✍ Wang, Hong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 131 KB 👁 3 views

For two integers a and b, we say that a bipartite graph G admits an (a, b)bipartition if G has a bipartition (X, Y ) such that |X| = a and |Y | = b. We say that two bipartite graphs G and H are compatible if, for some integers a and b, both G and H admit (a, b)-bipartitions. In this paper, we prove

Pagenumber of complete bipartite graphs

✍ Douglas J. Muder; Margaret Lefevre Weaver; Douglas B. West 📂 Article 📅 1988 🏛 John Wiley and Sons 🌐 English ⚖ 929 KB

Partitioning Complete Bipartite Graphs b

Partitioning Complete Bipartite Graphs by Monochromatic Cycles

✍ P.E. Haxell 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 886 KB

For every positive integer r there exists a constant C r depending only on r such that for every colouring of the edges of the complete bipartite graph K n, n with r colours, there exists a set of at most C r monochromatic cycles whose vertex sets partition the vertex set of K n, n . This answers a

Hall parameters of complete and complete

Hall parameters of complete and complete bipartite graphs

✍ M. M. Cropper; A. J. W. Hilton 📂 Article 📅 2002 🏛 John Wiley and Sons 🌐 English ⚖ 287 KB

## Abstract Given a graph __G__, for each υ ∈__V__(__G__) let __L__(υ) be a list assignment to __G__. The well‐known choice number __c__(__G__) is the least integer __j__ such that if |__L__(υ)| ≥__j__ for all υ ∈__V__(__G__), then __G__ has a proper vertex colouring ϕ with ϕ(υ) ∈ __L__ (υ) (∀υ ∈__

Acyclic orientations of complete biparti

Acyclic orientations of complete bipartite graphs

✍ Douglas B. West 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 216 KB

For a complete bipartite graph, the number of dependent edges in an acyclic orientation can be any integer from n-1 to e, where n and e are the number of vertices and edges in the graph. ## Ke3,words: Bipartite graph; Acyclic orientation Ill combinatorics we often ask whether an integer parameter