Skip to main content
Springer Nature Link
Log in

Extending Kotzig’s theorem

  • Published:
Israel Journal of Mathematics Aims and scope Submit manuscript

Abstract

The weight of a graphG is the minimum sum of the two degrees of the end points of edges ofG. Kotzig proved that every graph triangulating the sphere has weight at most 13, and Grünbaum and Shephard proved that every graph triangulating the torus has weight at most 15. We extend these results for graphs, multigraphs and pseudographs “triangulating” the sphere withg handlesS g ,g≧1, showing that the corresponding weights are at most about\(\sqrt {48g} ,8g + 7\) and 24g−9, respectively; if a (multi, pseudo) graph triangulatesS g and it is big enough, then its weight is at most 15.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. B. Grünbaum,Convex Polytopes, Interscience, New York, 1967.

    MATH  Google Scholar 

  2. B. Grünbaum,New views on some old questions of combinatorial geometry, Colloq. Int. Teorie Combinatoire, Rome, 1973, Vol. 1, 1976, pp. 451–468.

    Google Scholar 

  3. B. Grünbaum,Polytopal graphs, inStudies in Graph Theory, part II (D. R. Fulkerson, ed.), Math. Assoc. of America Studies in Math., Vol. 12, 1975, p. 201.

  4. B. Grünbaum and G. C. Shephard,Analogues for tilings of Kotzig’s Theorem on minimal weights of graphs, inTheory and Practice of Combinatorics (A. Rosa, G. Sabidussi and J. Turgeon, eds.), Annals of Discrete Mathematics12 (1982), 129–140.

  5. E. Jucovič,Strengthening of a theorem about 3-polytopes, Geom. Dedic.3 (1974), 233–237.

    Article  Google Scholar 

  6. A. Kotzig,Príspevok k téorii eulerovských polyédrov, Mat.-Fyz. Časopis Slovensk Akad. Vied.5 (1955), 101–113 (in Slovak; Russian summary).

    MathSciNet  Google Scholar 

  7. A. Kotzig,Some open problems and recent results on extremal polyhedral graphs, Publication CRM-796 of C.R.M.A., University of Montreal, 1978; also in Proc. Second Int. Conf. on Combinatorial Mathematics, New York, 1978 (publ. in J. New York Acad. Sci.).

  8. G. Ringel and J. W. T. Young,Solution of the Heawood map coloring problem, Proc. Nat. Acad. Sci. U.S.A.60 (1968), 438–445.

    Article  MATH  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, University of Haifa, Haifa, Israel

    Joseph Zaks

Authors
  1. Joseph Zaks
    View author publications

    You can also search for this author inPubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Zaks, J. Extending Kotzig’s theorem. Israel J. Math. 45, 281–296 (1983). https://doi.org/10.1007/BF02804013

Download citation

  • Received:

  • Revised:

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02804013

Keywords