Hostname: page-component-586b7cd67f-t7czq Total loading time: 0 Render date: 2024-11-25T08:16:35.321Z Has data issue: false hasContentIssue false
  • English
  • Français

Embedding Distributions of Generalized Fan Graphs

Published online by Cambridge University Press:  20 November 2018

Yichao Chen ,
Toufik Mansour  and
Qian Zou
Yichao Chen
Affiliation:
Mathematics Department, Hunan University, Changsha, 410082, PR China e-mail: [email protected]
Toufik Mansour
Affiliation:
Department of Mathematics, University of Haifa, Haifa, 31905, Israel e-mail: [email protected]
Qian Zou
Affiliation:
Mathematics Department, Hunan University, Changsha, 410082, PR China e-mail: joe [email protected]
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

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

Keywords

05C10total embedding distributionsplitting theoremgeneralized fan graphs
Type
Research Article
Information
Canadian Mathematical Bulletin , Volume 56 , Issue 2 , 01 June 2013 , pp. 265 - 271
Copyright
Copyright © Canadian Mathematical Society 2013

References

[1] Archdeacon, D., Calculations on the average genus and genus distribution of graphs. Congr. Numer. 67(1988), 114–124. Google Scholar
[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. http://dx.doi.org/10.1016/0012-365X(94)90105-8 Google Scholar
[3] Y. Chen, A note on a conjecture of S. Stahl. Canad. J. Math. 60(2008), no. 4, 958–959. http://dx.doi.org/10.4153/CJM-2008-040-2 Google Scholar
[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] 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. http://dx.doi.org/10.1007/s10114-005-0856-2 Google Scholar
[6] Chen, Y. and Liu, Y. P., On a conjecture of S. Stahl. Canad. J. Math. 62(2010), no. 5, 1058–1059. http://dx.doi.org/10.4153/CJM-2010-058-4 Google Scholar
[7] Edmonds, J., A combinatorial representation for polyhedral surfaces. Notices Amer. Math. Soc. 7(1960), 646.Google Scholar
[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. http://dx.doi.org/10.1016/0095-8956(8990004-X Google Scholar
[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] Gross, J. L. and Furst, M. L., Hierarchy for imbedding-distribution invariants of a graph. J. Graph Theory 11(1987), no. 2, 205–220. http://dx.doi.org/10.1002/jgt.3190110211 Google Scholar
[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] 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. http://dx.doi.org/10.1016/0095-8956(89)90030-0 Google Scholar
[13] Gross, J. L. and Tucker, T.W., Topological Graph Theory. Dover Publications, Dover, Moneola, NY, 2001.Google Scholar
[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. http://dx.doi.org/10.1016/j.aml.2007.05.001 Google Scholar
[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. http://dx.doi.org/10.1090/S0002-9947-1987-0869231-9 Google Scholar
[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. http://dx.doi.org/10.2307/2001535 Google Scholar
[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] 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] 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. http://dx.doi.org/10.1006/jctb.2002.2122 Google Scholar
[20] Kwak, J. H. and Lee, J., Genus polynomials of dipoles. Kyungpook Math. J. 33(1993), no. 1, 115–125. Google Scholar
[21] Kwak, J. H. and Lee, J., Enumeration of graph embeddings. Discrete Math. 135(1994), no. 1-3, 129–151. http://dx.doi.org/10.1016/0012-365X(93)E0075-F Google Scholar
[22] Kwak, J. H. and Shim, S. H., Total embedding distributions for bouquets of circles. Discrete Math. 248(2002), no. 1-3, 93–108. http://dx.doi.org/10.1016/S0012-365X(01)00187-X Google Scholar
[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] Mohar, B., An obstruction to embedding graphs in surface. Discrete Math. 78(1989), no. 1-2, 135–142. http://dx.doi.org/10.1016/0012-365X(89)90170-2 Google Scholar
[25] Mohar, B. and Thomassen, C., Graphs on Surfaces. Johns Hopkins University Press, Baltimore, MD, 2001.Google Scholar
[26] Mull, B. P., Enumerating the orientable 2-cell imbeddings of complete bipartite graphs. J. Graph Theory 30(1999), no. 2, 77–90. http://dx.doi.org/10.1002/(SICI)1097-0118(199902)30:2h77::AID-JGT2i3.0.CO;2-W Google Scholar
[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] Rieper, R. G., The Enumeration of Graph Imbeddings. Ph.D. dissertation, Western Michigan University, 1990.Google Scholar
[29] Ringel, G., Map Color Theorem. Die Grundlehren der mathematischenWissenschaften 209. Springer-Verlag, New York, 1974.Google Scholar
[30] Stahl, S., Generalized embedding schemes. J. Graph Theory 2(1978), no. 1, 41–52. http://dx.doi.org/10.1002/jgt.3190020106 Google Scholar
[31] Stahl, S., Region distributions of graph embeddings and Stirling numbers. Discrete Math. 82(1990), no. 1, 57–78. http://dx.doi.org/10.1016/0012-365X(90)90045-J Google Scholar
[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. http://dx.doi.org/10.1016/0095-8956(91)90062-O Google Scholar
[33] Stahl, S., Region distributions of some small diameter graphs. Discrete Math. 89(1991), no. 3, 281–299. http://dx.doi.org/10.1016/0012-365X(91)90121-H Google Scholar
[34] Stahl, S., On the zeros of some genus polynomials. Canad. J. Math. 49(1997), no. 3, 617–640. http://dx.doi.org/10.4153/CJM-1997-029-5 Google Scholar
[35] Tesar, E. H., Genus distribution of Ringel ladders. Discrete Math. 216(2000), no. 1-3, 235–252. http://dx.doi.org/10.1016/S0012-365X(99)00250-2 Google Scholar
[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] 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. http://dx.doi.org/10.1016/j.jctb.2007.04.002 Google Scholar
[38] White, A. T., Graphs of Groups on Surfaces. Interactions and Models. North-Holland Mathematics Studies,188. North-Holland, Amsterdam, 2001.Google Scholar
[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