20.500.12556/RUP-23438 Domination of subcubic planar graphs with large girth Dominacija podkubičnih ravninskih grafov z veliko ožino Since Reed conjectured in 1996 that the domination number of a connected cubic graph of order n is at most ⌈1/3n⌉, the domination number of cubic graphs has been extensively studied. It is now known that the conjecture is false in general, but Henning and Dorbec showed that it holds for graphs with girth at least 9. Zhu and Wu stated an analogous conjecture for 2-connected cubic planar graphs. In this paper, we present a new upper bound for the domination number of subcubic planar graphs: if G is a subcubic planar graph with girth at least 8, then γ(G) < n₀ + 3/4 n₁ + 11/20 n₂ + 7/20 n₃, where n_i denotes the number of vertices in G of degree i, for i ∈ {0, 1, 2, 3}. We also prove that if G is a subcubic planar graph with girth at least 9, then γ(G) < n₀ + 13/17 n₁ + 9/17 n₂ + 6/17 n₃. Odkar je Reed leta 1996 domneval, da je dominacijsko število povezanega kubičnega grafa reda n največ ⌈1/3n⌉, je bilo dominacijsko število kubičnih grafov obsežno preučevano. Danes je znano, da domneva na splošno ne drži, vendar sta Henning in Dorbec pokazala, da velja za grafe z ožino vsaj 9. Zhu in Wu sta podala analogno domnevo za 2-povezane kubične ravninske grafe. V tem članku podamo novo zgornjo mejo za dominacijsko število podkubičnih ravninskih grafov: če je G podkubičen ravninski graf z ožino vsaj 8, potem velja γ(G) < n₀ + 3/4 n₁ + 11/20 n₂ + 7/20 n₃, kjer n_i označuje število vozlišč v G stopnje i, za i ∈ {0, 1, 2, 3}. Prav tako dokažemo, da za vsak podkubičen ravninski graf G z ožino vsaj 9 velja γ(G) < n₀ + 13/17 n₁ + 9/17 n₂ + 6/17 n₃. domination subcubic planar graph upper bound dominacija podkubični ravninski graf zgornja meja true false true Založba Univerze na Primorskem Angleški jezik Slovenski jezik Članek v reviji 2026-08-11 11:03:03 2026-08-11 11:03:03 2026-08-12 03:07:39 0000-00-00 00:00:00 2026 0 0 32 str. no. 2, [article no.] P2.08 Vol. 26 2026 0000-00-00 Zaloznikova Objavljeno NiDoloceno 0000-00-00 0000-00-00 2026-03-18 51 1855-3974 10.26493/1855-3974.3389.86c AMC_Cho,_Culver,_G._Hartke,_Irsic_Chenoweth_2026.pdf AMC_Cho,_Culver,_G._Hartke,_Irsic_Chenoweth_2026.pdf 1 D88CEF05F194BCF47F536A07C6B0A442 1acf705fc7dd91ceb20154c0a10954a60e19c15122c14c376f0edb403ee0e76f b7fbf06c-9564-11f1-9e8d-005056ac49c0 https://repozitorij.upr.si/Dokument.php?lang=slv&id=34353 Založba Univerze na Primorskem 0 0 0