1. An asymptotic relation between the wirelength of an embedding and the Wiener indexK. Jagadeesh Kumar, Sandi Klavžar, R. Sundara Rajan, Indra Rajasingh, T. M. Rajalaxmi, 2021, izvirni znanstveni članek Opis: Wirelength is an important criterion to validate the quality of an embedding of a graph into a host graph and is used in particular in VLSI (Very-Large-Scale Integration) layout designs. Wiener index plays a significant role in mathematical chemistry, cheminformatics, and elsewhere. In this note these two concepts are related by proving that the Wiener index of a host graph is an upper bound for the wirelength of a given embedding. The wirelength of embedding complete ▫$2^p$▫-partite graphs into Cartesian products of paths and/or cycles as the function of the Wiener index is determined. The result is an asymptotic approximation of the general upper bound. Ključne besede: Wiener index, embedding, wirelength, complete 2p-partite graph, Cartesian product of graphs, integer labeling Objavljeno v DKUM: 23.09.2024; Ogledov: 0; Prenosov: 1 Celotno besedilo (365,63 KB) Gradivo ima več datotek! Več... |
2. On general position sets in Cartesian productsSandi Klavžar, Balázs Patkós, Gregor Rus, Ismael G. Yero, 2021, izvirni znanstveni članek Opis: The general position number gp(G) of a connected graph G is the cardinality of a largest set S of vertices such that no three distinct vertices from S lie on a common geodesic; such sets are refereed to as gp-sets of G. The general position number of cylinders Pr ◻ Cs is deduced. It is proved that (Cr ◻ Cs)∈{6,7} whenever r ≥ s ≥ 3, s ≠ 4, and r ≥ 6. A probabilistic lower bound on the general position number of Cartesian graph powers is achieved. Along the way a formula for the number of gp-sets in Pr ◻ Ps, where r,s ≥ 2, is also determined. Ključne besede: general position problem, Cartesian product of graphs, paths and cycles, probabilistic constructions, exact enumeration Objavljeno v DKUM: 27.08.2024; Ogledov: 39; Prenosov: 7 Celotno besedilo (586,20 KB) Gradivo ima več datotek! Več... |
3. 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č... |
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 non-trivial 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 vertex-transitive 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 v DKUM: 09.05.2017; Ogledov: 1348; Prenosov: 451 Celotno besedilo (56,60 KB) Gradivo ima več datotek! Več... |
5. Weak k-reconstruction 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 v DKUM: 31.03.2017; Ogledov: 1558; Prenosov: 432 Celotno besedilo (197,33 KB) Gradivo ima več datotek! Več... |
6. |
7. 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 Djokovic-Winkler relation. ▫$\Theta$▫-graphs that are 2-connected, 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 v DKUM: 31.03.2017; Ogledov: 1119; Prenosov: 144 Celotno besedilo (150,56 KB) Gradivo ima več datotek! Več... |
8. Edge-transitive lexicographic and cartesian productsWilfried Imrich, Ali Iranmanesh, Sandi Klavžar, Abolghasem Soltani, 2016, izvirni znanstveni članek Opis: In this note connected, edge-transitive 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 edge-transitive if and only if ▫$G$▫ is edge-transitive and ▫$H$▫ is edgeless. If the first factor of ▫$G \circ H$▫ is non-trivial and complete, then ▫$G \circ H$▫ is edge-transitive 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) 1924--1926). For the Cartesian product it is shown that every connected Cartesian product of at least two non-trivial factors is edge-transitive if and only if it is the Cartesian power of a connected, edge- and vertex-transitive graph. Ključne besede: edge-transitive graph, vertex-transitive graph, lexicographic product of graphs, Cartesian product of graphs Objavljeno v DKUM: 31.03.2017; Ogledov: 1072; Prenosov: 428 Celotno besedilo (150,33 KB) Gradivo ima več datotek! Več... |
9. Bucolic complexesBoštjan Brešar, Jérémie Chalopin, Victor Chepoi, Tanja Dravec, 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 2-skeletov in 1-skeletov (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 v DKUM: 10.07.2015; Ogledov: 1394; Prenosov: 26 Povezava na celotno besedilo |
10. Bucolic complexesBoštjan Brešar, Jérémie Chalopin, Victor Chepoi, Tanja Dravec, 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 graph-theoretic and topological viewpoints, as well as from the point of view of geometric group theory. Bucolic complexes can be defined as locally-finite simply connected prism complexes satisfying some local combinatorial conditions. We show that bucolic complexes are contractible, and satisfy some nonpositive-curvature-like properties. In particular, we prove a version of the Cartan-Hadamard theorem, the fixed point theorem for finite group actions, and establish some results on groups acting geometrically on such complexes. We also characterize the 1-skeletons (which we call bucolic graphs) and the 2-skeletons 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 1-skeletons 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 v DKUM: 10.07.2015; Ogledov: 1323; Prenosov: 29 Povezava na celotno besedilo |