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
JournalAmerican Mathematical Monthly
Volume126
Issue number8
DOIs
Publication statusPublished - 19 Sep 2019

Cite this

Knox, Fiachra ; Mohar, Bojan ; Wood, David R. / A Golden Ratio Inequality for Vertex Degrees of Graphs. In: American Mathematical Monthly. 2019 ; Vol. 126, No. 8. pp. 742-747.
@article{565845289b0e4abebc1867fa914fdd4a,
title = "A Golden Ratio Inequality for Vertex Degrees of Graphs",
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.",
author = "Fiachra Knox and Bojan Mohar and Wood, {David R.}",
year = "2019",
month = "9",
day = "19",
doi = "10.1080/00029890.2019.1627153",
language = "English",
volume = "126",
pages = "742--747",
journal = "American Mathematical Monthly",
issn = "0002-9890",
publisher = "Mathematical Association of America",
number = "8",

}

A Golden Ratio Inequality for Vertex Degrees of Graphs. / Knox, Fiachra; Mohar, Bojan; Wood, David R.

In: American Mathematical Monthly, Vol. 126, No. 8, 19.09.2019, p. 742-747.

Research output: Contribution to journalArticleResearchpeer-review

TY - JOUR

T1 - A Golden Ratio Inequality for Vertex Degrees of Graphs

AU - Knox, Fiachra

AU - Mohar, Bojan

AU - Wood, David R.

PY - 2019/9/19

Y1 - 2019/9/19

N2 - 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.

AB - 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.

UR - http://www.scopus.com/inward/record.url?scp=85073261928&partnerID=8YFLogxK

U2 - 10.1080/00029890.2019.1627153

DO - 10.1080/00029890.2019.1627153

M3 - Article

VL - 126

SP - 742

EP - 747

JO - American Mathematical Monthly

JF - American Mathematical Monthly

SN - 0002-9890

IS - 8

ER -