A note on the maximum number of edges of nonflowerable coin graphs

DOI10.1137/100796078MaRDI QIDQ3225149zbMATH OpenOpenAlexFDO

Authors Geir Agnarsson, Jill Bigley Dunham

Publication date 15 March 2012

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/0909.4315

zbMATH Keywords

coin graphflowerinteger programmingplanar graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35)

Abstract: For $ninats$ and $3leqkleqn$ we compute the exact value of $E_k(n)$, the maximum number of edges of a simple planar graph on $n$ vertices where each vertex bounds an $ell$-gon where $ellgeqk$. The lower bound of $E_k(n)$ is obtained by explicit construction, and the matching upper bound is obtained by using Integer Programming (IP.) We then use this result to conjecture the maximum number of edges of a non-flowerable coin graph on $n$ vertices. A {em flower} is a coin graph representation of the wheel graph. A collection of coins or discs in the Euclidean plane is {em non-flowerable} if no flower can be formed by coins from the collection.

Recommendations

• scientific article; zbMATH DE number 903282
• Bounding the number of edges of matchstick graphs
• On rational radii coin representations of the wheel graph
• The number of edges in a maximum cycle-distributed graph

Cited in

(1)

• On rational radii coin representations of the wheel graph

This page was built for publication: A note on the maximum number of edges of nonflowerable coin graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3225149)