✦ LIBER ✦

Self-dual embeddings of complete multipartite graphs

✍ Scribed by Dan Archdeacon

Publisher: John Wiley and Sons
Year: 1994
Tongue: English
Weight: 761 KB
Volume: 18
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190180709

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

In this paper we examine self‐dual embeddings of complete multipartite graphs, focusing primarily on K~m(n)~ having m parts each of size n. If m = 2, then n must be even. If the embedding is on an orientable surface, then an Euler characteristic argument shows that no such embedding exists when n is odd and m  2, 3 (mod 4); there is no such restriction for embeddings on nonorientable surfaces. We show that these embeddings exist with a few small exceptions. As a corollary, every group has a Cayley graph with a self‐dual embedding. Our main technique is an addition construction that combines self‐dual embeddings of two subgraphs into a self‐dual embedding of their union. We also apply this technique to nonregular multipartite graphs and to cubes.

📜 SIMILAR VOLUMES

Self-dual embeddings of complete biparti

Self-dual embeddings of complete bipartite graphs

✍ Dan Archdeacon; Nora Hartsfield 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 439 KB

Self-dual embeddings of Cayley graphs

✍ Saul Stahl 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 764 KB

The chromatic index of complete multipar

The chromatic index of complete multipartite graphs

✍ D. G. Hoffman; C. A. Rodger 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB

## Abstract We show that a complete multipartite graph is class one if and only if it is not eoverfull, thus determining its chromatic index.

Fair Hamilton Decompositions of Complete

Fair Hamilton Decompositions of Complete Multipartite Graphs

✍ C.D. Leach; C.A. Rodger 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 88 KB

A fair hamilton decomposition of the complete multipartite graph G is a set of hamilton cycles in G whose edges partition the edges of G in such a way that, for each pair of parts and for each pair of hamilton cycles H 1 and H 2 , the difference in the number of edges in H 1 and H 2 joining vertices

On path factorizations of complete multi

On path factorizations of complete multipartite graphs

✍ Min-li Yu 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 523 KB

## Necessary conditions for IK(n, r), the complete multipartite graph with r parts of size n in which each edge has multiplicity 1, to have a P,-factorization are nr=O(mod k) and i(r-l)kn=O(mod2(k-1)). We show that when n=O(modk) or r=O(modk), these two conditions are also sufficient. (This impli

Critical groups for complete multipartit

Critical groups for complete multipartite graphs and Cartesian products of complete graphs

✍ Brian Jacobson; Andrew Niedermaier; Victor Reiner 📂 Article 📅 2003 🏛 John Wiley and Sons 🌐 English ⚖ 147 KB

## Abstract The critical group of a connected graph is a finite abelian group, whose order is the number of spanning trees in the graph, and which is closely related to the graph Laplacian. Its group structure has been determined for relatively few classes of graphs, e.g., complete graphs and compl