1. Maker-Breaker domination game critical graphsAthira Divakaran, Tanja Dravec, Tijo James, Sandi Klavžar, Latha S. Nair, 2025, original scientific article Abstract: The Maker-Breaker domination game (MBD game) is a two-player game played on a graph ▫$G$▫ by Dominator and Staller. They alternately select unplayed vertices of ▫$G$▫. The goal of Dominator is to form a dominating set with the set of vertices selected by him while that of Staller is to prevent this from happening. In this paper MBD game critical graphs are studied. Their existence is established and critical graphs are characterized for most of the cases in which the first player can win the game in one or two moves.
Keywords: Maker-Breaker game, Maker-Breaker domination game, Maker-Breaker domination number, Maker-Breaker domination game critical graph
Published in DKUM: 25.07.2025; Views: 0; Downloads: 1
 Full text (540,67 KB)
This document has many files! More... |
2. Strong geodetic problem in networksPaul Manuel, Sandi Klavžar, Antony Xavier, Andrew Arokiaraj, Elizabeth Thomas, 2020, original scientific article Abstract: In order to model certain social network problems, the strong geodetic problem and its related invariant, the strong geodetic number, are introduced. The problem is conceptually similar to the classical geodetic problem but seems intrinsically more difficult. The strong geodetic number is compared with the geodetic number and with the isometric path number. It is determined for several families of graphs including Apollonian networks. Applying Sierpiński graphs, an algorithm is developed that returns a minimum path cover of Apollonian networks corresponding to the strong geodetic number. It is also proved that the strong geodetic problem is NP-complete.
Keywords: geodetic problem, strong geodetic problem, Apollonian networks, Sierpiński graphs, computational complexity
Published in DKUM: 11.03.2025; Views: 0; Downloads: 4
Full text (162,66 KB)
This document has many files! More... |
3. A survey on packing coloringsBoštjan Brešar, Jasmina Ferme, Sandi Klavžar, Douglas F. Rall, 2020, review article Abstract: If S=(a1,a2,...) is a non-decreasing sequence of positive integers, then an S-packing coloring of a graph G is a partition of V (G) into sets X1,X2,... such that for each pair of distinct vertices in the set Xi, the distance between them is larger than ai. If there exists an integer k such that V(G)=X1 U ... U Xk, then the partition is called an S-packing k-coloring. The S-packing chromatic number of G is the smallest k such that G admits an S-packing k-coloring. If ai=i for every i, then the terminology reduces to packing colorings and packing chromatic number. Since the introduction of these generalizations of the chromatic number in 2008 more than fifty papers followed. Here we survey the state of the art on the packing coloring, and ts generalization, the S-packing coloring. We also list several conjecres and open problems.
Keywords: packing coloring, packing chromatic number, subcubic graph, S-packing chromatic number, computational complexity
Published in DKUM: 11.03.2025; Views: 0; Downloads: 9
Full text (98,49 KB)
This document has many files! More... |
4. Trees with distinguishing index equal distinguishing number plus oneSaeid Alikhani, Sandi Klavžar, Florian Lehner, Samaneh Soltani, 2020, original scientific article Abstract: The distinguishing number (index) D(G) (D'(G)) of a graph G is the least integer d such that G has an vertex (edge) labeling with d labels that is preserved only by the trivial automorphism. It is known that for every graph G we have D'(G) \leq D(G) + 1. In this note we characterize finite trees for which this inequality is sharp. We also show that if G is a connected unicyclic graph, then D'(G) = D(G).
Keywords: automorphism group, distinguishing index, distinguishing number, tree, unicyclic graph
Published in DKUM: 11.03.2025; Views: 0; Downloads: 22
Full text (144,96 KB)
This document has many files! More... |
5. 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... |
6. 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... |
7. On Grundy total domination number in product graphsBoštjan Brešar, Csilla Bujtás, Tanja Dravec, Sandi Klavžar, Gašper Košmrlj, Tilen Marc, Balázs Patkós, Zsolt Tuza, Máté Vizer, 2021, original scientific article Abstract: A longest sequence (v1,....,vk) of vertices of a graph G is a Grundy total dominating sequence of G if for all i, N(vi)\U{j=1}^{i-1} N(vj)≠∅. The length k of the sequence is called the Grundy total domination number of G and denoted ɣ{gr}^{t}(G). In this paper, the Grundy total domination number is studied on four standard graph products. For the direct product we show that ɣ{gr}^{t}(G x H) > ɣ{gr}^{t}(G)ɣ{gr}^{t}(H), conjecture that the equality always holds, and prove the conjecture in several special cases. For the lexicographic product we express ɣ{gr}^{t}(G o H) in terms of related invariant of the factors and find some explicit formulas for it. For the strong product, lower bounds on ɣ{gr}^{t}(G ⊠ H) are proved as well as upper bounds for products of paths and cycles. For the Cartesian product we prove lower and upper bounds on the Grundy total domination number when factors are paths or cycles.
Keywords: total domination, Grundy total domination number, graph product
Published in DKUM: 07.08.2024; Views: 96; Downloads: 11
Full text (248,02 KB)
This document has many files! More... |
8. The cut method on hypergraphs for the Wiener indexSandi Klavžar, Gašper Domen Romih, 2023, original scientific article Abstract: The cut method has been proved to be extremely useful in chemical graph theory. In this paper the cut method is extended to hypergraphs. More precisely, the method is developed for the Wiener index of ▫$k$▫-uniform partial cube-hypergraphs. The method is applied to cube-hypergraphs and hypertrees. Extensions of the method to hypergraphs arising in chemistry which are not necessary ▫$k$▫-uniform and/or not necessary linear are also developed.
Keywords: hypergraphs, Wiener index, cut method, partial cube-hypergraphs, hypertrees, phenylene, Clar structures
Published in DKUM: 11.04.2024; Views: 230; Downloads: 10
Full text (318,42 KB)
This document has many files! More... |
9. Packings in bipartite prisms and hypercubesBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2024, original scientific article Abstract: ▫$2$▫-pakirno število ▫$\rho_2(G)$▫ grafa ▫$G$▫ je kardinalnost največjega ▫$2$▫-pakiranja grafa ▫$G$▫, odprto pakirno število ▫$\rho^{\rm o}(G)$▫ pa kardinalnost največjega odprtega pakiranja grafa ▫$G$▫, kjer je odprto pakiranje (oz. ▫$2$▫ pakiranje) množica vozlišč grafa ▫$G$▫, katerih dve (zaprti) soseščini se ne sekata. Dokazano je, da če je ▫$G$▫ dvodelen, potem je ▫$\rho^{\rm o}(G\Box K_2) = 2\rho_2(G)$▫. Za hiperkocke sta določeni spodnji meji ▫$\rho_2(Q_n) \ge 2^{n - \lfloor \log n\rfloor -1}$▫ in ▫$\rho^{\rm o}(Q_n) \ge 2^{n - \lfloor \log (n-1)\rfloor -1}$▫. Te ugotovitve so uporabljene za injektivna barvanja hiperkock. Dokazano je, da je ▫$Q_9$▫ najmanjša hiperkocka, ki ni popolno injektivno obarvljiva. Dokazano je tudi, da je ▫$\gamma_t(Q_{2^k}\times H) = 2^{2^k-k}\gamma_t(H)$▫, kjer je ▫$H$▫ poljuben graf brez izoliranih vozlišč.
Keywords: 2-pakirno število, odprto pakirno število, dvodelna prizma, hiperkocke, injektivno barvanje, celotno dominacijsko število, 2-packing number, open packing number, bipartite prism, hypercube, injective coloring, total domination number
Published in DKUM: 28.02.2024; Views: 260; Downloads: 11
 Link to full text |
10. |
