Embedding Distributions of Generalized Fan Graphs

Chen, Yichao ; Mansour, Toufik ; Zou, Qian

Canadian mathematical bulletin, Tome 56 (2013) no. 2, pp. 265-271

Résumé

Total embedding distributions have been known for a few classes of graphs. Chen, Gross, and Rieper computed it for necklaces, close-end ladders and cobblestone paths. Kwak and Shim computed it for bouquets of circles and dipoles. In this paper, a splitting theorem is generalized and the embedding distributions of generalized fan graphs are obtained

Détail

DOI : 10.4153/CMB-2011-176-6

Mots-clés : 05C10, total embedding distribution, splitting theorem, generalized fan graphs

Bibliographie

[1] [1] Archdeacon, D., Calculations on the average genus and genus distribution of graphs. Congr. Numer. 67(1988), 114–124. Google Scholar

[2] [2] Chen, J., Gross, J. L., and Rieper, R. G., Overlap matrices and total imbedding distributions. Discrete Math. 128(1994), no. 1-3, 73–94. Google Scholar | DOI

[3] [3] Y. Chen, A note on a conjecture of S. Stahl. Canad. J. Math. 60(2008), no. 4, 958–959. Google Scholar | DOI

[4] [4] Chen, J., Gross, J. L., and Rieper, R. G., Lower bounds for the average genus of a CF-graph. Electron. J. Combin. 17(2010), no. 1, Research Paper 150. Google Scholar

[5] [5] Chen, Y., Liu, Y. P., and Wang, T., The total embedding distributions of cacti and necklaces. Acta Math. Sin. 22(2006), no. 5, 1583–1590. Google Scholar | DOI

[6] [6] Chen, Y. and Liu, Y. P., On a conjecture of S. Stahl. Canad. J. Math. 62(2010), no. 5, 1058–1059. Google Scholar | DOI

[7] [7] Edmonds, J., A combinatorial representation for polyhedral surfaces. Notices Amer. Math. Soc. 7(1960), 646. Google Scholar

[8] [8] Furst, M., Gross, J. L., and Statman, R., Genus distributions for two first classes of graphs. J. Combin. Theory Ser. B 46(1989), no. 1, 22–36. Google Scholar | DOI

[9] [9] Gross, J. L., Genus distribution of graphs under surgery: adding edges and splitting vertices. New York J. Math. 16(2010), 161–178. Google Scholar

[10] [10] Gross, J. L. and Furst, M. L., Hierarchy for imbedding-distribution invariants of a graph. J. Graph Theory 11(1987), no. 2, 205–220. Google Scholar | DOI

[11] [11] Gross, J. L., Khan, I. F., and Poshni, M. I., Genus distribution of graph amalgamations: pasting at root-vertices. Ars Combin. 94(2010), 33–53. Google Scholar

[12] [12] Gross, J. L., Robbins, D. P., and Tucker, T.W., Genus distributions for bouquets of circles. J. Combin. Theory (B) 47(1989), no. 3, 292–306. Google Scholar | DOI

[13] [13] Gross, J. L. and Tucker, T.W., Topological Graph Theory. Dover Publications, Dover, Moneola, NY, 2001. Google Scholar

[14] [14] Hao, R. X. and Liu, Y. P., The genus distributions of directed antiladders in orientable surfaces. Appl Math Lett. 21(2008), no. 2, 161–164. Google Scholar | DOI

[15] [15] Jackson, D. M., Counting cycles in permutations by group characters, with an application to a topological problem. Trans. Amer. Math. Soc. 299(1987), no. 2, 785–801. Google Scholar | DOI

[16] [16] Jackson, D. M. and Visentin, T. I., A character-theoretic approach to embeddings of rooted maps in an orientable surface of given genus. Trans. Amer. Math. Soc. 322(1990), no. 1, 343–363. Google Scholar | DOI

[17] [17] Jackson, D. M. and Visentin, T. I., An Atlas of the Smaller Maps in Orientable and Nonorientable Surfaces. Chapman and Hall/CRC, Boca Raton, FL, 2001. Google Scholar

[18] [18] Khan, I. F., Poshni, M. I., and Gross, J. L., Genus distribution of graph amalgamations: Pasting when one root has arbitrary degree. Ars Math. Contemporanea 3(2010), no. 2, 121–138. Google Scholar

[19] [19] Korzhik, V. P. and Voss, H.-J., Exponential families of non-isomorphic non-triangular orientable genus embeddings of complete graphs. J. Combin. Theory Ser. B 86(2002), no. 1, 186–211. Google Scholar | DOI

[20] [20] Kwak, J. H. and Lee, J., Genus polynomials of dipoles. Kyungpook Math. J. 33(1993), no. 1, 115–125. Google Scholar

[21] [21] Kwak, J. H. and Lee, J., Enumeration of graph embeddings. Discrete Math. 135(1994), no. 1-3, 129–151. Google Scholar | DOI

[22] [22] Kwak, J. H. and Shim, S. H., Total embedding distributions for bouquets of circles. Discrete Math. 248(2002), no. 1-3, 93–108. Google Scholar | DOI

[23] [23] McGeoch, L. A., Algorithms for two graph problems: computing maximum-genus imbedding and the two-server problem. Ph.D. dissertation, Carnegie-Mellon University, 1987. Google Scholar

[24] [24] Mohar, B., An obstruction to embedding graphs in surface. Discrete Math. 78(1989), no. 1-2, 135–142. Google Scholar | DOI

[25] [25] Mohar, B. and Thomassen, C., Graphs on Surfaces. Johns Hopkins University Press, Baltimore, MD, 2001. Google Scholar

[26] [26] Mull, B. P., Enumerating the orientable 2-cell imbeddings of complete bipartite graphs. J. Graph Theory 30(1999), no. 2, 77–90. Google Scholar | DOI

[27] [27] Poshni, M. I., Khan, I. F., and Gross, J. L., Genus distributions of graphs under edge-amalgamations. Ars Math. Contemp. 3(2010), no. 1, 69–86. Google Scholar

[28] [28] Rieper, R. G., The Enumeration of Graph Imbeddings. Ph.D. dissertation, Western Michigan University, 1990. Google Scholar

[29] [29] Ringel, G., Map Color Theorem. Die Grundlehren der mathematischenWissenschaften 209. Springer-Verlag, New York, 1974. Google Scholar

[30] [30] Stahl, S., Generalized embedding schemes. J. Graph Theory 2(1978), no. 1, 41–52. Google Scholar | DOI

[31] [31] Stahl, S., Region distributions of graph embeddings and Stirling numbers. Discrete Math. 82(1990), no. 1, 57–78. Google Scholar | DOI

[32] [32] Stahl, S., Permutation-partition pairs. III: Embedding distributions of linear families of graphs. J. Combin. Theory Ser. B 52(1991), no. 2, 191–218. Google Scholar | DOI

[33] [33] Stahl, S., Region distributions of some small diameter graphs. Discrete Math. 89(1991), no. 3, 281–299. Google Scholar | DOI

[34] [34] Stahl, S., On the zeros of some genus polynomials. Canad. J. Math. 49(1997), no. 3, 617–640. Google Scholar | DOI

[35] [35] Tesar, E. H., Genus distribution of Ringel ladders. Discrete Math. 216(2000), no. 1-3, 235–252. Google Scholar | DOI

[36] [36] Visentin, T. I. and S.W.Wieler, On the genus distribution of (p; q; n)-dipoles. Electronic J. Combin. 14(2007), no. 1, Research Paper 12. Google Scholar

[37] [37] Wan, L. X. and Liu, Y. P., Orientable embedding genus distribution for certain types of graphs. J. Combin. Theory Ser. B 98(2008), no. 1, 19–32. Google Scholar | DOI

[38] [38] White, A. T., Graphs of Groups on Surfaces. Interactions and Models. North-Holland Mathematics Studies,188. North-Holland, Amsterdam, 2001. Google Scholar

[39] [39] Yang, Y. and Liu, Y. P., Classification of (p; q; n)-dipoles on nonorientable surfaces. Electron. J. Combin. 17(2010), no. 1, Note 12. Google Scholar