zbMATH — the first resource for mathematics

On isopart parameters of complete bipartite graphs and n-cubes. (English) Zbl 0585.05027
A graph H is said to be G-decomposable if H can be decomposed into the subgraphs \(H_ 1,H_ 2,...,H_ n\) such that they are all isomorphic to G. Fink introduced three ”isopart parameters”, \(p_ 0(G)\), \(r_ 0(G)\), and \(f_ 0(G)\). The numbers \(p_ 0(G)\) and \(r_ 0(G)\) are respectively the minimum order and minimum degree of regularity among all connected, regular, G-decomposable graphs. The parameter \(f_ 0(G)\) is the smallest number t (\(\geq 2)\) for which there exists a connected regular graph H decomposable into t copies of G. The authors determine the three parameters for all complete bipartite graphs and the n-cube.
Reviewer: Z.Ma
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C99 Graph theory
Full Text: EuDML
[1] BEHZAD M., CHARTRAND G., LESNIAK-FOSTER L.: Graphs & Digraphs. Wadsworth International, Belmont, CA, 1979. · Zbl 0403.05027
[2] FINK J. F.: Every graph is an induced isopart of a connected regular graph. Submitted for publication. · Zbl 0614.05052
[3] FINK J. F.: On smallest regular graphs with a given isopart. Submitted for publication. · Zbl 0607.05039
[4] FINK J. F., RUIZ S.: Every graph is an induced isopart of a circulant. Submitted for publication. · Zbl 0614.05052
[5] KÖNIG D.: Über Graphen und ihre Anwendung auf Determinantentheorie and Mengenlehre. Math. Ann. 77, 1916, 453-465. · JFM 46.0146.03
[6] PETERSEN J.: Die Theorie der regularen Graphen. Acta Math. 15, 1891, 193-220. · JFM 23.0115.03
[7] REISS M.: Über eine Steinersche kombinatorische Aufgabe. J. reine u. ang. Mathematik 56,1859, 326-344.
[8] WILSON R. M.: Decompositions of complete graphs into subgraphs isomorphic to a given graph. Proceedings of the Fifth British Combinatorial Conference (Univ. Aberdeen, Aberdeen, 1975) 647-659. Congressus Numerantium, 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.