𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Embeddings of cartesian products of nearly bipartite graphs

✍ Scribed by Bojan Mohar; Tomaž Pisanski; Arthur T. White

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
384 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Surgical techniques are often effective in constructing genus embeddings of cartesian products of bipartite graphs. In this paper we present a general construction that is “close” to a genus embedding for cartesian products, where each factor is “close” to being bipartite. In specializing this to repeated cartesian products of odd cycles, we are able to obtain asymptotic results in connection with the genus parameter for finite abelian groups.

📜 SIMILAR VOLUMES

Embeddings of bipartite graphs
Embeddings of bipartite graphs
✍ Mohammed Abu-Sbeih; T. D. Parsons 📂 Article 📅 1983 🏛 John Wiley and Sons 🌐 English ⚖ 458 KB
Quadrilateral embeddings of bipartite gr
Quadrilateral embeddings of bipartite graphs
✍ Ian Anderson 📂 Article 📅 1981 🏛 John Wiley and Sons 🌐 English ⚖ 304 KB

## Abstract Current graphs and a theorem of White are used to show the existence of almost complete regular bipartite graphs with quadrilateral embeddings conjectured by Pisanski. Decompositions of __K~n~__ and __K~n, n~__ into graphs with quadrilateral embeddings are discussed, and some thickness

Embedding Cartesian Products of Graphs i
Embedding Cartesian Products of Graphs into de Bruijn Graphs
✍ Thomas Andreae; Michael Nölle; Gerald Schreiber 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 172 KB

## Given a Cartesian product G of nontrivial connected graphs G i and the n-dimensional base B de Bruijn graph D = D B (n), it is investigated whether or not G is a spanning subgraph of D. Special attention is given to graphs G 1 × • • • × G m which are relevant for parallel computing, namely, to

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

Cartesian Products of Graphs and Metric
Cartesian Products of Graphs and Metric Spaces
✍ S. Avgustinovich; D. Fon-Der-Flaass 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 68 KB

We prove uniqueness of decomposition of a finite metric space into a product of metric spaces for a wide class of product operations. In particular, this gives the positive answer to the long-standing question of S. Ulam: 'If U × U V × V with U , V compact metric spaces, will then U and V be isometr

Circular chromatic index of Cartesian pr
Circular chromatic index of Cartesian products of graphs
✍ Douglas B. West; Xuding Zhu 📂 Article 📅 2007 🏛 John Wiley and Sons 🌐 English ⚖ 164 KB

## Abstract The __circular chromatic index__ of a graph __G__, written $\chi\_{c}'(G)$, is the minimum __r__ permitting a function $f : E(G)\rightarrow [0,r)$ such that $1 \le | f(e)-f(e')|\le r - 1$ whenever __e__ and $e'$ are incident. Let $G = H$ □ $C\_{2m +1}$, where □ denotes Cartesian product