Publications Meetings The Profession Membership Programs Math Samplings Policy & Advocacy In the News About the AMS
   
Mobile Device Pairing
Green Open Access
Transactions of the American Mathematical Society
Transactions of the American Mathematical Society
ISSN 1088-6850(online) ISSN 0002-9947(print)

A characterization of upper-embeddable graphs


Author: Mark Jungerman
Journal: Trans. Amer. Math. Soc. 241 (1978), 401-406
MSC: Primary 05C10; Secondary 05C40
MathSciNet review: 492309
Full-text PDF Free Access

Abstract | References | Similar Articles | Additional Information

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 [Enhancements On Off] (What's this?)

  • [1] J. Edmonds, A combinatorial representation for polyhedral surfaces, Notices Amer. Math. Soc. 7 (1960), A646.
  • [2] Sukhamay Kundu, Bounds on the number of disjoint spanning trees, J. Combinatorial Theory Ser. B 17 (1974), 199–203. MR 0369117 (51 #5353)
  • [3] 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 0286713 (44 #3922)
  • [4] R. Ringeisen, The maximum genus of a graph, Ph.D. Thesis, Michigan State Univ., 1970.
  • [5] -, Upper and lower embeddable graphs, Graph Theory and Applications, Lecture Notes in Math., vol. 303, Springer-Verlag, Berlin and New York, 1972.
  • [6] Richard D. Ringeisen, Determining all compact orientable 2-manifolds upon which 𝐾_{𝑚,𝑛} has 2-cell imbeddings, J. Combinatorial Theory Ser. B 12 (1972), 101–104. MR 0295969 (45 #5030)
  • [7] Gerhard Ringel, The combinatorial map color theorem, J. Graph Theory 1 (1977), no. 2, 141–155. MR 0444509 (56 #2860)

Similar Articles

Retrieve articles in Transactions of the American Mathematical Society with MSC: 05C10, 05C40

Retrieve articles in all journals with MSC: 05C10, 05C40


Additional Information

DOI: http://dx.doi.org/10.1090/S0002-9947-1978-0492309-3
PII: S 0002-9947(1978)0492309-3
Keywords: Maximum genus, upper-embeddable graph, spanning tree, edge-connectivity
Article copyright: © Copyright 1978 American Mathematical Society