1. A new framework to approach Vizing's conjectureBoštjan Brešar, Bert L. Hartnell, Michael A. Henning, Kirsti Kuenzel, Douglas F. Rall, 2021, izvirni znanstveni članek Opis: We introduce a new setting for dealing with the problem of the domination number of the Cartesian product of graphs related to Vizing's conjecture. The new framework unifies two different approaches to the conjecture. The most common approach restricts one of the factors of the product to some class of graphs and proves the inequality of the conjecture then holds when the other factor is any graph. The other approach utilizes the so-called Clark-Suen partition for proving a weaker inequality that holds for all pairs of graphs. We demonstrate the strength of our framework by improving the bound of Clark and Suen as follows: ɣ(X◻Y) ≥ max{1/2ɣ(X) ɣt(Y), 1/2ɣt(X) ɣ(Y)}, where ɣ stands for the domination number, ɣt is the total domination number, and X◻Y is the Cartesian product of graphs X and Y.
Ključne besede: Cartesian product, total domination, Vizing's conjecture, Clark and Suen bound
Objavljeno v DKUM: 09.08.2024; Ogledov: 86; Prenosov: 7
 Celotno besedilo (179,75 KB)
Gradivo ima več datotek! Več... |
2. 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: 7
Celotno besedilo (248,02 KB)
Gradivo ima več datotek! Več... |
3. Packings in bipartite prisms and hypercubesBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2024, izvirni znanstveni članek Opis: ▫$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šč.
Ključne besede: 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
Objavljeno v DKUM: 28.02.2024; Ogledov: 260; Prenosov: 5
 Povezava na celotno besedilo |
4. Contributions to the Study of Contemporary Domination Invariants of Graphs2019, doktorska disertacija Opis: This doctoral dissertation is devoted to contemporary domination concepts, such as the Grundy domination, the convex domination, the isometric domination and the total domination. Our main focus is to study their structure and algorithmic properties. Four Grundy domination invariants are presented, namely the Grundy domination number, the Grundy total domination number, the Z-Grundy domination number, and the L-Grundy domination number. Some bounds and properties of Grundy domination invariants are proven. All four Grundy domination parameters are studied on trees, bipartite distance-hereditary graphs, split graphs, interval graphs, Sierpi\'nski graphs, Kneser graphs and $P_4$-tidy graphs. Graphs with equal total domination number and Grundy total domination number are investigated.
Convex domination and isometric domination are studied on (weak) dominating pair graphs. For the chordal dominating pair graphs we present a polynomial algorithm to compute the convex domination number, and prove the NP-completeness of the corresponding decision problem for the chordal weak dominating pair graphs. For the isometric domination number of weak dominating pair graphs an efficient algorithm is presented.
Total domination is studied on the Cartesian product of graphs. We dedicate ourselves to graphs for which the equality holds in Ho's theorem, which states that the total domination number of the Cartesian product of any two graphs without isolated vertices is at least one half of the product of their total domination numbers.
Ključne besede: Grundy domination, Grundy total domination, Z-Grundy domination, L-Grundy domination, convex domination, isometric domination, total domination, trees, split graphs, interval graphs, Sierpi\'nski graphs, Kneser graphs, modular decomposition, dominating pair graphs, Cartesian product
Objavljeno v DKUM: 23.10.2019; Ogledov: 1549; Prenosov: 43
Celotno besedilo (764,69 KB)
Gradivo ima več datotek! Več... |
5. Partitioning the vertex set of ▫$G$▫ to make ▫$G \Box H$▫ an efficient open domination graphTadeja Kraner Šumenjak, Iztok Peterin, Douglas F. Rall, Aleksandra Tepeh, 2016, izvirni znanstveni članek Opis: A graph is an efficient open domination graph if there exists a subset of vertices whose open neighborhoods partition its vertex set. We characterize those graphs ▫$G$▫ for which the Cartesian product ▫$G \Box H$▫ is an efficient open domination graph when ▫$H$▫ is a complete graph of order at least 3 or a complete bipartite graph. The characterization is based on the existence of a certain type of weak partition of ▫$V(G)$▫. For the class of trees when ▫$H$▫ is complete of order at least 3, the characterization is constructive. In addition, a special type of efficient open domination graph is characterized among Cartesian products ▫$G \Box H$▫ when ▫$H$▫ is a 5-cycle or a 4-cycle.
Ključne besede: efficient open domination, Cartesian product, vertex labeling, total domination
Objavljeno v DKUM: 10.07.2017; Ogledov: 1085; Prenosov: 164
Celotno besedilo (166,60 KB)
Gradivo ima več datotek! Več... |
6. Open $k$-monopolies in graphs: complexity and related conceptsDorota Kuziak, Iztok Peterin, Ismael G. Yero, 2016, izvirni znanstveni članek Opis: Closed monopolies in graphs have a quite long range of applications in several problems related to overcoming failures, since they frequently have some common approaches around the notion of majorities, for instance to consensus problems, diagnosis problems or voting systems. We introduce here open ▫$k$▫-monopolies in graphs which are closely related to different parameters in graphs. Given a graph ▫$G=(V,E)$▫ and ▫$X \subseteq V$▫, if ▫$\delta_X(v)$▫ is the number of neighbors ▫$v$▫ has in ▫$X$▫, ▫$k$▫ is an integer and ▫$t$▫ is a positive integer, then we establish in this article a connection between the following three concepts: (1) Given a nonempty set ▫$M\subseteq V$▫ a vertex ▫$v$▫ of ▫$G$▫ is said to be ▫$k$▫-controlled by ▫$M$▫ if ▫$\delta_M(v)\ge \frac{\delta_V(v)}{2}+k$▫. The set ▫$M$▫ is called an open ▫$k$▫-monopoly for ▫$G$▫ if it ▫$k$▫-controls every vertex ▫$v$▫ of ▫$G$▫. (2) A function ▫$f: V\rightarrow \{-1,1\}$▫ is called a signed total ▫$t$▫-dominating function for ▫$G$▫ if ▫$f(N(v))=\sum_{v\in N(v)}f(v)\geq t$▫ for all ▫$v\in V$▫. (3) A nonempty set ▫$S\subseteq V$▫ is a global (defensive and offensive) ▫$k$▫-alliance in ▫$G$▫ if ▫$\delta_S(v)\ge \delta_{V-S}(v)+k$▫ holds for every ▫$v\in V$▫. In this article we prove that the problem of computing the minimum cardinality of an open ▫$0$▫-monopoly in a graph is NP-complete even restricted to bipartite or chordal graphs. In addition we present some general bounds for the minimum cardinality of open ▫$k$▫-monopolies and we derive some exact values.
Ključne besede: open k-monopolies, k-signed total domination, global defensive k-alliance, global offensive k-alliance
Objavljeno v DKUM: 10.07.2017; Ogledov: 1172; Prenosov: 152
Celotno besedilo (181,59 KB)
Gradivo ima več datotek! Več... |
7. 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: 156
Celotno besedilo (804,78 KB)
Gradivo ima več datotek! Več... |
8. 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: 415
Celotno besedilo (156,67 KB)
Gradivo ima več datotek! Več... |
9. New results on variants of covering codes in Sierpiński graphsSylvain Gravier, Matjaž Kovše, Michel Mollard, Julien Moncel, Aline Perreau, 2013, izvirni znanstveni članek Opis: V prispevku obravnavamo identifikacijske kode, lokalno-dominacijske kode in totalno-dominacijske kode v grafih Sierpińskega. Podani so izračuni minimalnih vrednosti teh kod v grafih Sierpińskega.
Ključne besede: kode v grafih, identifikacijske kode, lokalno-dominacijske kode, totalna-dominacija, grafi Sierpińskega, codes in graphs, identifying codes, locating-dominating codes, total-domination, Sierpiński graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 1302; Prenosov: 95
Povezava na celotno besedilo |
10. Lower bounds for domination and total domination number of direct products graphsGašper Mekiš, 2009 Opis: An exact lower bound for the domination number and the total domination number of the direct product of finitely many complete graphs is given: ▫$gamma(times_{i=1}^t K_{n_i} ge t+1$▫, ▫$t ge 3$▫. Sharpness is established in the case when the factors are large enough in comparison to the number of factors. The main result gives a lower bound for the domination (and the total domination) number of the direct product of two arbitrary graphs: ▫$gamma(G times H) ge gamma(G) + gamma(H) - 1$▫. Infinite families of graphs that attain the bound are presented. For these graphs it also holds ▫$gamma_t(G times H) = gamma(G) + gamma(H) - 1$▫. Some additional parallels with the total domination number are made.
Ključne besede: matematika, teorija grafov, dominacijska množica, dominacijsko število, celotna dominacijska množica, celotno dominacijsko število, direktni produkt grafov, poln graf, mathematics, graph theory, dominating set, domination number, total dominating set, total domination number, direct product graphs, complete graphs
Objavljeno v DKUM: 10.07.2015; Ogledov: 1305; Prenosov: 39
Povezava na celotno besedilo |
