A Note on the Maximum Number of Edges of Nonflowerable Coin Graphs
Geir Agnarsson, Jill Bigley Dunham · SIAM Journal on Discrete Mathematics · 2011
For $n\in\mathbb{N}$ and $4\leq k\leq n$ we compute the exact value of $E_k(n)$, the maximum number of edges of a simple plane graph on n vertices, where each vertex bounds an $\ell$-gon where $\ell\geq k$. The lower bound of $E_k(n)$ is obtained by explicit construction, while the matching upper bound is obtained by solving an integer program by inspection/picture. We then use this result to conjecture the maximum number of edges of a nonflowerable coin graph on n vertices. A flower is a coin graph representation of the wheel graph. A collection of coins or discs in the Euclidean plane is nonflowerable if no flower can be formed by coins from the collection.