1. On {k}-Roman graphsKenny Bešter Štorgel, Nina Chiarelli, Lara Fernández, J. Pascal Gollin, Claire Hilaire, Valeria Alejandra Leoni, Martin Milanič, 2025, published scientific conference contribution Abstract: 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.
Keywords: graph domination, {k}-Roman domination, {k}-Roman graph, split graph, split join, NP-completeness
Published in RUP: 16.12.2025; Views: 205; Downloads: 2
 Full text (395,09 KB)
This document has more files! More... |
2. k-Domination ivariants on Kneser graphsBoštjan Brešar, Tanja Dravec, María Gracia Cornet, Michael A. Henning, 2025, original scientific article Abstract: In this follow-up to work of M.G. Cornet and P. Torres from 2023, where the k-tuple domination number and the 2-packing number in Kneser graphs K(n, r) were studied, we are concerned with two variations, the k-domination number, γ_k(K(n, r)), and the k-tuple total domination number,
γ_{t × k}(K(n, r)), of K(n, r). For both invariants we prove monotonicity results by showing that γ_k(K(n, r)) ≥ γ_k(K(n + 1, r)) holds for any n ≥ 2(k + r), and γ_{t × k}(K(n, r)) ≥
γ_{t × k}(K(n + 1, r)) holds for any n ≥ 2r + 1. We prove that γ_k(K(n, r)) = γ_{t × k}(K(n, r)) = k + r when n ≥ r(k + r), and that in this case every γ_(k)-set and γ_(t × k)-set is a clique, while γ_k(r(k + r) − 1, r) = γ_{t × k}(r(k + r) − 1, r) = k + r + 1, for any k ≥ 2. Concerning the 2-packing number, ρ₂(K(n, r)), of K(n, r), we prove the exact values of ρ₂(K(3r − 3, r)) when r ≥ 10, and give sufficient conditions for ρ₂(K(n, r)) to be equal to some small values by imposing bounds on r with respect to n. We also prove a version of monotonicity for the 2-packing number of Kneser graphs.
Keywords: Kneser graphs, k-domination, k-tuple total domination, 2-packing
Published in RUP: 22.10.2025; Views: 264; Downloads: 1
Full text (375,34 KB) |
3. The 2-rainbow domination number of Cartesian product of cyclesSimon Brezovnik, Darja Rupnik Poklukar, Janez Žerovnik, 2025, original scientific article Abstract: A k-rainbow dominating function (kRDF) of G is a function that assigns subsets of {1, 2, ..., k} to the vertices of G such that for vertices v with f(v) = ∅ we have
⋃{u ∈ N(v)}f(u) = {1, 2, ..., k}. The weight w(f) of a kRDF f is defined as
w(f) = ∑{v ∈ V(G)}|f(v)|. The minimum weight of a kRDF of G is called the k-rainbow domination number of G, which is denoted by γrk(G). In this paper, we study the 2-rainbow domination number of the Cartesian product of two cycles. Exact values are given for a number of infinite families and we prove lower and upper bounds for all other cases.
Keywords: 2-rainbow domination, domination number, Cartesian product
Published in RUP: 21.10.2025; Views: 312; Downloads: 5
Full text (392,01 KB) |
4. The domination and independent domination numbers of some families of snarksAlessandra A. Pereira, Christiane N. Campos, 2025, original scientific article Abstract: A dominating set of a graph G is a set S ⊆ V (G) such that every vertex in V (G) either belongs to S or is adjacent to some vertex in S. The domination number is the minimum cardinality of a dominating set of G. An independent dominating set of G is a dominating set that is also independent. The minimum cardinality of an independent dominating set of G is the independent domination number of G. Given the computational complexity of these problems, extensive research has been done on finding bounds or determining these parameters for classes of graphs, especially cubic graphs. Furthermore, determining how far apart these parameters are is also a challenging problem. In this work, we establish some bounds for the domination number and the independent domination number for families of cubic graphs, in particular for Generalized Blanuša Snarks and for two families of
Loupekine Snarks known as LP_0-snarks and LP_1-snarks. We also show that the parameters are equal for these graphs and conjecture that this equality holds for every snark.
Keywords: domination, independent domination, Generalized Blanuša Snarks, Loupekine Snarks
Published in RUP: 21.10.2025; Views: 321; Downloads: 9
Full text (505,21 KB) |
5. Indicated total domination gameMichael A. Henning, Douglas F. Rall, 2025, original scientific article Abstract: A vertex u in a graph G totally dominates a vertex v if u is adjacent to v in G. A total dominating set of G is a set S of vertices of G such that every vertex of G is totally dominated by a vertex in S. The indicated total domination game is played on a graph G by two players, Dominator and Staller, who take turns making a move. In each of his moves, Dominator indicates a vertex v of the graph that has not been totally dominated in the previous moves, and Staller chooses (or selects) any vertex adjacent to v that has not yet been played, and adds it to a set D that is being built during the game. The game ends when every vertex is totally dominated, that is, when D is a total dominating set of G. The goal of Dominator is to minimize the size of D, while Staller wants just the opposite. Providing that both players are playing optimally with respect to their goals, the size of the resulting set D is the indicated total domination number of G, denoted by γti(G). In this paper we present several results on indicated total domination game. Among other results we prove that the indicated total domination number of a graph is bounded below by the well studied upper total domination number.
Keywords: total domination game, indicated total domination game
Published in RUP: 21.10.2025; Views: 288; Downloads: 1
Full text (378,61 KB) |
6. |
7. |
8. |
9. |
10. |
