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, original scientific article Abstract: 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.
Keywords: Wiener index, embedding, wirelength, complete 2p-partite graph, Cartesian product of graphs, integer labeling
Published in DKUM: 23.09.2024; Views: 0; Downloads: 5
 Full text (365,63 KB)
This document has many files! More... |
2. On general position sets in Cartesian productsSandi Klavžar, Balázs Patkós, Gregor Rus, Ismael G. Yero, 2021, original scientific article Abstract: 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.
Keywords: general position problem, Cartesian product of graphs, paths and cycles, probabilistic constructions, exact enumeration
Published in DKUM: 27.08.2024; Views: 39; Downloads: 7
Full text (586,20 KB)
This document has many files! More... |
3. 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 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.
Keywords: 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
Published in DKUM: 23.10.2019; Views: 1549; Downloads: 54
Full text (764,69 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 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.
Keywords: domination game, game domination number, bluff graphs, minus graphs, generalized Petersen graphs, Kneser graphs, Cartesian product of graphs, Hamming graphs
Published in DKUM: 09.05.2017; Views: 1348; Downloads: 478
Full text (56,60 KB)
This document has many files! More... |
5. Weak k-reconstruction 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 in DKUM: 31.03.2017; Views: 1558; Downloads: 612
Full text (197,33 KB)
This document has many files! More... |
6. 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 non-existence 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 c-strong rainbow coloring is introduced. In particular it is proved that the so-called ▫$\Theta$▫-coloring of an isometric subgraph of a hypercube is its unique optimal c-strong rainbow coloring.
Keywords: graph theory, rainbow connection, strong rainbow connection, Cartesian product of graphs, isometric subgraph, hypercube
Published in DKUM: 31.03.2017; Views: 1207; Downloads: 434
Full text (125,60 KB)
This document has many files! More... |
7. 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 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.
Keywords: mathematics, graph theory, intersection graph, partial cube, median graph, expansion theorem, Cartesian product of graphs
Published in DKUM: 31.03.2017; Views: 1119; Downloads: 166
Full text (150,56 KB)
This document has many files! More... |
8. Edge-transitive lexicographic and cartesian productsWilfried Imrich, Ali Iranmanesh, Sandi Klavžar, Abolghasem Soltani, 2016, original scientific article Abstract: 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.
Keywords: edge-transitive graph, vertex-transitive graph, lexicographic product of graphs, Cartesian product of graphs
Published in DKUM: 31.03.2017; Views: 1072; Downloads: 451
Full text (150,33 KB)
This document has many files! More... |
9. The k-independence number of direct products of graphs and Hedetniemi's conjectureSimon Špacapan, 2011, original scientific article Abstract: 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$▫.
Keywords: matematika, teorija grafov, neodvisnostno število, kartezični produkt grafov, mathematics, graph theory, independence number, Cartesian product of graphs
Published in DKUM: 10.07.2015; Views: 1487; Downloads: 69
 Link to full text |
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 Abstract: 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 cage-amalgamation 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 1-skeletons of CAT(0) cubical complexes.
Keywords: 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
Published in DKUM: 10.07.2015; Views: 1199; Downloads: 112
Link to full text |
