Edge and vertex operations on upper embeddable graphs. (English) Zbl 0858.05039

A connected graph \(G\) is upper embeddable if the maximum genus of \(G\) is equal to \(\lfloor(|E(G)|-|V(G)|+1)/2\rfloor\). The authors investigate the question of how adding or deleting an edge (or adding one or several vertices) affects upper embeddability. As a consequence, several new classes of upper embeddable graphs are constructed.


05C10 Planar graphs; geometric and topological aspects of graph theory
Full Text: EuDML


[1] BEHZAD M.-CHARTRAD G.-LESNIAK-FOSTER L.: Graphs and Digraphs. Prindle, Weber and Schmidt, Boston, 1979.
[2] FU H. L.-TSAI M. C.: The maximum genus of diameter three graphs. Preprint. · Zbl 0862.05027
[3] JUNGERMAN M.: A characterization of upper embeddable graphs. Trans. Amer. Math. Soc. 241 (1978), 401-406. · Zbl 0379.05025
[4] KUNDU S.: Bounds on the number of disjoint spanning trees. J. Combin. Theory Ser. B 17 (1974), 199-203. · Zbl 0285.05113
[5] NEBESKÝ L.: A new characterization of the maximum genus of a graph. Czechoslovak Math. J. 31(106) (1981), 604-613. · Zbl 0482.05034
[6] NEBESKÝ L.: A note on upper embeddable graphs. Czechoslovak Math. J. 33(108) (1983), 37-40. · Zbl 0518.05029
[7] NEBESKÝ L.: On 2-cell embeddings of graphs with minimum numbers of regions. Czechoslovak Math. J. 35(110) (1985), 625-631. · Zbl 0586.05015
[8] NEDELA R.-ŠKOVIERA M.: The maximum genus of a graph and doubly Eulerian trails. Boll Un. Mat. Ital. B (7) 4 (1990), 541-551. · Zbl 0715.05018
[9] ŠKOVIERA.-M.: The maximum genus of graphs of diameter two. Discrete Math. 87 (1991), 175-180. · Zbl 0724.05021
[10] XUONG N. H.: How to determine the maximum genus of a graph. J. Combin. Theory Ser. B 26 (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.