zbMATH — the first resource for mathematics

On smallest regular graphs with a given isopart. (English) Zbl 0607.05039
A G-decomposition of a graph H is a family of subgraphs \(H_ 1,H_ 2,...,H_ n\) of H, whose edge-sets partition E(H), and such that each \(H_ i\) is isomorphic to G. G-decompositions have been studied by Bermond, Rosa, Schönheim, Harary, Wilson, and many others. Here the author asks for three extremal parameters related to G-decompositions: the least p (respectively r, respectively f) such that there exists a connected regular graph H which admits a G-decomposition and has p vertices (respectively degree r, respectively the G-decomposition has f subgraphs). After a fairly straightforward calculation of the parameters p, r, and f for complete graphs, cycles, and stars, the author studies the parameter r for an arbitrary tree T. If the maximum degree \(\Delta\) (T) is even, then \(r=\Delta (T)\). Otherwise r could be \(\Delta\) (T) or \(\Delta (T)+1\); when \(\Delta (T)=3\) the author characterizes those trees with \(r=3\).
Reviewer: P.Hell

05C35 Extremal problems in graph theory
05C05 Trees
Full Text: DOI
[1] , and , Graphs & Digraphs. Wadsworth International, Belmont, CA (1979).
[2] Every graph is an induced isopart of a connected regular graph. Submitted for publication. · Zbl 0614.05052
[3] and , Every graph is an induced isopart of a circulant. Submitted for publication. · Zbl 0614.05052
[4] Konig, Math. Ann. 77 pp 453– (1916)
[5] Petersen, Acta Math. 15 pp 193– (1891)
[6] Reiss, J. Reine Agnew. Math. 56 pp 326– (1859) · ERAM 056.1496cj
[7] On certain valuations of the vertices of a graph. Theory of Graphs (Internat. Sympos. Rome, 1966) 349–355. Gordon and Breach, New York; Dunod, Paris (1967).
[8] Decompositions of complete graphs into subgraphs isomorphic to a given graph. Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) 647–659. Congresses Numeratium, No. XV, Utilitas Math., Winnipeg, Man. (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.