1. Maker-Breaker domination game critical graphsAthira Divakaran, Tanja Dravec, Tijo James, Sandi Klavžar, Latha S. Nair, 2025, izvirni znanstveni članek Opis: The Maker-Breaker domination game (MBD game) is a two-player game played on a graph ▫$G$▫ by Dominator and Staller. They alternately select unplayed vertices of ▫$G$▫. The goal of Dominator is to form a dominating set with the set of vertices selected by him while that of Staller is to prevent this from happening. In this paper MBD game critical graphs are studied. Their existence is established and critical graphs are characterized for most of the cases in which the first player can win the game in one or two moves.
Ključne besede: Maker-Breaker game, Maker-Breaker domination game, Maker-Breaker domination number, Maker-Breaker domination game critical graph
Objavljeno v DKUM: 25.07.2025; Ogledov: 0; Prenosov: 1
 Celotno besedilo (540,67 KB)
Gradivo ima več datotek! Več... |
2. 2-rainbow independent domination in complementary prismsDragana Božović, Gordana Radić, Aleksandra Tepeh, 2025, izvirni znanstveni članek Opis: A function f that assigns values from the set to each vertex of a graph G is called a 2-rainbow independent dominating function, if the vertices assigned the value 1 form an independent set, the vertices assigned the value 2 form another independent set, and every vertex to which 0 is assigned has at least one neighbor in each of the mentioned independent sets. The weight of this function is the total number of vertices assigned nonzero values. The 2-rainbow independent domination number of G, , is the minimum weight of such a function. Motivated by a real-life application, we study the 2-rainbow independent domination number of the complementary prism of a graph G, which is constructed by taking G and its complement , and then adding edges between corresponding vertices. We provide tight bounds for , and characterize graphs for which the lower bound, i.e. , is attained. The obtained results can, in practice, enable the prediction of the cost estimate for a given communication or surveillance network.
Ključne besede: graph theory, domination, 2-rainbow independent domination, complementary prism
Objavljeno v DKUM: 23.04.2025; Ogledov: 0; Prenosov: 6
Celotno besedilo (366,59 KB) |
3. On Grundy total domination number in product graphsBoštjan Brešar, Csilla Bujtás, Tanja Dravec, Sandi Klavžar, Gašper Košmrlj, Tilen Marc, Balázs Patkós, Zsolt Tuza, Máté Vizer, 2021, izvirni znanstveni članek Opis: A longest sequence (v1,....,vk) of vertices of a graph G is a Grundy total dominating sequence of G if for all i, N(vi)\U{j=1}^{i-1} N(vj)≠∅. The length k of the sequence is called the Grundy total domination number of G and denoted ɣ{gr}^{t}(G). In this paper, the Grundy total domination number is studied on four standard graph products. For the direct product we show that ɣ{gr}^{t}(G x H) > ɣ{gr}^{t}(G)ɣ{gr}^{t}(H), conjecture that the equality always holds, and prove the conjecture in several special cases. For the lexicographic product we express ɣ{gr}^{t}(G o H) in terms of related invariant of the factors and find some explicit formulas for it. For the strong product, lower bounds on ɣ{gr}^{t}(G ⊠ H) are proved as well as upper bounds for products of paths and cycles. For the Cartesian product we prove lower and upper bounds on the Grundy total domination number when factors are paths or cycles.
Ključne besede: total domination, Grundy total domination number, graph product
Objavljeno v DKUM: 07.08.2024; Ogledov: 96; Prenosov: 11
Celotno besedilo (248,02 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 Opis: 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 DKUM: 09.08.2023; Ogledov: 446; Prenosov: 56
Celotno besedilo (419,38 KB)
Gradivo ima več datotek! Več... |
5. Roman domination number of the Cartesian products of paths and cyclesPolona Repolusk, Janez Žerovnik, 2012, izvirni znanstveni članek Opis: Roman domination is a historically inspired variety of general domination such that every vertex is labeled with labels from $\{0,1,2\}$. Roman domination number is the smallest of the sums of labels fulfilling condition that every vertex, labeled 0, has a neighbor, labeled 2. Using algebraic approach we give ▫$O(C)$▫ time algorithm for computing Roman domination number of special classes of polygraphs (rota- and fasciagraphs). By implementing the algorithm we give formulas for Roman domination number of the Cartesian products of paths and cycles ▫$P_n \Box P_k$▫, ▫$P_n \Box C_k$▫ for ▫$k \leq 8$▫ and ▫$n \in {\mathbb N}$▫ and for ▫$C_n \Box P_k$▫ and ▫$C_n \Box C_k$▫ for ▫$k \leq 5$▫, ▫$n \in {\mathbb N}$▫. We also give a list of Roman graphs among investigated families.
Ključne besede: graph theory, Roman domination number, Cartesian product, polygraphs, path algebra
Objavljeno v DKUM: 23.08.2017; Ogledov: 1634; Prenosov: 320
Celotno besedilo (719,06 KB)
Gradivo ima več datotek! Več... |
6. Efficient open domination in graph productsDorota Kuziak, Iztok Peterin, Ismael G. Yero, 2014, izvirni znanstveni članek Opis: A graph ▫$G$▫ is an efficient open domination graph if there exists a subset ▫$D$▫ of ▫$V(G)$▫ for which the open neighborhoods centered in vertices of ▫$D$▫ form a partition of ▫$V(G)$▫. We completely describe efficient open domination graphs among lexicographic, strong, and disjunctive products of graphs. For the Cartesian product we give a characterization when one factor is ▫$K_2$▫.
Ključne besede: graph theory, efficient open domination, graph products, total domination
Objavljeno v DKUM: 10.07.2017; Ogledov: 1379; Prenosov: 171
Celotno besedilo (804,78 KB)
Gradivo ima več datotek! Več... |
7. Some results on total domination in direct products of graphsPaul Dorbec, Sylvain Gravier, Sandi Klavžar, Simon Špacapan, izvirni znanstveni članek Opis: Upper and lower bounds on the total domination number of the direct product ofgraphs are given. The bounds involve the ▫$\{2\}$▫-total domination number, the total 2-tuple domination number, and the open packing number of the factors. Using these relationships one exact total domination number is obtained. An infinite family of graphs is constructed showing that the bounds are best possible. The domination number of direct products of graphs is also bounded from below.
Ključne besede: mathematics, graph theory, direktni produkt, total domination, ▫$k$▫-tuple domination, open packing, domination
Objavljeno v DKUM: 31.03.2017; Ogledov: 1234; Prenosov: 481
Celotno besedilo (156,67 KB)
Gradivo ima več datotek! Več... |
8. On Vizing's conjectureBoštjan Brešar, 2001, izvirni znanstveni članek Opis: A dominating set ▫$D$▫ gor a graph ▫$G$▫ is a subset ▫$V(G)$▫ such that any vertex in ▫$V(G)-D$▫ has a neighbor in ▫$D$▫, and a domination number ▫$\gamma(G)$▫ is the size of a minimum dominating set for ▫$G$▫. For the Cartesian product ▫$G \Box H$▫ Vizing's conjecture states that ▫$\gamma(G \Box H) \ge \gamma(G)\gamma(H)$▫ for every pair of graphs ▫$G,H$▫. In this paper we introduce a new concept which extends the ordinary domination of graphs, and prove that the conjecture holds when ▫$\gamma(G) = \gamma(H) = 3$▫.
Ključne besede: mathematics, graph theory, graph, Cartesian product, domination number
Objavljeno v DKUM: 31.03.2017; Ogledov: 1520; Prenosov: 140
Celotno besedilo (126,98 KB)
Gradivo ima več datotek! Več... |
9. Domination game: extremal families of graphs for 3/5-conjecturesBoštjan Brešar, Sandi Klavžar, Gašper Košmrlj, Douglas F. Rall, 2013, izvirni znanstveni članek Opis: Igralca, Dominator in Zavlačevalka, izmenoma izbirata vozlišča grafa ▫$G$▫, takoda vsako izbrano vozlišče poveča množico do sedaj dominiranih vozlišč. Cilj Dominatorja je končati igro čim hitreje, medtem ko je Zavlačevalkin cilj ravno nasprotno. Igralno dominacijsko število ▫$gamma_g(G)$▫ je skupno število izbranih vozlišč v igri, ko Dominator naredi prvo potezo in oba igralca igrata optimalno. Postavljena je bila domneva [W.B. Kinnersley, D.B. West, R. Zemani, Extremal problems for game domination number, Manuscript, 2012], da velja ▫$gamma_g(G) leq frac{3|V(G)|}{5}$▫ za poljuben graf ▫$G$▫ brez izoliranih vozlišč. V posebnem je domneva odprta tudi, ko je ▫$G$▫ gozd. V tem članku predstavimo konstrukcije, ki nam dajo velike družine dreves, ki dosežejo domnevno mejo ▫$3/5$▫. Leplenje dreves iz nekaterih izmed teh družin napoljuben graf nam da konstrukcijo grafov ▫$G$▫, ki imajo igralno dominacijsko število enako ▫$3|V(G)|/5$▫. Z računalnikom smo poiskali vsa ekstremna drevesa znajveč 20 vozlišči. V posebnem, na 20 vozliščih obstaja natanko deset dreves ▫$T$▫, za katere velja ▫$gamma_g(T) = 12$▫, in vsa pripadajo skonstruiranim družinam.
Ključne besede: matematika, teorija grafov, dominacijska igra, igralno dominacijsko številko, 3/5-domneva, računalniško iskanje, mathematics, graph theory, domination game, game domination number, 3/5-conjecture, computer search
Objavljeno v DKUM: 10.07.2015; Ogledov: 1488; Prenosov: 98
 Povezava na celotno besedilo |
10. A note on the domination number of the Cartesian products of paths and cyclesPolona Repolusk, Janez Žerovnik, 2011 Opis: Z uporabo algebraičnega pristopa implementiramo konstantni algoritem za računanje dominantnega števila kartezičnih produktov poti in ciklov. Podamo formule za dominantna števila ▫$gamma(P_n Box C_k)$▫ (za ▫$k leq 11$▫, ▫$n in {mathbb N}$)▫ in dominantna števila ▫$gamma(C_n Box P_k)$▫ in ▫$gamma(C_n Box C_k)$▫ (za ▫$k leq 6$▫, ▫$n in {mathbb N}$▫).
Ključne besede: teorija grafov, kartezični produkt, grid, torus, dominacija, algebra poti, konstantni algoritem, graph theory, Cartesian product, grid graph, torus, graph domination, path algebra, constant time algorithm
Objavljeno v DKUM: 10.07.2015; Ogledov: 1740; Prenosov: 42
Povezava na celotno besedilo |
