Geodesic
On the Zeros of Some Genus Polynomials
Canadian journal of mathematics, Tome 49 (1997) no. 3, pp. 617-640

Voir la notice de l'article provenant de la source Cambridge University Press

In the genus polynomial of the graph G, the coefficient of xk is the number of distinct embeddings of the graph G on the oriented surface of genus k. It is shown that for several infinite families of graphs all the zeros of the genus polynomial are real and negative. This implies that their coefficients, which constitute the genus distribution of the graph, are log concave and therefore also unimodal. The geometric distribution of the zeros of some of these polynomials is also investigated and some new genus polynomials are presented.
DOI : 10.4153/CJM-1997-029-5
Mots-clés : 05C10, 05A15, 30C15, 26C10 
Stahl, Saul. On the Zeros of Some Genus Polynomials. Canadian journal of mathematics, Tome 49 (1997) no. 3, pp. 617-640. doi: 10.4153/CJM-1997-029-5
@article{10_4153_CJM_1997_029_5,
     author = {Stahl, Saul},
     title = {On the {Zeros} of {Some} {Genus} {Polynomials}},
     journal = {Canadian journal of mathematics},
     pages = {617--640},
     year = {1997},
     volume = {49},
     number = {3},
     doi = {10.4153/CJM-1997-029-5},
     url = {http://geodesic.mathdoc.fr/articles/10.4153/CJM-1997-029-5/}
}
TY  - JOUR
AU  - Stahl, Saul
TI  - On the Zeros of Some Genus Polynomials
JO  - Canadian journal of mathematics
PY  - 1997
SP  - 617
EP  - 640
VL  - 49
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.4153/CJM-1997-029-5/
DO  - 10.4153/CJM-1997-029-5
ID  - 10_4153_CJM_1997_029_5
ER  - 
%0 Journal Article
%A Stahl, Saul
%T On the Zeros of Some Genus Polynomials
%J Canadian journal of mathematics
%D 1997
%P 617-640
%V 49
%N 3
%U http://geodesic.mathdoc.fr/articles/10.4153/CJM-1997-029-5/
%R 10.4153/CJM-1997-029-5
%F 10_4153_CJM_1997_029_5

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

[2] 2. Archdeacon, D., The orientable genus is nonadditive, J. Graph Theory 10(1986), 385–402. Google Scholar

[3] 3. Archdeacon, D., The nonorientable genus is additive, J. Graph Theory 10(1986), 363–384. Google Scholar

[4] 4. Brenti, F., Royle, G.F. and Wagner, D.G., Location of zeros of chromatic and related polynomials of graphs, Canad. J. Math. 46(1994), 55-80. Google Scholar

[5] 5. Comtet, L., Advanced combinatorics, Reidel Publ. Co. Boston, 1974. Google Scholar

[6] 6. Cori, R., Machi, A., Penaud, J.G. and Vauquelin, B., On the automorphism group of a planar hypermap, European J. Combin. 2(1981), 331–334. Google Scholar

[7] 7. Duke, R.A., The genus, regional number, and Betti number of a graph, Canad. J.Math. 134(1966), 817–822. Google Scholar

[8] 8. Furst, M.L., Gross, J.L. and Statman, R., Genus distributions of two classes of graphs, J. Combinatorial Theory (B) 46(1989), 22–36. Google Scholar

[9] 9. Gross, J.L., Robbins, D.P. and Tucker, T., Genus distributions for bouquets of circles, J. Combin. Theory Ser. B 47(1989), 292–306. Google Scholar

[10] 10. Gross, J.L. and Tucker, T., Topological graph theory, Wiley-Interscience, New York, 1987. Google Scholar

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

[12] 12. Harer, J. and Zagier, D., The Euler characteristics of the moduli space of curves, Invent. Math. 85(1986), 457–485. Google Scholar

[13] 13. Heilman, O.J. and Lieb, E.H., Theory of monomer-dimer systems, Commun. Math. Phys. 25(1972), 190– 232. Google Scholar

[14] 14. Jackson, D.M., Counting cycles in permutations by group characters, with applications to a topological problem, Trans.Amer.Math. Soc. 299(1987), 785–801. Google Scholar

[15] 15. Keilson, J. and Gerber, H., Some results for discrete unimodality, J. Amer. Statist. Assoc. 66(1971), 386–389. Google Scholar

[16] 16. McGeoch, L.A., Genus distributions for circular and Möbius ladders, manuscript. Google Scholar

[17] 17. Rieper, R.G., Doctoral dissertation, Western Mischigan University, August 1987. Google Scholar

[18] 18. Stahl, S., Permutation-partition pairs: A combinatorial generalization of graph embeddings, Trans. Amer. Math. Soc. 259(1980), 129–145. Google Scholar

[19] 19. Stahl, S., Permuttion-partition pairs III: Embedding distributions of linear families of graphs, J. Combin. Theory Ser. B 52(1991), 191–218. Google Scholar

[20] 20. Stahl, S., On the number of maximum genus embeddings of almost all graphs, European J. Combin. 13(1992), 119–126. Google Scholar

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

[22] 22. Stahl, S., A combinatorial analog of the Jordan Curve Theorem, J. Combin. Theory Ser. B 35(1983), 28–38. Google Scholar

[23] 23. Stahl, S., A duality for permutations, Discrete Math. 71(1988), 257–271. Google Scholar

[24] 24. Stanley, R.P., Log-concave and unimodal sequences in algebra, combinatorics, and geometry, In: Graph Theory and its Applications: East and West, Ann. New York Acad. Sci. 576(1986), 500–535. Google Scholar

[25] 25. Wagner, D.G., The partition polynomial of a finite set system, J. Combin. Theory Ser.A 56(1991), 138–159. Google Scholar

[26] 26. Wagner, D.G., Total positivity of Hadamard products, J. Math. Anal. Appl. 163(1992), 459–483. Google Scholar

[27] 27. Walkup, D.W., How many ways can a permutation be factored into two n-cycles, ? DiscreteMath. 28(1979), 315–319. Google Scholar

Cité par Sources :