1. Graphs with equal Grundy domination and independence numberGábor Bacsó, Boštjan Brešar, Kirsti Kuenzel, Douglas F. Rall, 2023, izvirni znanstveni članek Povzetek: The Grundy domination number, ${\gamma_{\rm gr}}(G)$, of a graph $G$ is the maximum length of a sequence $(v_1,v_2,\ldots, v_k)$ of vertices in $G$ such that for every $i\in \{2,\ldots, k\}$, the closed neighborhood $N[v_i]$ contains a vertex that does not belong to any closed neighborhood $N[v_j]$, where $jKljučne besede: Grundy domination, independence number, upper domination number, bipartite graphs Objavljeno v DiRROS: 09.04.2024; Ogledov: 80; Prenosov: 44 Celotno besedilo (803,91 KB) Gradivo ima več datotek! Več... |
2. Domination and independence numbers of large 2-crossing-critical graphsVesna Iršič, Maruša Lekše, Miha Pačnik, Petra Podlogar, Martin Praček, 2023, izvirni znanstveni članek Povzetek: After 2-crossing-critical graphs were characterized in 2016, their most general subfamily, large 3-connected 2-crossing-critical graphs, has attracted separate attention. This paper presents sharp upper and lower bounds for their domination and independence number. Ključne besede: crossing-critical graphs, domination number, independence number Objavljeno v DiRROS: 09.04.2024; Ogledov: 65; Prenosov: 41 Celotno besedilo (393,09 KB) Gradivo ima več datotek! Več... |
3. Maker-Breaker domination game on trees when Staller winsCsilla Bujtás, Pakanun Dokyeesun, Sandi Klavžar, 2023, izvirni znanstveni članek Povzetek: In the Maker-Breaker domination game played on a graph $G$, Dominator's goal is to select a dominating set and Staller's goal is to claim a closed neighborhood of some vertex. We study the cases when Staller can win the game. If Dominator (resp., Staller) starts the game, then $\gamma_{\rm SMB}(G)$ (resp., $\gamma_{\rm SMB}'(G)$) denotes the minimum number of moves Staller needs to win. For every positive integer $k$, trees $T$ with $\gamma_{\rm SMB}'(T)=k$ are characterized and a general upper bound on $\gamma_{\rm SMB}'$ is proved. Let $S = S(n_1,\dots, n_\ell)$ be the subdivided star obtained from the star with $\ell$ edges by subdividing its edges $n_1-1, \ldots, n_\ell-1$ times, respectively. Then $\gamma_{\rm SMB}'(S)$ is determined in all the cases except when $\ell\ge 4$ and each $n_i$ is even. The simplest formula is obtained when there are at least two odd $n_i$s. If ▫$n_1$▫ and $n_2$ are the two smallest such numbers, then $\gamma_{\rm SMB}'(S(n_1,\dots, n_\ell))=\lceil \log_2(n_1+n_2+1)\rceil$▫. For caterpillars, exact formulas for $\gamma_{\rm SMB}$ and for $\gamma_{\rm SMB}'$ are established. Ključne besede: domination game, Maker-Breaker game, Maker-Breaker domination game, hypergraphs, trees, subdivided stars, caterpillars Objavljeno v DiRROS: 08.04.2024; Ogledov: 103; Prenosov: 50 Celotno besedilo (255,58 KB) Gradivo ima več datotek! Več... |
4. Orientable domination in product-like graphsSarah Anderson, Boštjan Brešar, Sandi Klavžar, Kirsti Kuenzel, Douglas F. Rall, 2023, izvirni znanstveni članek Povzetek: The orientable domination number, ${\rm DOM}(G)$, of a graph $G$ is the largest domination number over all orientations of $G$. In this paper, ${\rm DOM}$ is studied on different product graphs and related graph operations. The orientable domination number of arbitrary corona products is determined, while sharp lower and upper bounds are proved for Cartesian and lexicographic products. A result of Chartrand et al. from 1996 is extended by establishing the values of ${\rm DOM}(K_{n_1,n_2,n_3})$ for arbitrary positive integers $n_1,n_2$ and $n_3$. While considering the orientable domination number of lexicographic product graphs, we answer in the negative a question concerning domination and packing numbers in acyclic digraphs posed in [Domination in digraphs and their direct and Cartesian products, J. Graph Theory 99 (2022) 359-377]. Ključne besede: digraph, domination, orientable domination number, packing, graph product, corona graph Objavljeno v DiRROS: 20.03.2024; Ogledov: 114; Prenosov: 52 Celotno besedilo (366,61 KB) Gradivo ima več datotek! Več... |
5. Computational complexity aspects of super dominationCsilla Bujtás, Nima Ghanbari, Sandi Klavžar, 2023, izvirni znanstveni članek Povzetek: Let ▫$G$▫ be a graph. A dominating set ▫$D\subseteq V(G)$▫ is a super dominating set if for every vertex ▫$x\in V(G) \setminus D$▫ there exists ▫$y\in D$▫ such that ▫$N_G(y)\cap (V(G)\setminus D)) = \{x\}$▫. The cardinality of a smallest super dominating set of ▫$G$▫ is the super domination number of ▫$G$▫. An exact formula for the super domination number of a tree ▫$T$▫ is obtained, and it is demonstrated that a smallest super dominating set of ▫$T$▫ can be computed in linear time. It is proved that it is NP-complete to decide whether the super domination number of a graph ▫$G$▫ is at most a given integer if ▫$G$▫ is a bipartite graph of girth at least ▫$8$▫. The super domination number is determined for all ▫$k$▫-subdivisions of graphs. Interestingly, in half of the cases the exact value can be efficiently computed from the obtained formulas, while in the other cases the computation is hard. While obtaining these formulas, II-matching numbers are introduced and proved that they are computationally hard to determine. Ključne besede: super domination number, trees, bipartite graphs, k-subdivision of a graph, computational complexity, matching, II-matching number Objavljeno v DiRROS: 14.03.2024; Ogledov: 96; Prenosov: 56 Celotno besedilo (453,39 KB) Gradivo ima več datotek! Več... |
6. Packings in bipartite prisms and hypercubesBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2024, izvirni znanstveni članek Povzetek: The $2$-packing number $\rho_2(G)$ of a graph $G$ is the cardinality of a largest $2$-packing of $G$ and the open packing number $\rho^{\rm o}(G)$ is the cardinality of a largest open packing of $G$, where an open packing (resp. $2$-packing) is a set of vertices in $G$ no two (closed) neighborhoods of which intersect. It is proved that if $G$ is bipartite, then $\rho^{\rm o}(G\Box K_2) = 2\rho_2(G)$. For hypercubes, the lower bounds $\rho_2(Q_n) \ge 2^{n - \lfloor \log n\rfloor -1}$ and $\rho^{\rm o}(Q_n) \ge 2^{n - \lfloor \log (n-1)\rfloor -1}$ are established. These findings are applied to injective colorings of hypercubes. In particular, it is demonstrated that $Q_9$ is the smallest hypercube which is not perfect injectively colorable. It is also proved that $\gamma_t(Q_{2^k}\times H) = 2^{2^k-k}\gamma_t(H)$, where $H$ is an arbitrary graph with no isolated vertices. Ključne besede: 2-packing number, open packing number, bipartite prism, hypercube, injective coloring, total domination number Objavljeno v DiRROS: 19.02.2024; Ogledov: 187; Prenosov: 70 Celotno besedilo (231,57 KB) Gradivo ima več datotek! Več... |
7. Partial domination in supercubic graphsCsilla Bujtás, Michael A. Henning, Sandi Klavžar, 2024, izvirni znanstveni članek Povzetek: For some $\alpha$ with $0 < \alpha \le 1$, a subset $X$ of vertices in a graph $G$ of order $n$ is an $\alpha$-partial dominating set of $G$ if the set $X$ dominates at least $\alpha \times n$ vertices in $G$. The $\alpha$-partial domination number ${\rm pd}_{\alpha}(G)$ of $G$ is the minimum cardinality of an $\alpha$-partial dominating set of $G$. In this paper partial domination of graphs with minimum degree at least $3$ is studied. It is proved that if $G$ is a graph of order $n$ and with $\delta(G)\ge 3$, then ${\rm pd}_{\frac{7}{8}}(G) \le \frac{1}{3}n$. If in addition $n\ge 60$, then ${\rm pd}_{\frac{9}{10}}(G) \le \frac{1}{3}n$, and if $G$ is a connected cubic graph of order $n\ge 28$, then ${\rm pd}_{\frac{13}{14}}(G) \le \frac{1}{3}n$. Along the way it is shown that there are exactly four connected cubic graphs of order $14$ with domination number $5$. Ključne besede: domination, partial domination, cubic graphs, supercubic graphs Objavljeno v DiRROS: 15.02.2024; Ogledov: 148; Prenosov: 70 Celotno besedilo (304,87 KB) Gradivo ima več datotek! Več... |