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: 7
Celotno besedilo (98,49 KB)
Gradivo ima več datotek! Več... |
3. Strong edge geodetic problem in networksPaul Manuel, Sandi Klavžar, Antony Xavier, Andrew Arokiaraj, Elizabeth Thomas, 2017, izvirni znanstveni članek Opis: Geodesic covering problems form a widely researched topic in graph theory. One such problem is geodetic problem introduced by Harary et al. Here we introduce a variation of the geodetic problem and call it strong edge geodetic problem. We illustrate how this problem is evolved from social transport networks. It is shown that the strong edge geodetic problem is NP-complete. We derive lower and upper bounds for the strong edge geodetic number and demonstrate that these bounds are sharp. We produce exact solutions for trees, block graphs, silicate networks and glued binary trees without randomization.
Ključne besede: geodetic problem, strong edge geodetic problem, computational complexity, transport networks
Objavljeno v DKUM: 03.11.2017; Ogledov: 1194; Prenosov: 452
Celotno besedilo (657,86 KB)
Gradivo ima več datotek! Več... |
4. On the packing chromatic number of Cartesian products, hexagonal lattice, and treesBoštjan Brešar, Sandi Klavžar, Douglas F. Rall, 2007, izvirni znanstveni članek Opis: Pakirno kromatično število ▫$chi_{rho}(G)$▫ grafa ▫$G$▫ je najmanjše število ▫$k$▫, tako da lahko množico vozlišč grafa ▫$G$▫ razbijemo v pakiranja s paroma različnimi širinami. Dobljenih je več spodnjih in zgornjih meja za pakirno kromatično število kartezičnega produkta grafov. Dokazano je, da pakirno kromatično število šestkotniške mreže leži med 6 in 8. Optimalne spodnje in zgornje meje so dokazane za subdividirane grafe. Obravnavana so tudi drevesa ter vpeljana monotona barvanja.
Ključne besede: matematika, teorija grafov, pakirno kromatično število, kartezični produkt grafov, šestkotniška mreža, subdividiran graf, drevo, računska zahtevnost, mathematics, graph theory, packing chromatic number, Cartesian product of graphs, hexagonal lattice, subdivision graph, tree, computational complexity
Objavljeno v DKUM: 10.07.2015; Ogledov: 1320; Prenosov: 158
 Povezava na celotno besedilo |
5. Encyclopedia of complexity and systems scienceslovar, enciklopedija, leksikon, priročnik, atlas, zemljevid Opis: Encyclopedia of Complexity and Systems Science provides an authoritative single source for understanding and applying the concepts of complexity theory together with the tools and measures for analyzing complex systems in all fields of science and engineering. The science and tools of complexity and systems science include theories of self-organization, complex systems, synergetics, dynamical systems, turbulence, catastrophes, instabilities, nonlinearity, stochastic processes, chaos, neural networks, cellular automata, adaptive systems, and genetic algorithms. Examples of near-term problems and major unknowns that can be approached through complexity and systems science include: The structure, history and future of the universe; the biological basis of consciousness; the integration of genomics, proteomics and bioinformatics as systems biology; human longevity limits; the limits of computing; sustainability of life on earth; predictability, dynamics and extent of earthquakes, hurricanes, tsunamis, and other natural disasters; the dynamics of turbulent flows; lasers or fluids in physics, microprocessor design; macromolecular assembly in chemistry and biophysics; brain functions in cognitive neuroscience; climate change; ecosystem management; traffic management; and business cycles. All these seemingly quite different kinds of structure formation have a number of important features and underlying structures in common. These deep structural similarities can be exploited to transfer analytical methods and understanding from one field to another. This unique work will extend the influence of complexity and system science to a much wider audience than has been possible to date.
Ključne besede: cellular automata, complex networks, computational nanoscience, ecological complexity, ergodic theory, fractals, game theory, granular computing, graph theory, intelligent systems, perturbation theory, quantum information science, system dynamics, traffic management, chaos, climate modelling, complex systems, dynamical sistems, fuzzy theory systems, nonlinear systems, soft computing, stochastic processes, synergetics, self-organization, systems biology, systems science
Objavljeno v DKUM: 01.06.2012; Ogledov: 2813; Prenosov: 148
Povezava na celotno besedilo |
