Premium
Constructing certain families of 3‐polytopal graphs
Author(s) -
Maffucci Riccardo W.
Publication year - 2023
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.22882
Subject(s) - combinatorics , mathematics , vertex (graph theory) , polytope , degree (music) , vertex connectivity , graph , discrete mathematics , physics , acoustics
Letn ≥ 3 $n\ge 3$ andR n${R}_{n}$ be a 3‐polytopal graph such that for every3 ≤ i ≤ n $3\le i\le n$ ,R n${R}_{n}$ has at least one vertex of degreei $i$ . We find the minimal vertex count forR n${R}_{n}$ . We then describe an algorithm to construct the graphsR n${R}_{n}$ . A dual statement may be formulated for faces of 3‐polytopes. The ideas behind the algorithm generalise readily to solve related problems. Moreover, given a 3‐polytopeT l${T}_{l}$ comprising a vertex of degreei $i$ for all3 ≤ i ≤ l $3\le i\le l$ ,l $l$ fixed, we define an algorithm to output forn > l $n\gt l$ a 3‐polytopeT n${T}_{n}$ comprising a vertex of degreei $i$ , for all3 ≤ i ≤ n $3\le i\le n$ , and such that the initialT l${T}_{l}$ is a subgraph ofT n${T}_{n}$ . The vertex count ofT n${T}_{n}$ is asymptotically optimal, in the sense that it matches the aforementioned minimal vertex count up to order of magnitude, asn $n$ gets large. In fact, we only lose a small quantity on the coefficient of the second highest term, and this quantity may be taken as small as we please, with the tradeoff of first constructing an accordingly large auxiliary graph.