The genera of amalgamations of graphs

Alpert, Seth R.

doi:10.1090/S0002-9947-1973-0371698-X

The genera of amalgamations of graphs
HTML articles powered by AMS MathViewer

by Seth R. Alpert PDF

Trans. Amer. Math. Soc. 178 (1973), 1-39 Request permission

Abstract:

If $p \leq m$, n then ${K_m}{ \vee _{{K_p}}}{K_n}$ is the graph obtained by identify ing a copy of ${K_p}$ contained in ${K_m}$ with a copy of ${K_p}$ contained in ${K_n}$ . It is shown that for all integers $p \leq m$, n the genus $g({K_m}{ \vee _{{K_p}}}{K_n})$ of ${K_m}{ \vee _{{K_p}}}{K_n}$ is less than or equal to $g({K_m}) + g({K_n})$. Combining this fact with the lower bound obtained from the Euler formula, one sees that for $2 \leq p \leq 5,g({K_m}{ \vee _{{K_p}}}{K_n})$ is either $g({K_m}) + g({K_n})$ or else $g({K_m}) + g({K_n}) - 1$. Except in a few special cases, it is determined which of these values is actually attained.

References

Joseph Battle, Frank Harary, Yukihiro Kodama, and J. W. T. Youngs, Additivity of the genus of a graph, Bull. Amer. Math. Soc. 68 (1962), 565–568. MR 155313, DOI 10.1090/S0002-9904-1962-10847-7
J. Ch. Boland, Embedding of graphs into orientable surfaces, Nederl. Akad. Wetensch. Proc. Ser. A 70=Indag. Math. 29 (1967), 33–44. MR 0211391, DOI 10.1016/S1385-7258(67)50005-7

A combinatorial representation for polyhedral surfaces

7

William Gustin, Orientable embedding of Cayley graphs, Bull. Amer. Math. Soc. 69 (1963), 272–275. MR 145506, DOI 10.1090/S0002-9904-1963-10952-0
Frank Harary, Graph theory, Addison-Wesley Publishing Co., Reading, Mass.-Menlo Park, Calif.-London 1969. MR 0256911, DOI 10.21236/AD0705364

The mapping of graphs on surfaces

16

Jean Mayer, Le problème des régions voisines sur les surfaces closes orientables, J. Combinatorial Theory 6 (1969), 177–195. MR 234863, DOI 10.1016/S0021-9800(69)80118-3
Gerhard Ringel, Färbungsprobleme auf Flächen und Graphen, Mathematische Monographien, vol. 2, VEB Deutscher Verlag der Wissenschaften, Berlin, 1959 (German). MR 0109349
Gerhard Ringel and J. W. T. Youngs, Lösung des Problems der Nachbargebiete, Arch. Math. (Basel) 20 (1969), 190–201 (German). MR 242720, DOI 10.1007/BF01899013
Gerhard Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem, Proc. Nat. Acad. Sci. U.S.A. 60 (1968), 438–445. MR 228378, DOI 10.1073/pnas.60.2.438
Gerhard Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem—Case 11, J. Combinatorial Theory 7 (1969), 71–93. MR 240006, DOI 10.1016/S0021-9800(69)80008-6
Gerhard Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem—case 2, J. Combinatorial Theory 7 (1969), 342–352. MR 265216, DOI 10.1016/S0021-9800(69)80061-X
Gerhard Ringel and J. W. T. Youngs, Solution of the Heawood map-coloring problem—case 8, J. Combinatorial Theory 7 (1969), 353–363. MR 262113, DOI 10.1016/S0021-9800(69)80062-1
C. M. Terry, L. R. Welch, and J. W. T. Youngs, The genus of $K_{12s}$, J. Combinatorial Theory 2 (1967), 43–60. MR 206939
C. M. Terry, L. R. Welch, and J. W. T. Youngs, Solution of the Heawood map-coloring problem—case $4$, J. Combinatorial Theory 8 (1970), 170–174. MR 258675, DOI 10.1016/S0021-9800(70)80074-6
J. W. T. Youngs, The Heawood map coloring conjecture, Graph Theory and Theoretical Physics, Academic Press, London, 1967, pp. 313–354. MR 0236059
J. W. T. Youngs, Minimal imbeddings and the genus of a graph, J. Math. Mech. 12 (1963), 303–315. MR 0145512
J. W. T. Youngs, Solution of the Heawood map-coloring problem—case $3,\,5,\,6$, and $9$, J. Combinatorial Theory 8 (1970), 175–219. MR 258676, DOI 10.1016/S0021-9800(70)80075-8
J. W. T. Youngs, The Heawood map-coloring problem—cases $1,\,7,\,$and$\,10$, J. Combinatorial Theory 8 (1970), 220–231. MR 258677, DOI 10.1016/S0021-9800(70)80076-X