1. General Position Sets in Two Families of Cartesian Product GraphsDanilo Korže, Aleksander Vesel, 2023, izvirni znanstveni članek Opis: For a given graph G, the general position problem asks for the largest set of vertices S⊆V(G) , such that no three distinct vertices of S belong to a common shortest path of G. The general position problem for Cartesian products of two cycles as well as for hypercubes is considered. The problem is completely solved for the first family of graphs, while for the hypercubes, some partial results based on reduction to SAT are given. Ključne besede: general position set, cartesian product, hypercube, SAT Objavljeno v DKUM: 02.04.2024; Ogledov: 183; Prenosov: 20 Celotno besedilo (405,17 KB) Gradivo ima več datotek! Več... |
2. A new alternative to Szeged, Mostar, and PI polynomials : the SMP polynomialsMartin Knor, Niko Tratnik, 2023, izvirni znanstveni članek Opis: Szeged-like topological indices are well-studied distance-based molecular descriptors, which include, for example, the (edge-)Szeged index, the (edge-)Mostar index, and the (vertex-)PI index. For these indices, the corresponding polynomials were also defined, i.e., the (edge-)Szeged polynomial, the Mostar polynomial, the PI polynomial, etc. It is well known that, by evaluating the first derivative of such a polynomial at x = 1, we obtain the related topological index. The aim of this paper is to introduce and investigate a new graph polynomial of two variables, which is called the SMP polynomial, such that all three vertex versions of the above-mentioned indices can be easily calculated using this polynomial. Moreover, we also define the edge-SMP polynomial, which is the edge version of the SMP polynomial. Various properties of the new polynomials are studied on some basic families of graphs, extremal problems are considered, and several open problems are stated. Then, we focus on the Cartesian product, and we show how the (edge-)SMP polynomial of the Cartesian product of n graphs can be calculated using the (weighted) SMP polynomials of its factors. Ključne besede: SMP polynomial, edge-SMP polynomial, Cartesian product, Szeged index, Mostar index, PI index Objavljeno v DKUM: 09.02.2024; Ogledov: 203; Prenosov: 15 Celotno besedilo (320,27 KB) Gradivo ima več datotek! Več... |
3. |
4. 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, izvirni znanstveni članek Opis: 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. Ključne besede: domination number, Cartesian product, directed cycle Objavljeno v DKUM: 02.09.2022; Ogledov: 533; Prenosov: 10 Povezava na celotno besedilo |
5. 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: 1494; Prenosov: 39 Celotno besedilo (764,69 KB) Gradivo ima več datotek! Več... |
6. 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 v DKUM: 23.08.2017; Ogledov: 1564; Prenosov: 237 Celotno besedilo (719,06 KB) Gradivo ima več datotek! Več... |
7. 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 5-cycle or a 4-cycle. Ključne besede: efficient open domination, Cartesian product, vertex labeling, total domination Objavljeno v DKUM: 10.07.2017; Ogledov: 1022; Prenosov: 158 Celotno besedilo (166,60 KB) Gradivo ima več datotek! Več... |
8. 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: 1285; Prenosov: 450 Celotno besedilo (56,60 KB) Gradivo ima več datotek! Več... |
9. 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: 1476; Prenosov: 404 Celotno besedilo (197,33 KB) Gradivo ima več datotek! Več... |
10. 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. Path-like median graphs are introduced as the graphs whose periphery graph has independence number 2, and it is proved that there are path-like 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 v DKUM: 31.03.2017; Ogledov: 1427; Prenosov: 404 Celotno besedilo (145,86 KB) Gradivo ima več datotek! Več... |