Decompositions of regular bipartite graphs

Michael S. Jacobson; Miroslaw Truszczyński; Zsolt Tuza

doi:10.1016/0012-365X(91)90396-J

Decompositions of regular bipartite graphs

Michael S. Jacobson, Miroslaw Truszczyński, Zsolt Tuza

Computer Science

Research output: Contribution to journal › Article › peer-review

21 Scopus citations

Abstract

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 P₄.

Original language	English
Pages (from-to)	17-27
Number of pages	11
Journal	Discrete Mathematics
Volume	89
Issue number	1
DOIs	https://doi.org/10.1016/0012-365X(91)90396-J
State	Published - May 3 1991

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Access to Document

10.1016/0012-365X(91)90396-J

Cite this

@article{a23fa24882ac4033abb4a28d22d5c2b6,

title = "Decompositions of regular bipartite graphs",

abstract = "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 P4.",

author = "Jacobson, {Michael S.} and Miroslaw Truszczy{\'n}ski and Zsolt Tuza",

year = "1991",

month = may,

day = "3",

doi = "10.1016/0012-365X(91)90396-J",

language = "English",

volume = "89",

pages = "17--27",

number = "1",

}

TY - JOUR

T1 - Decompositions of regular bipartite graphs

AU - Jacobson, Michael S.

AU - Truszczyński, Miroslaw

AU - Tuza, Zsolt

PY - 1991/5/3

Y1 - 1991/5/3

N2 - 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 P4.

AB - 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 P4.

UR - http://www.scopus.com/inward/record.url?scp=0039126623&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0039126623&partnerID=8YFLogxK

U2 - 10.1016/0012-365X(91)90396-J

DO - 10.1016/0012-365X(91)90396-J

M3 - Article

AN - SCOPUS:0039126623

VL - 89

SP - 17

EP - 27

IS - 1

ER -

Decompositions of regular bipartite graphs

Abstract

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this