1. 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: 284
 Celotno besedilo (258,32 KB)
Gradivo ima več datotek! Več... |
2. 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č... |
3. 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č... |
4. Bootstrap percolation in strong products of graphsBoštjan Brešar, Jaka Hedžet, 2024, izvirni znanstveni članek Povzetek: Given a graph $G$ and assuming that some vertices of $G$ are infected, the $r$-neighbor bootstrap percolation rule makes an uninfected vertex $v$ infected if $v$ has at least $r$ infected neighbors. The $r$-percolation number, $m(G,r)$, of $G$ is the minimum cardinality of a set of initially infected vertices in $G$ such that after continuously performing the $r$-neighbor bootstrap percolation rule each vertex of $G$ eventually becomes infected. In this paper, we consider percolation numbers of strong products of graphs. If $G$ is the strong product $G_1\boxtimes \cdots \boxtimes G_k$ of $k$ connected graphs, we prove that $m(G,r)=r$ as soon as $r\le 2^{k-1}$ and $|V(G)|\ge r$. As a dichotomy, we present a family of strong products of $k$ connected graphs with the $(2^{k-1}+1)$-percolation number arbitrarily large. We refine these results for strong products of graphs in which at least two factors have at least three vertices. In addition, when all factors $G_i$ have at least three vertices we prove that $m(G_1 \boxtimes \dots \boxtimes G_k,r)\leq 3^{k-1} -k$ for all $r\leq 2^k-1$, and we again get a dichotomy, since there exist families of strong products of $k$ graphs such that their $2^{k}$-percolation numbers are arbitrarily large. While $m(G\boxtimes H,3)=3$ if both $G$ and $H$ have at least three vertices, we also characterize the strong prisms $G\boxtimes K_2$ for which this equality holds. Some of the results naturally extend to infinite graphs, and we briefly consider percolation numbers of strong products of two-way infinite paths.
Ključne besede: bootstrap percolation, strong product of graphs, infinite path
Objavljeno v DiRROS: 20.11.2024; Ogledov: 1014; Prenosov: 584
Celotno besedilo (649,39 KB)
Gradivo ima več datotek! Več... |
5. Variety of mutual-visibility problems in graphsSerafino Cicerone, Gabriele Di Stefano, Lara Drožđek, Jaka Hedžet, Sandi Klavžar, Ismael G. Yero, 2023, izvirni znanstveni članek Povzetek: If $X$ is a subset of vertices of a graph $G$, then vertices $u$ and $v$ are $X$-visible if there exists a shortest $u,v$-path $P$ such that $V(P)\cap X \subseteq \{u,v\}$. If each two vertices from $X$ are $X$-visible, then $X$ is a mutual-visibility set. The mutual-visibility number of $G$ is the cardinality of a largest mutual-visibility set of $G$ and has been already investigated. In this paper a variety of mutual-visibility problems is introduced based on which natural pairs of vertices are required to be $X$-visible. This yields the total, the dual, and the outer mutual-visibility numbers. We first show that these graph invariants are related to each other and to the classical mutual-visibility number, and then we prove that the three newly introduced mutual-visibility problems are computationally difficult. According to this result, we compute or bound their values for several graphs classes that include for instance grid graphs and tori. We conclude the study by presenting some inter-comparison between the values of such parameters, which is based on the computations we made for some specific families.
Ključne besede: mutual-visibility, total mutual-visibility, dual mutual-visibility number, outer mutual-visibility, grid graphs, torus graphs, computational complexity
Objavljeno v DiRROS: 10.04.2024; Ogledov: 1593; Prenosov: 818
Celotno besedilo (456,36 KB)
Gradivo ima več datotek! Več... |
