Independence numbers of polyhedral graphs

2022/12/29 by Sébastien Gaspoz, Gaspoz, Sébastien, Riccardo W. Maffucci +1
Computer Science · #05C10 #05C35 #05C69 #52B05 #Advanced Graph Theory Research #Combinatorics (math.CO) #Computational Geometry and Mesh Generation #FOS: Mathematics #Optimization and Search Problems

paper · pdf · doi:10.48550/arxiv.2212.14323

openalex publication_date 2022/12/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

A polyhedral graph is a 3-connected planar graph. We find the least possible order p(k,a) of a polyhedral graph containing a k-independent set of size a for all positive integers k and a. In the case k = 1 and a even, we prove that the extremal graphs are exactly the vertex-face (radial) graphs of maximal planar graphs.

Related

• On the d-independence number in 1-planar graphs
• Sharp upper bounds on the k-independence number in graphs with given minimum and maximum degree
• Regular independent sets
• Triangle-free planar graphs with small independence number
• Relating the independence number and the dissociation number