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.

**[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****[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****[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****[7]**Gerhard Ringel,*The combinatorial map color theorem*, J. Graph Theory**1**(1977), no. 2, 141–155. MR**0444509**

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

Keywords:
Maximum genus,
upper-embeddable graph,
spanning tree,
edge-connectivity

Article copyright:
© Copyright 1978
American Mathematical Society