1. 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 ZGrundy domination number, and the LGrundy domination number. Some bounds and properties of Grundy domination invariants are proven. All four Grundy domination parameters are studied on trees, bipartite distancehereditary 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 NPcompleteness 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, ZGrundy domination, LGrundy 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: 23.10.2019; Views: 429; Downloads: 11 Full text (764,69 KB) This document has many files! More...

2. 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: 23.08.2017; Views: 529; Downloads: 140 Full text (719,06 KB) This document has many files! More...

3. 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 5cycle or a 4cycle. Keywords: efficient open domination, Cartesian product, vertex labeling, total domination Published: 10.07.2017; Views: 362; Downloads: 75 Full text (166,60 KB) This document has many files! More...

4. 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 nontrivial 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 vertextransitive 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: 09.05.2017; Views: 569; Downloads: 322 Full text (56,60 KB) This document has many files! More...

5. Weak kreconstruction of Cartesian productsWilfried Imrich, Blaž Zmazek, Janez Žerovnik, 2003, original scientific article Abstract: By Ulam's conjecture every finite graph ▫$G$▫ can be reconstructed from its deck of vertex deleted subgraphs. The conjecture is still open, but many special cases have been settled. In particular, one can reconstruct Cartesian products. We consider the case of ▫$k$▫vertex deleted subgraphs of Cartesian products and prove that one can decide whether a graph ▫$H$▫ is a ▫$k$▫vertex deleted subgraph of a Cartesian product ▫$G$▫ with at least ▫$k+1$▫ prime factors on at least ▫$k+1$▫ vertices each, and that ▫$H$▫ uniquely determines ▫$G$▫. This extends previous works of the authors and Sims. This paper also contains a counterexample to a conjecture of MacAvaney. Keywords: mathematics, graph theory, reconstruction problem, Cartesian product, composite graphs Published: 31.03.2017; Views: 766; Downloads: 277 Full text (197,33 KB) This document has many files! More...

6. The periphery graph of a median graphBoštjan Brešar, Manoj Changat, Ajitha R. Subhamathi, Aleksandra Tepeh, 2010, original scientific article Abstract: The periphery graph of a median graph is the intersection graph of its peripheral subgraphs. We show that every graph without a universal vertex can be realized as the periphery graph of a median graph. We characterize those median graphs whose periphery graph is the join of two graphs and show that they are precisely Cartesian products of median graphs. Pathlike median graphs are introduced as the graphs whose periphery graph has independence number 2, and it is proved that there are pathlike median graphs with arbitrarily large geodetic number. Peripheral expansion with respect to periphery graph is also considered, and connections with the concept of crossing graph are established. Keywords: mathematics, graph theory, median graph, Cartesian product, geodesic, periphery, peripheral expansion Published: 31.03.2017; Views: 754; Downloads: 288 Full text (145,86 KB) This document has many files! More...

7. Recognizing weighted directed Cartesian graph bundlesBlaž Zmazek, Janez Žerovnik, 2000, original scientific article Abstract: In this paper we show that methods for recognizing Cartesian graph bundles can be generalized to weighted digraphs. The main result is an algorithm which lists the sets of degenerate arcs for all representations of digraph as a weighted directed Cartesian graph bundle over simple base digraphs not containing transitive tournament on three vertices. Two main notions are used.The first one is the new relation ▫$\vec{\delta}^\ast$▫ defined among the arcs of a digraph as a weighted directed analogue of the wellknown relation ▫$\delta^\ast$▫. The second one is the concept of halfconvex subgraphs. A subgraph ▫$H$▫ is halfconvex in ▫$G$▫ if any vertex ▫$x \in G \setminus H$▫ has at most one predecessor and at most one successor Keywords: mathematics, graph theory, graph bundles, Cartesian graph product, weighted digraphs, halfconvexity Published: 31.03.2017; Views: 550; Downloads: 266 Full text (240,86 KB) This document has many files! More...

8. 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: 31.03.2017; Views: 670; Downloads: 74 Full text (126,98 KB) This document has many files! More...

9. On the rainbow connection of Cartesian products and their subgraphsSandi Klavžar, Gašper Mekiš, 2012, original scientific article Abstract: Rainbow connection number of Cartesian products and their subgraphs are considered. Previously known bounds are compared and nonexistence of such bounds for subgraphs of products are discussed. It is shown that the rainbow connection number of an isometric subgraph of a hypercube is bounded above with the rainbow connection number of the hypercube. Isometric subgraphs of hypercubes with the rainbow connection number smaller as much as possible than the rainbow connection of the hypercube are constructed. The concept of cstrong rainbow coloring is introduced. In particular it is proved that the socalled ▫$\Theta$▫coloring of an isometric subgraph of a hypercube is its unique optimal cstrong rainbow coloring. Keywords: graph theory, rainbow connection, strong rainbow connection, Cartesian product of graphs, isometric subgraph, hypercube Published: 31.03.2017; Views: 557; Downloads: 271 Full text (125,60 KB) This document has many files! More...

10. On [Theta]graphs of partial cubesSandi Klavžar, Matjaž Kovše, 2007, original scientific article Abstract: The ▫$\Theta$▫graph ▫$\Theta(G)$▫ of a partial cube ▫$G$▫ is the intersection graph of the equivalence classes of the DjokovicWinkler relation. ▫$\Theta$▫graphs that are 2connected, trees, or complete graphs are characterized. In particular, ▫$\Theta(G)$▫ is complete if and only if ▫$G$▫ can be obtained from ▫$K_1$▫ by a sequence of (newly introduced) dense expansions. ▫$\Theta$▫graphs are also compared with familiar concepts of crossing graphs and ▫$\tau$▫graphs. Keywords: mathematics, graph theory, intersection graph, partial cube, median graph, expansion theorem, Cartesian product of graphs Published: 31.03.2017; Views: 444; Downloads: 64 Full text (150,56 KB) This document has many files! More...
