Decompositions of regular bipartite graphs. (English) Zbl 0754.05057

Summary: 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_ 4\).


05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C05 Trees
Full Text: DOI


[1] Bermond, J.C.; Wilson, R.J., Graceful graphs, radio antennae and French windmills, Graph theory and combinatorics, 18-37, (1979), London · Zbl 0447.05032
[2] Bialostocki, A., A strong factorization of the graph of the n-cube, Ars combin., 22, 78-80, (1986) · Zbl 0647.05046
[3] Bloom, G.S., A chronology of the ringel-kotzig conjecture and the continuing quest to call all trees graceful, (), 32-51 · Zbl 0465.05027
[4] Y. Caro, and Z. Tuza, Decompositions of partially ordered sets into chains and antichains of given size, Order, to appear. · Zbl 0665.06002
[5] Chung, F.R.K.; Graham, R.L., Recent results in graph decompositions, (), 103-124 · Zbl 0464.05046
[6] Kotzig, A., On certain valuations of finite graphs, Utilitas math., 4, 261-290, (1973) · Zbl 0277.05102
[7] Lonc, Z.; Trusczyński, M., Decomposition of large uniform hypergraphs, 1, 345-350, (1985), Order · Zbl 0558.05048
[8] Rosa, A.; Rosenstiehl, P., On certain valuations of the vertices of a graph, Theory of graphs, Rome, Proc. internat. symposium, 349-355, (1966)
[9] Wilson, R.W., Construction and uses of pairwise balanced designs, (), 18-41
[10] Wilson, R.W., Decompositions of complete graphs into subgraphs, Proc. Fifth British Combinatorial Conf., Aberdeen, 1975, Congr. numer., 15, (1976)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.