1. Strong geodetic problem in networksPaul Manuel, Sandi Klavžar, Antony Xavier, Andrew Arokiaraj, Elizabeth Thomas, 2020, izvirni znanstveni članek Opis: 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. Ključne besede: geodetic problem, strong geodetic problem, Apollonian networks, Sierpiński graphs, computational complexity Objavljeno v DKUM: 11.03.2025; Ogledov: 0; Prenosov: 4
Celotno besedilo (162,66 KB) Gradivo ima več datotek! Več... |
2. A survey on packing coloringsBoštjan Brešar, Jasmina Ferme, Sandi Klavžar, Douglas F. Rall, 2020, pregledni znanstveni članek Opis: 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. Ključne besede: packing coloring, packing chromatic number, subcubic graph, S-packing chromatic number, computational complexity Objavljeno v DKUM: 11.03.2025; Ogledov: 0; Prenosov: 5
Celotno besedilo (98,49 KB) Gradivo ima več datotek! Več... |
3. Trees with distinguishing index equal distinguishing number plus oneSaeid Alikhani, Sandi Klavžar, Florian Lehner, Samaneh Soltani, 2020, izvirni znanstveni članek Opis: 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). Ključne besede: automorphism group, distinguishing index, distinguishing number, tree, unicyclic graph Objavljeno v DKUM: 11.03.2025; Ogledov: 0; Prenosov: 4
Celotno besedilo (144,96 KB) Gradivo ima več datotek! Več... |
4. 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: 2
Celotno besedilo (365,63 KB) Gradivo ima več datotek! Več... |
5. 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č... |
6. 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, izvirni znanstveni članek Opis: 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. Ključne besede: total domination, Grundy total domination number, graph product Objavljeno v DKUM: 07.08.2024; Ogledov: 96; Prenosov: 11
Celotno besedilo (248,02 KB) Gradivo ima več datotek! Več... |
7. The cut method on hypergraphs for the Wiener indexSandi Klavžar, Gašper Domen Romih, 2023, izvirni znanstveni članek Opis: 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. Ključne besede: hypergraphs, Wiener index, cut method, partial cube-hypergraphs, hypertrees, phenylene, Clar structures Objavljeno v DKUM: 11.04.2024; Ogledov: 230; Prenosov: 10
Celotno besedilo (318,42 KB) Gradivo ima več datotek! Več... |
8. Packings in bipartite prisms and hypercubesBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2024, izvirni znanstveni članek Opis: ▫$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šč. Ključne besede: 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 Objavljeno v DKUM: 28.02.2024; Ogledov: 260; Prenosov: 9
Povezava na celotno besedilo |
9. |
10. Szeged-like topological indices and the efficacy of the cut method: the case of melem structuresMicheal Arockiaraj, Shagufa Mushtaq, Sandi Klavžar, J. Celin Fiona, Krishnan Balasubramanian, 2022, izvirni znanstveni članek Opis: The Szeged index is a bond-additive topological descriptor that quantifies each bond's terminal atoms based on their closeness sets which is measured by multiplying the number of atoms in the closeness sets. Based on the high correlation between the Szeged index and the physico-chemical properties of chemical compounds, Szeged-like indices have been proposed by considering closeness sets with bond counts and other mathematical operations like addition and subtraction. As there are many ways to compute the Szeged-like indices, the cut method is predominantly used due to its complexity compared to other approaches based on algorithms and interpolations. Yet, we here analyze the usefulness of the cut method in the case of melem structures and find that it is less effective when the size and shape of the cavities change in the structures. Ključne besede: distance, Szeged index, cut-method Objavljeno v DKUM: 11.08.2023; Ogledov: 425; Prenosov: 46
Celotno besedilo (551,00 KB) Gradivo ima več datotek! Več... |