A Golden Ratio Inequality for Vertex Degrees of Graphs

Fiachra Knox, Bojan Mohar, David R. Wood

Research output: Contribution to journalArticleResearchpeer-review

Abstract

Motivated by the study of the crossing number of graphs, it is shown that, for trees, the sum of the products of the degrees of the end-vertices of all edges has an upper bound in terms of the sum of all vertex degrees to the power of ϕ2, where ϕ is the golden ratio. The exponent ϕ2 is best possible. This inequality is generalized for all graphs with bounded maximum average degree.

Original languageEnglish
Pages (from-to)742-747
Number of pages6
JournalThe American Mathematical Monthly
Volume126
Issue number8
DOIs
Publication statusPublished - 19 Sep 2019

Cite this