A characterization of upper-embeddable graphs
HTML articles powered by AMS MathViewer
- by Mark Jungerman
- Trans. Amer. Math. Soc. 241 (1978), 401-406
- DOI: https://doi.org/10.1090/S0002-9947-1978-0492309-3
- PDF | Request permission
Abstract:
It is proved that a pseudograph G is upper-embeddable if and only if it has a spanning tree T such that G - T has at most one component with an odd number of edges. This result is then used to show that all 4-edge connected graphs are upper-embeddable.References
- J. Edmonds, A combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc. 7 (1960), A646.
- Sukhamay Kundu, Bounds on the number of disjoint spanning trees, J. Combinatorial Theory Ser. B 17 (1974), 199–203. MR 369117, DOI 10.1016/0095-8956(74)90087-2
- E. A. Nordhaus, B. M. Stewart, and A. T. White, On the maximum genus of a graph, J. Combinatorial Theory Ser. B 11 (1971), 258–267. MR 286713, DOI 10.1016/0095-8956(71)90036-0 R. Ringeisen, The maximum genus of a graph, Ph.D. Thesis, Michigan State Univ., 1970. —, Upper and lower embeddable graphs, Graph Theory and Applications, Lecture Notes in Math., vol. 303, Springer-Verlag, Berlin and New York, 1972.
- Richard D. Ringeisen, Determining all compact orientable $2$-manifolds upon which $K_{m,\,n}$ has $2$-cell imbeddings, J. Combinatorial Theory Ser. B 12 (1972), 101–104. MR 295969, DOI 10.1016/0095-8956(72)90014-7
- Gerhard Ringel, The combinatorial map color theorem, J. Graph Theory 1 (1977), no. 2, 141–155. MR 444509, DOI 10.1002/jgt.3190010210
Bibliographic Information
- © Copyright 1978 American Mathematical Society
- Journal: Trans. Amer. Math. Soc. 241 (1978), 401-406
- MSC: Primary 05C10; Secondary 05C40
- DOI: https://doi.org/10.1090/S0002-9947-1978-0492309-3
- MathSciNet review: 492309