1. A new framework to approach Vizing's conjectureBoštjan Brešar, Bert L. Hartnell, Michael A. Henning, Kirsti Kuenzel, Douglas F. Rall, 2021, original scientific article Abstract: 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. Keywords: Cartesian product, total domination, Vizing's conjecture, Clark and Suen bound Published in DKUM: 09.08.2024; Views: 28; Downloads: 0 Full text (179,75 KB) This document has many files! More... |
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, 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: 51; Downloads: 2 Full text (248,02 KB) This document has many files! More... |
3. 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: 227; Downloads: 4 Link to full text |
4. 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: 427; Downloads: 37 Full text (419,38 KB) This document has many files! More... |
5. 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: 564; Downloads: 10 Link to full text |
6. Contributions to the Study of Contemporary Domination Invariants of Graphs2019, doctoral dissertation Abstract: 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. Keywords: 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 Published in DKUM: 23.10.2019; Views: 1522; Downloads: 40 Full text (764,69 KB) This document has many files! More... |
7. Clarifying power, domination, and exploitation : between "classical" and "Foucauldian" concepts of powerTibor Rutar, 2017, original scientific article Abstract: The paper examines two ubiquitous concepts of power: the "classical sociological" concept which draws on Max Weber's definition of power, and the "Foucauldian" concept which stems from Michel Foucault's genealogical works. Three main theses are argued for. First, the two concepts are not, in most respects, as radically different as it is usually claimed. It is demonstrated that both can make room for different sources of power, for understanding power in a non-reified way, for the fact that power is rarely completely centralised, etc. Second, in those respects in which the two concepts actually differ, the classical view of power is more convincing and useful than the Foucauldian one. It is demonstrated that the Foucauldian view is implicitly positivist in the normative domain and thus unable to differentiate between power and domination, and that it succumbs to errors of methodological holism (i. e. undertheorising agency). Third, it is argued that the classical sociological view allows to analytically distinguish between power, domination and exploitation. These three categories are shown not to be synonymous and to carry with them importantly different sociological implications. It is demonstrated that exploitation cannot merely refer to any process of unpaid appropriation of surplus as obvious false positives are generated from this definition. Nonetheless, such appropriation is the fundamental characteristic which differentiates exploitation from domination (but not power itself), and this reveals an important sociological implication for the dynamics of struggle of the exploited against exploitation in contrast to the struggle of the dominated against the dominators. Keywords: power, domination, exploitation, Foucault, value-neutrality Published in DKUM: 24.10.2017; Views: 1483; Downloads: 162 Full text (423,22 KB) This document has many files! More... |
8. 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: 1590; Downloads: 243 Full text (719,06 KB) This document has many files! More... |
9. 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, original scientific article Abstract: 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. Keywords: efficient open domination, Cartesian product, vertex labeling, total domination Published in DKUM: 10.07.2017; Views: 1061; Downloads: 161 Full text (166,60 KB) This document has many files! More... |
10. Open $k$-monopolies in graphs: complexity and related conceptsDorota Kuziak, Iztok Peterin, Ismael G. Yero, 2016, original scientific article Abstract: 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. Keywords: open k-monopolies, k-signed total domination, global defensive k-alliance, global offensive k-alliance Published in DKUM: 10.07.2017; Views: 1152; Downloads: 148 Full text (181,59 KB) This document has many files! More... |