✦ LIBER ✦

A Family of Perfect Factorisations of Complete Bipartite Graphs

✍ Scribed by Darryn Bryant; Barbara M. Maenhaut; Ian M. Wanless

Publisher: Elsevier Science
Year: 2002
Tongue: English
Weight: 493 KB
Volume: 98
Category: Article
ISSN: 0097-3165
DOI: 10.1006/jcta.2001.3240

No coin nor oath required. For personal study only.

✦ Synopsis

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 square is pan-Hamiltonian if the permutation defined by any row relative to any other row is a single cycle.

📜 SIMILAR VOLUMES

Solution of fink & straight conjecture o

Solution of fink & straight conjecture on path-perfect complete bipartite graphs

✍ Weiting Cao; Peter Hamburger 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 213 KB 👁 1 views

## Abstract We consider various edge disjoint partitions of complete bipartite graphs. One case is where we decompose the edge set into edge disjoint paths of increasing lengths. A graph __G__ is __path‐perfect__ if there is a positive integer __n__ such that the edge set __E__(__G__) of the graph

Families of graphs complete for the stro

Families of graphs complete for the strong perfect graph Conjecture

✍ D. G. Corneil 📂 Article 📅 1986 🏛 John Wiley and Sons 🌐 English ⚖ 381 KB 👁 1 views

The Strong Perfect Graph Conjecture states that a graph is perfect iff neither it nor its complement contains an odd chordless cycle of size greater than or equal to 5. In this article it is shown that many families of graphs are complete for this conjecture in the sense that the conjecture is true

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__ (υ) (∀υ ∈__

Regular orientable embeddings of complet

Regular orientable embeddings of complete bipartite graphs

✍ Jin Ho Kwak; Young Soo Kwon 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 199 KB

## Abstract In this paper, it will be shown that the isomorphism classes of regular orientable embeddings of the complete bipartite graph __K__~__n,n__~ are in one‐to‐one correspondence with the permutations on __n__ elements satisfying a given criterion, and the isomorphism classes of them are com

On the Pagenumber of Complete Bipartite

On the Pagenumber of Complete Bipartite Graphs

✍ Hikoe Enomoto; Tomoki Nakamigawa; Katsuhiro Ota 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 324 KB

The pagenumber p(G) of a graph G is defined as the smallest n such that G can be embedded in a book with n pages. We give an upper bound for the pagenumber of the complete bipartite graph K m, n . Among other things, we prove p(K n, n ) w2nÂ3x+1 and p(K wn 2 Â4x, n ) n&1. We also give an asymptotic

Intersection Representation of Complete

Intersection Representation of Complete Unbalanced Bipartite Graphs

✍ Nancy Eaton 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 282 KB

A p-intersection representation of a graph G is a map, f, that assigns each vertex a subset of [1, 2, ..., t] The symbol % p (G) denotes this minimum t such that a p-intersection representation of G exists. In 1966 Erdo s, Goodman, and Po sa showed that for all graphs G on 2n vertices, % 1 (G) % 1