1. Graphs with unique Grundy dominating setsBoštjan Brešar, Tanja Dravec, 2026, izvirni znanstveni članek Povzetek: Given a graph $G$ consider a procedure of building a dominating set $D$ in $G$ by adding vertices to $D$ one at a time in such a way that whenever vertex $x$ is added to $D$ there exists a vertex $y\in N_G[x]$ that becomes dominated only after $x$ is added to $D$. The maximum cardinality of a set $D$ obtained in the described way is called the Grundy domination number of $G$ and $D$ a Grundy dominating set. While a Grundy dominating set of a connected graph $G$ is not unique unless $G$ is the trivial graph, we consider a natural weaker uniqueness condition, notably that for every two Grundy dominating sets in a graph $G$ there is an automorphism that maps one to the other. We investigate both versions of uniqueness for several concepts of Grundy domination, which appeared in the context of domination games and are also closely related to zero forcing. For each of the four variations of Grundy domination we characterize the graphs that have only one Grundy dominating set of the given type, and characterize those forests that enjoy the weaker (isomorphism based) condition of uniqueness. The latter characterizations lead to efficient algorithms for recognizing the corresponding classes of forests.
Ključne besede: Grundy total domination number, Grundy domination number, zero forcing number, trees, graph automorphism
Objavljeno v DiRROS: 22.06.2026; Ogledov: 117; Prenosov: 93
 Celotno besedilo (490,32 KB)
Gradivo ima več datotek! Več... |
2. Independent mutual-visibility coloring and related conceptsBoštjan Brešar, Iztok Peterin, Babak Samadi, Ismael G. Yero, 2026, izvirni znanstveni članek Povzetek: Given a graph $G$, a subset $M\subseteq V(G)$ is a mutual-visibility (MV) set if for every $u,v\in M$, there exists a $u,v$-geodesic whose internal vertices are not in $M$. We investigate proper vertex colorings of graphs whose color classes are mutual-visibility sets. The main concepts that arise in this investigation are independent mutual-visibility (IMV) sets and vertex partitions into these sets (IMV colorings). The IMV number $\mu_{i}$ and the IMV chromatic number $\chi_{\mu_{i}}$ are defined as maximum and minimum cardinality taken over all IMV sets and IMV colorings, respectively. Along the way, we also continue with the study of MV chromatic number $\chi_{\mu}$ (as the smallest number of sets in a vertex partition into MV sets), which was initiated in an earlier paper. We establish a close connection between the (I)MV chromatic numbers of subdivisions of complete graphs and Ramsey numbers $R(4^k;2)$. From the computational point of view, we prove that the problems of computing $\chi_{\mu_{i}}$ and $\mu_{i}$ are NP-complete, and that it is NP-hard to decide whether a graph $G$ satisfies $\mu_i(G)=\alpha(G)$ where $\alpha(G)$ is the independence number of $G$. Several tight bounds on $\chi_{\mu_{i}}$, $\chi_{\mu}$ and $\mu_{i}$ are given. Exact values/formulas for these parameters in some classical families of graphs are proved. In particular, we prove that $\chi_{\mu_{i}}(T)=\chi_{\mu}(T)$ holds for any tree $T$ of order at least $3$, and determine their exact formulas in the case of lexicographic product graphs. Finally, we give tight bounds on the (I)MV chromatic numbers for the Cartesian and strong product graphs, which lead to exact values in some important families of product graphs.
Ključne besede: independent mutual visibility, mutual-visibility coloring, independence number, Ramsey number, graph product, diameter 2 graph, geodesic
Objavljeno v DiRROS: 05.05.2026; Ogledov: 250; Prenosov: 162
Celotno besedilo (596,20 KB)
Gradivo ima več datotek! Več... |
3. Isolation game on graphsBoštjan Brešar, Tanja Dravec, Daniel P. Johnston, Kirsti Kuenzel, Douglas F. Rall, 2026, izvirni znanstveni članek Povzetek: Given a graph $G$ and a family of graphs $\cal F$, an $\cal F$-isolating set, as introduced by Caro and Hansberg, is any set $S\subset V(G)$ such that $G - N[S]$ contains no member of $\cal F$ as a subgraph. In this paper, we introduce a game in which two players with opposite goals are together building an $\cal F$-isolating set in $G$. Following the domination games, Dominator (Staller) wants that the resulting $\cal F$-isolating set obtained at the end of the game, is as small (as big) as possible, which leads to the graph invariant called the game $\cal F$-isolation number, denoted $\iota_{\rm g}(G,\cal F)$. We prove that the Continuation Principle holds in the $\cal F$-isolation game, and that the difference between the game $\cal F$-isolation numbers when either Dominator or Staller starts the game is at most $1$. Considering two arbitrary families of graphs $\cal F$ and $\cal F'$, we find relations between them that ensure $\iota_{\rm g}(G,{\mathcal{F}}') \leq \iota_{\rm g}(G,{\mathcal{F}})$ for any graph $G$. A special focus is given on the isolation game, which takes place when ${\cal F}=\{K_2\}$. We prove that $\iota_{\rm g}(G,\{K_2\})\le |V(G)|/2$ for any graph $G$, and conjecture that $\lceil 3|V(G)|/7\rceil$ is the actual (sharp) upper bound. We prove that the isolation game on a forest when Dominator has the first move never lasts longer than the one in which Staller starts the game. Finally, we prove good lower and upper bounds on the game isolation numbers of paths $P_n$, which lead to the exact values $\iota_{\rm g}(P_n,\{K_2\})=\left\lfloor\frac{2n+2}{5}\right\rfloor$ when $n \equiv i \pmod 5$ and $i \in \{1,2,3\}$.
Ključne besede: isolation number, graph games, domination games, continuation principle, forest
Objavljeno v DiRROS: 03.03.2026; Ogledov: 344; Prenosov: 256
Celotno besedilo (290,47 KB)
Gradivo ima več datotek! Več... |
4. Bootstrap percolation and $P_3$-hull number in direct products of graphsBoštjan Brešar, Jaka Hedžet, Rebekah Herrman, 2026, izvirni znanstveni članek Povzetek: The $r$-neighbor bootstrap percolation is a graph infection process based on the update rule by which a vertex with $r$ infected neighbors becomes infected. We say that an initial set of infected vertices propagates if all vertices of a graph $G$ are eventually infected, and the minimum cardinality of such a set in $G$ is called the $r$-bootstrap percolation number, $m(G,r)$, of $G$. In this paper, we study percolating sets in direct products of graphs. While in general graphs there is no non-trivial upper bound on $m(G\times H,r)$, we prove several upper bounds under the assumption $\delta(G)\ge r$. We also characterize the connected graphs $G$ and $H$ with minimum degree $2$ that satisfy $m(G \times H, 2) = \frac{|V(G \times H)|}{2}$. In addition, we determine the exact values of $m(P_n \times P_m, 2)$, which are $m+n-1$ if $m$ and $n$ are of different parities, and $m+n$ otherwise.
Ključne besede: bootstrap percolation, direct product of graphs, $P_3$-convexity
Objavljeno v DiRROS: 16.01.2026; Ogledov: 424; Prenosov: 285
Celotno besedilo (258,32 KB)
Gradivo ima več datotek! Več... |
5. Thresholds for the biased Maker-Breaker domination gamesBoštjan Brešar, Csilla Bujtás, Pakanun Dokyeesun, Tanja Dravec, 2025, izvirni znanstveni članek Povzetek: In the $(a,b)$-biased Maker-Breaker domination game, two players alternately select unplayed vertices in a graph $G$ such that Dominator selects $a$ and Staller selects $b$ vertices per move. Dominator wins if the vertices he selected during the game form a dominating set of $G$, while Staller wins if she can prevent Dominator from achieving this goal. Given a positive integer $b$, Dominator's threshold, ${\rm a}_b$, is the minimum $a$ such that Dominator wins the $(a,b)$-biased game on $G$ when he starts the game. Similarly, ${\rm a}'_b$ denotes the minimum $a$ such that Dominator wins when Staller starts the $(a,b)$-biased game. Staller's thresholds, ${\rm b}_a$ and ${\rm b}'_a$, are defined analogously. It is proved that Staller wins the $(k-1,k)$-biased games in a graph $G$ if its order is sufficiently large with respect to a function of $k$ and the maximum degree of $G$. Along the way, the $\ell$-local domination number of a graph is introduced. This new parameter is proved to bound Dominator's thresholds ${\rm a}_\ell$ and ${\rm a}_\ell'$ from above. As a consequence, ${\rm a}_1'(G)\le 2$ holds for every claw-free graph $G$. More specific results are obtained for thresholds in line graphs and Cartesian grids. Based on the concept of $[1,k]$-factor of a graph $G$, we introduce the star partition width $\sigma(G)$ of $G$, and prove that ${\rm a}_1'(G)\le \sigma(G)$ holds for any nontrivial graph $G$, while ${\rm a}_1'(G)=\sigma(G)$ if $G$ is a tree.
Ključne besede: Maker-Breaker domination game, biased Maker-Breaker game, trees, line graph, grid
Objavljeno v DiRROS: 23.10.2025; Ogledov: 553; Prenosov: 309
Celotno besedilo (415,24 KB)
Gradivo ima več datotek! Več... |
6. Spreading in claw-free cubic graphsBoštjan Brešar, Jaka Hedžet, Michael A. Henning, 2025, izvirni znanstveni članek Povzetek: Let $p\in\mathbb{N}$ and $q\in\mathbb{N}\cup\{\infty\}$. We study a dynamic coloring of the vertices of a graph $G$ that starts with an initial subset $S$ of blue vertices, with all remaining vertices colored white. If a white vertex $v$ has at least $p$ blue neighbors and at least one of these blue neighbors of $v$ has at most $q$ white neighbors, then by the spreading color change rule the vertex $v$ is recolored blue. The initial set $S$ of blue vertices is a $(p,q)$-spreading set for $G$ if by repeatedly applying the spreading color change rule all the vertices of $G$ are eventually colored blue. The $(p,q)$-spreading set is a generalization of the well-studied concepts of $k$-forcing and $r$-percolating sets in graphs. For $q\ge2$, a $(1,q)$-spreading set is exactly a $q$-forcing set, and the $(1,1)$-spreading set is a $1$-forcing set (also called a zero forcing set), while for $q=\infty$, a $(p,\infty)$-spreading set is exactly a $p$-percolating set. The $(p,q)$-spreading number, $\sigma_{(p,q)}(G)$, of $G$ is the minimum cardinality of a $(p,q)$-spreading set. In this paper, we study $(p,q)$-spreading in claw-free cubic graphs. While the zero-forcing number of claw-free cubic graphs was studied earlier, for each pair of values $p$ and $q$ that are not both $1$ we either determine the $(p,q)$-spreading number of a claw-free cubic graph $G$ or show that $\sigma_{(p,q)}(G)$ attains one of two possible values.
Ključne besede: bootstrap percolation, zero forcing set, k-forcing set, spreading
Objavljeno v DiRROS: 23.09.2025; Ogledov: 564; Prenosov: 301
Celotno besedilo (530,15 KB)
Gradivo ima več datotek! Več... |
7. Injective colorings of Sierpiński-like graphs and Kneser graphsBoštjan Brešar, Sandi Klavžar, Babak Samadi, Ismael G. Yero, 2025, izvirni znanstveni članek Povzetek: Two relationships between the injective chromatic number and, respectively, chromatic number and chromatic index, are proved. They are applied to determine the injective chromatic number of Sierpiński graphs and to give a short proof that Sierpiński graphs are Class 1. Sierpiński-like graphs are also considered, including generalized Sierpiński graphs over cycles and rooted products. It is proved that the injective chromatic number of a rooted product of two graphs lies in a set of six possible values. Sierpiński graphs and Kneser graphs $K(n,r)$ are considered with respect of being perfect injectively colorable, where a graph is perfect injectively colorable if it has an injective coloring in which every color class forms an open packing of largest cardinality. In particular, all Sierpiński graphs and Kneser graphs $K(n,r)$ with $n\ge 3r-1$, are perfect injectively colorable, while $K(7,3)$ is not.
Ključne besede: injective coloring, injective chromatic number, perfect injectively colorable graph, Sierpiński graphs, Kneser graphs, rooted product graph
Objavljeno v DiRROS: 25.07.2025; Ogledov: 728; Prenosov: 444
Celotno besedilo (6,36 MB)
Gradivo ima več datotek! Več... |
8. $k$-domination invariants on Kneser graphsBoštjan Brešar, Tanja Dravec, María Gracia Cornet, Michael A. Henning, 2025, izvirni znanstveni članek Povzetek: 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, $\gamma_k(K(n,r))$, and the $k$-tuple total domination number, $\gamma_{t\times k}(K(n,r))$, of $K(n,r)$. For both invariants we prove monotonicity results by showing that $\gamma_k(K(n,r))\ge \gamma_k(K(n+1,r))$ holds for any $n\ge 2(k+r)$, and $\gamma_{t\times k}(K(n,r))\ge \gamma_{t\times k}(K(n+1,r))$ holds for any $n\ge 2r+1$. We prove that $\gamma_k(K(n,r))= \gamma_{t\times k}(K(n,r))= k+r$ when $n\geq r(k+r)$, and that in this case every $\gamma_k$-set and $\gamma_{t\times k}$-set is a clique, while $\gamma_k(r(k+r)-1,r)=\gamma_{t\times k}(r(k+r)-1,r)=k+r+1$, for any $k\ge 2$. Concerning the $2$-packing number, $\rho_2(K(n,r))$, of $K(n,r)$, we prove the exact values of $\rho_2(K(3r-3,r))$ when $r\ge 10$, and give sufficient conditions for $\rho_2(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 DiRROS: 24.07.2025; Ogledov: 794; Prenosov: 487
Celotno besedilo (377,04 KB)
Gradivo ima več datotek! Več... |
9. Total ▫$k$▫-coalition: bounds, exact values and an application to double coalitionBoštjan Brešar, Sandi Klavžar, Babak Samadi, 2025, izvirni znanstveni članek Povzetek: Let $G=\big{(}V(G),E(G)\big{)}$ be a graph with minimum degree $k$. A subset $S\subseteq V(G)$ is called a total $k$-dominating set if every vertex in $G$ has at least $k$ neighbors in $S$. Two disjoint sets $A,B\subset V(G)$ form a total $k$-coalition in $G$ if none of them is a total $k$-dominating set in $G$ but their union $A\cup B$ is a total $k$-dominating set. A vertex partition $\Omega=\{V_{1},\ldots,V_{|\Omega|}\}$ of $G$ is a total $k$-coalition partition if each set $V_{i}$ forms a total $k$-coalition with another set $V_{j}$. The total $k$-coalition number ${\rm TC}_{k}(G)$ of $G$ equals the maximum cardinality of a total $k$-coalition partition of $G$. In this paper, the above-mentioned concepts are investigated from combinatorial points of view. Several sharp lower and upper bounds on ${\rm TC}_{k}(G)$ are proved, where the main emphasis is given on the invariant when $k=2$. As a consequence, the exact values of ${\rm TC}_2(G)$ when $G$ is a cubic graph or a $4$-regular graph are obtained. By using similar methods, an open question posed by Henning and Mojdeh regarding double coalition is answered. Moreover, ${\rm TC}_3(G)$ is determined when $G$ is a cubic graph.
Ključne besede: total k-coalition, total k-domination, regular graph, double coalition
Objavljeno v DiRROS: 17.07.2025; Ogledov: 728; Prenosov: 395
Celotno besedilo (480,42 KB)
Gradivo ima več datotek! Več... |
10. Induced matching vs edge open packing: trees and product graphsBoštjan Brešar, Tanja Dravec, Jaka Hedžet, Babak Samadi, 2025, izvirni znanstveni članek Povzetek: Given a graph $G$, the maximum size of an induced subgraph of $G$ each component of which is a star is called the edge open packing number, $\rho_{e}^{o} (G)$, of $G$. Similarly, the maximum size of an induced subgraph of $G$ each component of which is the star $K_{1,1}$ is the induced matching number, $\nu_I(G)$, of $G$. While the inequality $\rho_{e}^{o}(G)\ge \nu_I(G)$ clearly holds for all graphs $G$, we provide a structural characterization of those trees that attain the equality. We prove that the induced matching number of the lexicographic product $G\circ H$ of arbitrary two graphs $G$ and $H$ equals $\alpha(G)\nu_I(H)$. By similar techniques, we prove sharp lower and upper bounds on the edge open packing number of the lexicographic product of graphs, which in particular lead to NP-hardness results in triangular graphs for both invariants studied in this paper. For the direct product $G\times H$ of two graphs we provide lower bounds on $\nu_I(G\times H)$ and $\rho_{e}^{o} (G\times H)$, both of which are widely sharp. We also present sharp lower bounds for both invariants in the Cartesian and the strong product of two graphs. Finally, we consider the edge open packing number in hypercubes establishing the exact values of $\rho_{e}^{o} (Q_n)$ when $n$ is a power of $2$, and present a closed formula for the induced matching number of the rooted product of arbitrary two graphs over an arbitrary root vertex.
Ključne besede: induced matching, edge open packing, graph product, independent set, trees
Objavljeno v DiRROS: 07.03.2025; Ogledov: 1433; Prenosov: 598
Celotno besedilo (1,31 MB)
Gradivo ima več datotek! Več... |
