1. Domination of subcubic planar graphs with large girthEun-Kyung Cho, Eric Culver, Stephen G. Hartke, Vesna Iršič Chenoweth, 2026, izvirni znanstveni članek Opis: 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₃.
Ključne besede: domination, subcubic planar graph, upper bound
Objavljeno v RUP: 11.08.2026; Ogledov: 320; Prenosov: 7
 Celotno besedilo (635,04 KB) |
2. On {k}-Roman graphsKenny Bešter Štorgel, Nina Chiarelli, Lara Fernández, J. Pascal Gollin, Claire Hilaire, Valeria Alejandra Leoni, Martin Milanič, 2025, objavljeni znanstveni prispevek na konferenci Opis: For a positive integer k, a {k}-Roman dominating function of a graph G = (V, E) is a function f : V → {0, 1, . . . , k} satisfying f (N(v)) ≥ k for each vertex v ∈ V with f (v) = 0. Every graph G satisfies γ{Rk}(G) ≤ kγ(G), where γ{Rk}(G) denotes the minimum weight of a {k}-Roman dominating function of G and γ(G) is the domination number of G. In this work we study graphs for which the equality is reached, called {k}-Roman graphs. This extends the concept of {k}-Roman trees studied by Wang et al. in 2021 to gen- eral graphs. We prove that for every k ≥ 3, the problem of recognizing {k}-Roman graphs is NP-hard, even when restricted to split graphs. We provide partial answers to the question of which split graphs are {2}-Roman: we characterize {2}-Roman split graphs that can be decomposed with respect to the split join operation into two smaller split graphs and classify the {k}-Roman property within two specific families of split graphs that are prime with respect to the split join operation: suns and their complements.
Ključne besede: graph domination, {k}-Roman domination, {k}-Roman graph, split graph, split join, NP-completeness
Objavljeno v RUP: 16.12.2025; Ogledov: 1024; Prenosov: 4
Celotno besedilo (395,09 KB)
Gradivo ima več datotek! Več... |
3. |
4. |
5. |
6. |
7. Linear separation of connected dominating sets in graphsNina Chiarelli, Martin Milanič, 2019, izvirni znanstveni članek Ključne besede: connected dominating set, connected domination, connected-domishold graph, forbidden induced subgraph characterization, split graph, chordal graph, minimal cutset, minimal separator, 1-Sperner hypergraph, threshold hypergraph, threshold Boolean function, polynomial-time algorithm
Objavljeno v RUP: 04.04.2019; Ogledov: 6119; Prenosov: 171
Celotno besedilo (648,51 KB) |
8. |
9. |
10. |
