Independence numbers of polyhedral graphs

DOI10.1016/J.AMC.2023.128349MaRDI QIDQ6068196zbMATH OpenFDO

Authors Sébastien Gaspoz, Riccardo W. Maffucci

Publication date 13 November 2023

Published in Applied Mathematics and Computation (Search for Journal in Brave)

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

zbMATH Keywords

3-polytopeextremal problemindependent setplanar graphradial graph

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Extremal problems in graph theory (05C35) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05)

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.

Recommendations

• scientific article; zbMATH DE number 3882467
• scientific article; zbMATH DE number 6116809
• Cyclomatic numbers of planar graphs
• Extremal polygonal cactus chain concerning k-independent sets.
• Lower bounds for constant degree independent sets

Cites work

• Diameters of Polyhedral Graphs
• Generation of simple quadrangulations of the sphere
• Graph theory with applications
• Graphs of polyhedra; polyhedra as graphs
• Graphs on surfaces
• Reducibility among combinatorial problems
• Self-dual polyhedra of given degree sequence
• The \(k\)-independence number of \(t\)-connected graphs
• The construction and classification of self-dual spherical polyhedra
• The symetries of cubic polyhedral graphs with face size no larger than 6

Cited in

(2)

• On unigraphic polyhedra with one vertex of degree \({p-2}\)
• Generation of 3-connected, planar line graphs

This page was built for publication: Independence numbers of polyhedral graphs

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