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

Producción científica: Article › revisión exhaustiva

25 Citas (Scopus)

Resumen

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

Idioma original	English
Páginas (desde-hasta)	17-27
Número de páginas	11
Publicación	Discrete Mathematics
Volumen	89
N.º	1
DOI	https://doi.org/10.1016/0012-365X(91)90396-J
Estado	Published - may 3 1991

ASJC Scopus subject areas

Theoretical Computer Science
Discrete Mathematics and Combinatorics

Acceder al documento

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

Otros archivos y enlaces

Citar esto

@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 - https://www.scopus.com/pages/publications/0039126623

UR - https://www.scopus.com/pages/publications/0039126623#tab=citedBy

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

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

M3 - Article

AN - SCOPUS:0039126623

SN - 0012-365X

VL - 89

SP - 17

EP - 27

JO - Discrete Mathematics

JF - Discrete Mathematics

IS - 1

ER -

Decompositions of regular bipartite graphs

Resumen

ASJC Scopus subject areas

Acceder al documento

Otros archivos y enlaces

Huella

Citar esto