zbMATH — the first resource for mathematics

Upper embeddable factorizations of graphs. (English) Zbl 0583.05045
Let G be a graph (possibly with multiple edges and loops). A sequence \((G_ 1,\ldots,G_ n)\), where \(n\geq 1\), is referred to as an upper embeddable n-factorization of G if \(G_ 1,\ldots,G_ n\) are upper embeddable spanning subgraphs of G, and each edge of G belongs to exactly one of the graphs \(G_ 1,\ldots,G_ n\). The paper gives a necessary and sufficient condition for a graph to have an upper embeddable n- factorization (Theorem 2). The proof is partially based on a generalization of methods used by the author in his paper on the maximum genus of a graph [ibid. 31(106), 604-613 (1981; Zbl 0482.05034)].
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: EuDML
[1] M. Behzad G. Chartrand, and L. Lesniak-Foster: Graphs & Digraphs. Prindte, Weber & Schmidt, Boston 1979. · Zbl 0403.05027
[2] N. P. Homenko N. A. Ostroverkhy, and V. A. Kiismenko: The maximum genus of a graph. (in Ukrainian, English summary). \(\fi\)-peretvorennya grafiv (N. P. Homenko IM AN URSR, Kiev 1973, pp. 180-210.
[3] M. Jungerman: A characterization of upper embeddabie graphs. Trans. Amer. Math. Soc. 241 (1978), 401-406. · Zbl 0379.05025
[4] C. St. J. A. Nash-Williams: Edge-disjoint spanning trees of finite graphs. J. London Math, Soc. 36 (1961), 445-450. · Zbl 0102.38805
[5] L. Nebeský: A new characterization of the maximum genus of a graph. Czechoslovak Math. J. 31 (706) (1981), 604-613. · Zbl 0482.05034
[6] W. T. Tutte: On the problem of decomposing a graph into n connected factors. J. London Maih. Soc. 36 (1961), 221-230. · Zbl 0096.38001
[7] A. T. White: Graphs, Groups, and Surfaces. North-Holland, Amsterdam 1973. · Zbl 0268.05102
[8] N. H. Xuong: How to determine the maximum genus of a graph. J. Combinatorial Theory 26 B (1979), 217-225. · Zbl 0403.05035
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.