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: 311; Prenosov: 13
 Celotno besedilo (437,20 KB) |
2. 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: 759; Prenosov: 7
Celotno besedilo (392,01 KB) |
3. |
4. A note on domination and independence-domination numbers of graphsMartin Milanič, 2013, objavljeni znanstveni prispevek na konferenci Opis: Vizing's conjecture is true for graphs ▫$G$▫ satisfying ▫$\gamma^i(G) = \gamma(G)$▫, where ▫$\gamma(G)$▫ is the domination number of a graph ▫$G$▫ and ▫$\gamma^i(G)$▫ is the independence-domination number of ▫$G$▫, that is, the maximum, over all independent sets ▫$I$▫ in ▫$G$▫, of the minimum number of vertices needed to dominate ▫$I$▫. The equality ▫$\gamma^i(G) = \gamma(G)$▫ is known to hold for all chordal graphs and for chordless cycles of length ▫$0 \pmod{3}$▫. We prove some results related to graphs for which the above equality holds. More specifically, we show that the problems of determining whether ▫$\gamma^i(G) = \gamma(G) = 2$▫ and of verifying whether ▫$\gamma^i(G) \ge 2$▫ are NP-complete, even if ▫$G$▫ is weakly chordal. We also initiate the study of the equality ▫$\gamma^i = \gamma$▫ in the context of hereditary graph classes and exhibit two infinite families of graphs for which ▫$\gamma^i < \gamma$▫.
Ključne besede: Vizing's conjecture, domination number, independence-domination number, weakly chordal graph, NP-completeness, hereditary graph class, IDD-perfect graph
Objavljeno v RUP: 15.10.2013; Ogledov: 5331; Prenosov: 134
Celotno besedilo (300,57 KB) |
