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: 542; Prenosov: 11 Celotno besedilo (764,69 KB) Gradivo ima več datotek! Več...

2. 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: 651; Prenosov: 361 Celotno besedilo (56,60 KB) Gradivo ima več datotek! Več...

3. 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: 834; Prenosov: 295 Celotno besedilo (197,33 KB) Gradivo ima več datotek! Več...

4. 
5. 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: 520; Prenosov: 66 Celotno besedilo (150,56 KB) Gradivo ima več datotek! Več...

6. Edgetransitive lexicographic and cartesian productsWilfried Imrich, Ali Iranmanesh, Sandi Klavžar, Abolghasem Soltani, 2016, izvirni znanstveni članek Opis: In this note connected, edgetransitive lexicographic and Cartesian products are characterized. For the lexicographic product ▫$G \circ H$▫ of a connected graph ▫$G$▫ that is not complete by a graph ▫$H$▫, we show that it is edgetransitive if and only if ▫$G$▫ is edgetransitive and ▫$H$▫ is edgeless. If the first factor of ▫$G \circ H$▫ is nontrivial and complete, then ▫$G \circ H$▫ is edgetransitive if and only if ▫$H$▫ is the lexicographic product of a complete graph by an edgeless graph. This fixes an error of Li, Wang, Xu, and Zhao (Appl. Math. Lett. 24 (2011) 19241926). For the Cartesian product it is shown that every connected Cartesian product of at least two nontrivial factors is edgetransitive if and only if it is the Cartesian power of a connected, edge and vertextransitive graph. Ključne besede: edgetransitive graph, vertextransitive graph, lexicographic product of graphs, Cartesian product of graphs Objavljeno: 31.03.2017; Ogledov: 561; Prenosov: 340 Celotno besedilo (150,33 KB) Gradivo ima več datotek! Več...

7. Bucolic complexesBoštjan Brešar, Jérémie Chalopin, Victor Chepoi, Tanja Gologranc, Damian Osajda, 2013, izvirni znanstveni članek Opis: Vpeljemo in obravnavamo bukolične kompleksne, skupno posplošitev sistoličnih in CAT(0) kubnih kompleksov. Definirani so kot enostavno povezani kompleksi prizem, ki zadoščajo določenim lokalnim kombinatornim pogojem. Raziskujemo različne pristope k bukoličnim kompleksom: gledamo jih iz vidika teorije grafov in topološkega vidika kot tudi iz perspektive geometrijske teorije grup. Tako med drugim okarakteriziramo bukolične komplekse preko nekih lastnosti njihovih 2skeletov in 1skeletov (ki jim pravimo bukolični grafi), s čimer posplošimo več prej znanih rezultatov. Prav tako dokažemo, da so lokalno končni bukolični kompleksi kontraktibilni in da zadoščajo nekim lastnostim tipa nepozitivnih ukrivljenosti. Ključne besede: CAT(0) kubni in sistolični kompleksi, medianski in mostovni grafi, zastražena amalgamacija, kartezični produkt, kompleksi prizem, retrakti, fiksne točke, asferičnost, CAT(0) cubical and systolic complexes, median and bridged graphs, gated amalgamation, Cartesian product, prism complexes, retracts, fixed points, asphericity Objavljeno: 10.07.2015; Ogledov: 673; Prenosov: 18 Povezava na celotno besedilo 
8. Bucolic complexesBoštjan Brešar, Jérémie Chalopin, Victor Chepoi, Tanja Gologranc, Damian Osajda, 2012, izvirni znanstveni članek Opis: In this article, we introduce and investigate bucolic complexes, a common generalization of systolic complexes and of CAT(0) cubical complexes. This class of complexes is closed under Cartesian products and amalgamations over some convex subcomplexes. We study various approaches to bucolic complexes: from graphtheoretic and topological viewpoints, as well as from the point of view of geometric group theory. Bucolic complexes can be defined as locallyfinite simply connected prism complexes satisfying some local combinatorial conditions. We show that bucolic complexes are contractible, and satisfy some nonpositivecurvaturelike properties. In particular, we prove a version of the CartanHadamard theorem, the fixed point theorem for finite group actions, and establish some results on groups acting geometrically on such complexes. We also characterize the 1skeletons (which we call bucolic graphs) and the 2skeletons of bucolic complexes. In particular, we prove that bucolic graphs are precisely retracts of Cartesian products of locally finite weakly bridged graphs (i.e., of 1skeletons of weakly systolic complexes). We show that bucolic graphs are exactly the weakly modular graphs satisfying some local conditions formulated in terms of forbidden induced subgraphs and that finite bucolic graphs can be obtained by gated amalgamations of products of weakly bridged graphs. Ključne besede: CAT(0) kubni in sistolični kompleksi, medianski in mostovni grafi, zastražena amalgamacija, kartezični produkt, prizmični kompleksi, retrakti, fiksne točke, asferičnost, CAT(0) cubical and systolic complexes, median and bridged graphs, gated amalgamation, Cartesian product, prism complexes, retracts, fixed points, asphericity Objavljeno: 10.07.2015; Ogledov: 629; Prenosov: 17 Povezava na celotno besedilo 
9. The kindependence number of direct products of graphs and Hedetniemi's conjectureSimon Špacapan, 2011, izvirni znanstveni članek Opis: The ▫$k$▫independence number of ▫$G$▫, denoted as ▫$alpha_k(G)$▫, is the size of a largest ▫$k$▫colorable subgraph of ▫$G$▫. The direct product of graphs ▫$G$▫ and ▫$H$▫, denoted as ▫$G times H$▫, is the graph with vertex set ▫$V(G) times V(H)$▫, where two vertices ▫$(x_1, y_1)$▫ and ▫$(x_2, y_2)$▫ are adjacent in ▫$G times H$▫, if ▫$x_1$▫ is adjacent to ▫$x_2$▫ in ▫$G$▫ and ▫$y_1$▫ is adjacent to ▫$y_2$▫ in ▫$H$▫. We conjecture that for any graphs ▫$G$▫ and ▫$H$▫, ▫$$alpha_k(G times H) ge alpha_k(G)V(H) + alpha_k(H)V(G)  alpha_k(G) alpha_k(H).$$▫ The conjecture is stronger than Hedetniemi's conjecture. We prove the conjecture for ▫$k = 1, 2$▫ and prove that ▫$alpha_k(G times H) ge alpha_k(G)V(H) + alpha_k(H)V(G)  alpha_k(G) alpha_k(H)$▫ holds for any ▫$k$▫. Ključne besede: matematika, teorija grafov, neodvisnostno število, kartezični produkt grafov, mathematics, graph theory, independence number, Cartesian product of graphs Objavljeno: 10.07.2015; Ogledov: 789; Prenosov: 18 Povezava na celotno besedilo 
10. Retracts of products of chordal graphsBoštjan Brešar, Jérémie Chalopin, Victor Chepoi, Matjaž Kovše, Arnaud Labourel, Yann Vaxès, 2010 Opis: We characterize the graphs ▫$G$▫ that are retracts of Cartesian products of chordal graphs. We show that they are exactly the weakly modular graphs that do not contain ▫$K_{2;3}$▫, ▫$k$▫wheels ▫$W_k$▫, and ▫$k$▫wheels minus one spoke T$W_k^ ; (k ge 4)$T as induced subgraphs. We also show that these graphs ▫$G$▫ are exactly the cageamalgamation graphs introduced by Brešar and Tepeh Horvat (2009); this solves the open question raised by these authors. Finally, we prove that replacing all products of cliques of $G$ by products of "solid" simplices, we obtain a polyhedral cell complex which, endowed with an intrinsic Euclidean metric, is a CAT(0) space. This generalizes similar results about median graphs as retracts of hypercubes (products of edges) and median graphs as 1skeletons of CAT(0) cubical complexes. Ključne besede: teorija grafov, graf, retrakt, zastražena amalgamacija, tetiven graf, kartezični produkt grafov, medianski graf, graph theory, graph, retract, gated amalgamation, chordal graph, Cartesian product of graphs, median graph Objavljeno: 10.07.2015; Ogledov: 559; Prenosov: 81 Povezava na celotno besedilo 