𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Decompositions of regular bipartite graphs

✍ Scribed by Michael S. Jacobson; Miroslaw Truszczyński; Zsolt Tuza

Publisher
Elsevier Science
Year
1991
Tongue
English
Weight
692 KB
Volume
89
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

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, and (3) every 4-regular bipartite graph decomposes into paths Pd.

📜 SIMILAR VOLUMES

Regular path decompositions of odd regul
Regular path decompositions of odd regular graphs
✍ Odile Favaron; François Genest; Mekkia Kouider 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 197 KB

## Abstract Kotzig asked in 1979 what are necessary and sufficient conditions for a __d__‐regular simple graph to admit a decomposition into paths of length __d__ for odd __d__>3. For cubic graphs, the existence of a 1‐factor is both necessary and sufficient. Even more, each 1‐factor is extendable

P4-decompositions of regular graphs
P4-decompositions of regular graphs
✍ Heinrich, Katherine; Liu, Jiping; Yu, Minli 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 246 KB 👁 1 views

In this article, we show that every simple r-regular graph G admits a balanced P 4 -decomposition if r ≡ 0(mod 3) and G has no cut-edge when r is odd. We also show that a connected 4-regular graph G admits a P 4 -decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degr

Regular bipartite graphs are antimagic
Regular bipartite graphs are antimagic
✍ Daniel W. Cranston 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 94 KB

## Abstract A labeling of a graph __G__ is a bijection from __E__(__G__) to the set {1, 2,… |__E__(__G__)|}. A labeling is __antimagic__ if for any distinct vertices __u__ and __v__, the sum of the labels on edges incident to __u__ is different from the sum of the labels on edges incident to __v__.

Tails of Bipartite Distance-regular Grap
Tails of Bipartite Distance-regular Graphs
✍ Michael S. Lang 📂 Article 📅 2002 🏛 Elsevier Science 🌐 English ⚖ 205 KB

Let denote a bipartite distance-regular graph with diameter D ≥ 4 and valency k ≥ 3. Let θ 0 > θ 1 > • • • > θ D denote the eigenvalues of and let E 0 , E 1 , . . . , E D denote the associated primitive idempotents. Fix s (1 ≤ s ≤ D -1) and abbreviate E := E s . We say E is a tail whenever the entry

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