1. Complete co-secure domination in graphsGisha Saraswathy, Manju K. Menon, 2026, izvirni znanstveni članek Opis: A dominating set S ⊆ V is a co-secure dominating set if for each u ∈ S there exists v ∈ V \ S such that v is adjacent to u and (S \ {u}) ∪ {v} is a dominating set. The cardinality of a minimum co-secure dominating set in G is called the cosecure domination number of G and is denoted by γcs(G). The study of a co-secure dominating set is important in interconnection networks as it studies its security. In cosecure domination, a guard can ensure the safety of only one of its adjacent unguarded vertices. This motivated us to define a new domination parameter called complete co-secure domination, in which a guard can move to any one of its adjacent unguarded vertices without compromising the protection of G. A co-secure dominating set S is called a complete co-secure dominating set if for every u ∈ S and for every v ∈ V \ S that is adjacent to u, (S \ {u})∪ {v} is a dominating set. The cardinality of a minimum complete co-secure dominating set is called the complete co-secure domination number of G and is denoted by γccs(G). In this paper, we study the complete co-secure domination in graphs and determined the lower and upper bounds and have checked their sharpness. We have proved that for any positive integer m, there exists a graph whose co-secure domination number is m and complete co-secure domination number is b, where m ≤ b ≤ 2m. We characterize graphs G such that γcs(G) = γccs(G). We obtain a condition for which γcs(G) = γccs(G) = γs(G) for graphs with δ(G) ≥ 2, thus partially resolving a question posed in paper from Arumugam, Ebadi and Manrique from 2014. We also obtain the complete co-secure domination number of some families of graphs.
Ključne besede: domination number, co-secure domination number, complete co-secure domination number
Objavljeno v RUP: 20.03.2026; Ogledov: 315; Prenosov: 13
 Celotno besedilo (437,20 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: 567; Prenosov: 3
Celotno besedilo (395,09 KB)
Gradivo ima več datotek! Več... |
3. k-Domination ivariants on Kneser graphsBoštjan Brešar, Tanja Dravec, María Gracia Cornet, Michael A. Henning, 2025, izvirni znanstveni članek Opis: 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.
Ključne besede: Kneser graphs, k-domination, k-tuple total domination, 2-packing
Objavljeno v RUP: 22.10.2025; Ogledov: 528; Prenosov: 3
Celotno besedilo (375,34 KB) |
4. The 2-rainbow domination number of Cartesian product of cyclesSimon Brezovnik, Darja Rupnik Poklukar, Janez Žerovnik, 2025, izvirni znanstveni članek Opis: 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.
Ključne besede: 2-rainbow domination, domination number, Cartesian product
Objavljeno v RUP: 21.10.2025; Ogledov: 777; Prenosov: 7
Celotno besedilo (392,01 KB) |
5. The domination and independent domination numbers of some families of snarksAlessandra A. Pereira, Christiane N. Campos, 2025, izvirni znanstveni članek Opis: 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.
Ključne besede: domination, independent domination, Generalized Blanuša Snarks, Loupekine Snarks
Objavljeno v RUP: 21.10.2025; Ogledov: 689; Prenosov: 13
Celotno besedilo (505,21 KB) |
6. Indicated total domination gameMichael A. Henning, Douglas F. Rall, 2025, izvirni znanstveni članek Opis: 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.
Ključne besede: total domination game, indicated total domination game
Objavljeno v RUP: 21.10.2025; Ogledov: 642; Prenosov: 3
Celotno besedilo (378,61 KB) |
7. |
8. |
9. |
10. |
