1. 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 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. Ključne besede: 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 Objavljeno: 23.10.2019; Ogledov: 566; Prenosov: 11 Celotno besedilo (764,69 KB) Gradivo ima več datotek! Več...

2. 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: 23.08.2017; Ogledov: 649; Prenosov: 153 Celotno besedilo (719,06 KB) Gradivo ima več datotek! Več...

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, 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 5cycle or a 4cycle. Ključne besede: efficient open domination, Cartesian product, vertex labeling, total domination Objavljeno: 10.07.2017; Ogledov: 452; Prenosov: 83 Celotno besedilo (166,60 KB) Gradivo ima več datotek! Več...

4. How long can one bluff in the domination game?Boštjan Brešar, Paul Dorbec, Sandi Klavžar, Gašper Košmrlj, 2017, izvirni znanstveni članek Opis: 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. Ključne besede: domination game, game domination number, bluff graphs, minus graphs, generalized Petersen graphs, Kneser graphs, Cartesian product of graphs, Hamming graphs Objavljeno: 09.05.2017; Ogledov: 672; Prenosov: 361 Celotno besedilo (56,60 KB) Gradivo ima več datotek! Več...

5. Weak kreconstruction of Cartesian productsWilfried Imrich, Blaž Zmazek, Janez Žerovnik, 2003, izvirni znanstveni članek Opis: 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. Ključne besede: mathematics, graph theory, reconstruction problem, Cartesian product, composite graphs Objavljeno: 31.03.2017; Ogledov: 852; Prenosov: 296 Celotno besedilo (197,33 KB) Gradivo ima več datotek! Več...

6. The periphery graph of a median graphBoštjan Brešar, Manoj Changat, Ajitha R. Subhamathi, Aleksandra Tepeh, 2010, izvirni znanstveni članek Opis: 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. Ključne besede: mathematics, graph theory, median graph, Cartesian product, geodesic, periphery, peripheral expansion Objavljeno: 31.03.2017; Ogledov: 860; Prenosov: 308 Celotno besedilo (145,86 KB) Gradivo ima več datotek! Več...

7. Recognizing weighted directed Cartesian graph bundlesBlaž Zmazek, Janez Žerovnik, 2000, izvirni znanstveni članek Opis: 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 Ključne besede: mathematics, graph theory, graph bundles, Cartesian graph product, weighted digraphs, halfconvexity Objavljeno: 31.03.2017; Ogledov: 624; Prenosov: 289 Celotno besedilo (240,86 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: 31.03.2017; Ogledov: 759; Prenosov: 80 Celotno besedilo (126,98 KB) Gradivo ima več datotek! Več...

9. 
10. On [Theta]graphs of partial cubesSandi Klavžar, Matjaž Kovše, 2007, izvirni znanstveni članek Opis: 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. Ključne besede: mathematics, graph theory, intersection graph, partial cube, median graph, expansion theorem, Cartesian product of graphs Objavljeno: 31.03.2017; Ogledov: 535; Prenosov: 67 Celotno besedilo (150,56 KB) Gradivo ima več datotek! Več...
