1. 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, original scientific article Abstract: 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.
Keywords: total domination, Grundy total domination number, graph product
Published in DKUM: 07.08.2024; Views: 96; Downloads: 11
 Full text (248,02 KB)
This document has many files! More... |
2. Packings in bipartite prisms and hypercubesBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2024, original scientific article Abstract: ▫$2$▫-pakirno število ▫$\rho_2(G)$▫ grafa ▫$G$▫ je kardinalnost največjega ▫$2$▫-pakiranja grafa ▫$G$▫, odprto pakirno število ▫$\rho^{\rm o}(G)$▫ pa kardinalnost največjega odprtega pakiranja grafa ▫$G$▫, kjer je odprto pakiranje (oz. ▫$2$▫ pakiranje) množica vozlišč grafa ▫$G$▫, katerih dve (zaprti) soseščini se ne sekata. Dokazano je, da če je ▫$G$▫ dvodelen, potem je ▫$\rho^{\rm o}(G\Box K_2) = 2\rho_2(G)$▫. Za hiperkocke sta določeni spodnji meji ▫$\rho_2(Q_n) \ge 2^{n - \lfloor \log n\rfloor -1}$▫ in ▫$\rho^{\rm o}(Q_n) \ge 2^{n - \lfloor \log (n-1)\rfloor -1}$▫. Te ugotovitve so uporabljene za injektivna barvanja hiperkock. Dokazano je, da je ▫$Q_9$▫ najmanjša hiperkocka, ki ni popolno injektivno obarvljiva. Dokazano je tudi, da je ▫$\gamma_t(Q_{2^k}\times H) = 2^{2^k-k}\gamma_t(H)$▫, kjer je ▫$H$▫ poljuben graf brez izoliranih vozlišč.
Keywords: 2-pakirno število, odprto pakirno število, dvodelna prizma, hiperkocke, injektivno barvanje, celotno dominacijsko število, 2-packing number, open packing number, bipartite prism, hypercube, injective coloring, total domination number
Published in DKUM: 28.02.2024; Views: 260; Downloads: 10
 Link to full text |
3. Orientable domination in product-like graphsSarah Anderson, Boštjan Brešar, Sandi Klavžar, Kirsti Kuenzel, Douglas F. Rall, 2023, original scientific article Abstract: 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].
Keywords: digraph, domination, orientable domination number, packing, graph product, corona graph
Published in DKUM: 09.08.2023; Views: 446; Downloads: 54
Full text (419,38 KB)
This document has many files! More... |
4. More results on the domination number of Cartesian product of two directed cyclesAnsheng Ye, Fang Miao, Zehui Shao, Jia-Bao Liu, Janez Žerovnik, Polona Repolusk, 2019, original scientific article Abstract: Let γ(D) denote the domination number of a digraph D and let C$_m$□C$_n$ denote the Cartesian product of C$_m$ and C$_n$, the directed cycles of length n ≥ m ≥ 3. Liu et al. obtained the exact values of γ(C$_m$□C$_n$) for m up to 6 [Domination number of Cartesian products of directed cycles, Inform. Process. Lett. 111 (2010) 36–39]. Shao et al. determined the exact values of γ(C$_m$□C$_n$) for m = 6, 7 [On the domination number of Cartesian product of two directed cycles, Journal of Applied Mathematics, Volume 2013, Article ID 619695]. Mollard obtained the exact values of γ(C$_m$□C$_n$) for m = 3k + 2 [M. Mollard, On domination of Cartesian product of directed cycles: Results for certain equivalence classes of lengths, Discuss. Math. Graph Theory 33(2) (2013) 387–394.]. In this paper, we extend the current known results on C$_m$□C$_n$ with m up to 21. Moreover, the exact values of γ(C$_n$□C$_n$) with n up to 31 are determined.
Keywords: domination number, Cartesian product, directed cycle
Published in DKUM: 02.09.2022; Views: 611; Downloads: 13
Link to full text |
5. Roman domination number of the Cartesian products of paths and cyclesPolona Repolusk, Janez Žerovnik, 2012, original scientific article Abstract: 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.
Keywords: graph theory, Roman domination number, Cartesian product, polygraphs, path algebra
Published in DKUM: 23.08.2017; Views: 1634; Downloads: 258
Full text (719,06 KB)
This document has many files! More... |
6. How long can one bluff in the domination game?Boštjan Brešar, Paul Dorbec, Sandi Klavžar, Gašper Košmrlj, 2017, original scientific article Abstract: The domination game is played on an arbitrary graph ▫$G$▫ by two players, Dominator and Staller. The game is called Game 1 when Dominator starts it, and Game 2 otherwise. In this paper bluff graphs are introduced as the graphs in which every vertex is an optimal start vertex in Game 1 as well as in Game 2. It is proved that every minus graph (a graph in which Game 2 finishes faster than Game 1) is a bluff graph. A non-trivial infinite family of minus (and hence bluff) graphs is established. Minus graphs with game domination number equal to 3 are characterized. Double bluff graphs are also introduced and it is proved that Kneser graphs ▫$K(n,2)$▫, za ▫$n \ge 6$▫, are double bluff. The domination game is also studied on generalized Petersen graphs and on Hamming graphs. Several generalized Petersen graphs that are bluff graphs but not vertex-transitive are found. It is proved that Hamming graphs are not double bluff.
Keywords: domination game, game domination number, bluff graphs, minus graphs, generalized Petersen graphs, Kneser graphs, Cartesian product of graphs, Hamming graphs
Published in DKUM: 09.05.2017; Views: 1348; Downloads: 464
Full text (56,60 KB)
This document has many files! More... |
7. On Vizing's conjectureBoštjan Brešar, 2001, original scientific article Abstract: 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$▫.
Keywords: mathematics, graph theory, graph, Cartesian product, domination number
Published in DKUM: 31.03.2017; Views: 1520; Downloads: 126
Full text (126,98 KB)
This document has many files! More... |
8. Domination game: extremal families of graphs for 3/5-conjecturesBoštjan Brešar, Sandi Klavžar, Gašper Košmrlj, Douglas F. Rall, 2013, original scientific article Abstract: 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.
Keywords: 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
Published in DKUM: 10.07.2015; Views: 1488; Downloads: 96
Link to full text |
9. Domination game played on trees and spanning subgraphsBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2013, original scientific article Abstract: Igra dominacije na grafu ▫$G$▫ je bila vpeljana v [B. Brešar, S. Klavžar, D. F. Rall, Domination game and an imagination strategy, SIAM J. Discrete Math. 24 (2010) 979-991]. Dva igralca, Dominator in Zavlačevalec, drug za drugim izbirata po eno vozlišče grafa. Vsako izbrano vozlišče mora povečati množico vozlišč, ki so bila dominirana do tega trenutka igre. Oba igralca izbirata optimalno strategijo, pri čemer Dominator želi igro končati v najmanjšem možnem številu korakov, Zavlačevalec pa v največjem možnem številu korakov. Igralno dominacijsko število ▫$gamma_g(G)$▫ je število izbranih vozlišč v igri, kjer je Dominator prvi izbral vozlišče. Ustrezno invarianto, ko igro začne Zavlačevalec, označimo z ▫$gamma_g'(G)$▫. V članku sta obe igri proučevani na drevesih in vpetih podgrafih. Dokazana je spodnja meja za igralno dominacijsko število drevesa, ki je funkcija njegovega reda in maksimalne stopnje. Pokazano je, da je meja asimptotično optimalna. Dokazano je, da za vsak ▫$k$▫ obstaja drevo ▫$T$▫ z ▫$(gamma_g(T),gamma_g'(T)) = (k,k+1)$▫ in postavljena je domneva, da ne obstaja drevo z ▫$(gamma_g(T),gamma_g'(T)) = (k,k-1)$▫. Obravnavana je povezava med igralnim dominacijskim številom grafa in njegovimi vpetimi podgrafi. Dokazano je, da obstajajo 3-povezani grafi ▫$G$▫, ki vsebujejo 2-povezani vpeti podgraf ▫$H$▫, tako da je igralno dominacijsko število grafa ▫$H$▫ poljubno manjše od igralnega dominacijskega števila grafa ▫$G$▫. Podobno je dokazano, da za vsako celo število ▫$ell ge 1$▫ obstajata graf ▫$G$▫ in njegov vpeti podgraf $T$, tako da velja ▫$gamma_g(G)-gamma_g(T) ge ell$▫. Po drugi strani obstajajo grafi ▫$G$▫, za katere je igralno dominacijsko število vsakega vpetega drevesa v ▫$G$▫ poljubno večje od igralnega dominacijskega števila od ▫$G$▫.
Keywords: igra dominacije, igralno dominacijsko število, drevo, vpeti podgraf, graph theory, domination game, game domination number, tree, spanning subgraph
Published in DKUM: 10.07.2015; Views: 1349; Downloads: 95
Link to full text |
10. Roman domination number of the Cartesian products of paths and cyclesPolona Repolusk, Janez Žerovnik, 2011, original scientific article Abstract: Rimska dominacija je zgodovinsko utemeljena različica običajne dominacije, pri kateri vozlišča grafa označimo z oznakami iz množice ▫${0,1,2}$▫ tako, da ima vsako vozlišče z oznako 0 soseda z oznako 2. Najmanjšo izmed vsot oznak grafa imenujemo rimsko dominantno število grafa. Z uporabo algebraičnega pristopa dobimo konstantni algoritem za računanje rimskega dominantnega števila posebne vrste poligrafov: rota- in fasciagrafov. V posebnih primerih izračunamo formule za rimsko dominanto število kartezičnega produkta poti in ciklov ▫$P_n Box P_k$▫, ▫$P_n Box C_k$▫ za ▫$k leq 8$▫ in ▫$n in {mathbb N}$▫ ter za ▫$C_n Box P_k$▫ in ▫$C_n Box C_k$▫ za ▫$k leq 5$▫, ▫$n in {mathbb N}$▫. Dodan je seznam rimskih grafov med kartezičnimi produkti zgoraj omenjenih poti in ciklov.
Keywords: teorija grafov, kartezični produkt, rimsko dominantno število, poligrafi, algebra poti, graph theory, Roman domination number, Cartesian product, polygraphs, path algebra
Published in DKUM: 10.07.2015; Views: 1762; Downloads: 75
Link to full text |
