Iskanje po katalogu digitalne knjižnice

Opis: V doktorski disertaciji obravnavamo spreminjanje stanja vozlišč grafa po pravilu procesa, imenovanega $r$-ojačano pronicanje. Bolj podrobno se lotimo preučevanja tega procesa na standardnih grafovskih produktih in vpeljemo nov pojem, imenovan razširjanje, ki sestoji iz kombinacije pravil ojačanega pronicanja ter ničelne prisile oziroma $k$-prisile. Po uvodnih poglavjih je disertacija razdeljena na pet delov, znotraj katerih predstavimo rezultate na omenjeno temo. V prvem delu obravnavamo proces pronicanja na kartezičnih mrežah, ki so kartezični produkti poti. Natančneje, določimo $3$-ojačitveno število pronicanja za kartezične mreže velikosti $3 \times n$ in $5 \times n$, kjer je $n$ poljubno naravno število. Dodatno omejimo vrednost $3$-ojačitvenega števila za kartezično mrežo velikosti $4\times n$ na dve možni vrednosti. V drugem delu disertacije se usmerimo v preučevanje pronicanja na krepkih produktih grafov, in sicer za poljubno število faktorjev. Določimo vrednosti za prag $r$, pri katerih $r$-ojačitveno število produkta $k$ grafov zasede svojo trivialno spodnjo mejo, ki je enaka $r$. Nadalje postavimo dodatne pogoje za faktorje krepkega produkta, pri katerih ohranimo enako lastnost $r$-ojačitvenega števila za višji prag $r$. Posebej se lotimo tudi najmanjšega primera, ki ni zajet v teh rezultatih, to je produkt dveh faktorjev in prag $r=3$, kjer karakteriziramo tiste krepke produkte, katerih $3$-ojačitveno število je enako $3$. Raziskavo razširimo na neskončne grafe, kjer opazujemo obnašanje $r$-ojačitvenega števila na krepkih produktih dvosmernih neskončnih poti. V tretjem delu se lotimo še zadnjega izmed treh standardnih komutativnih grafovskih produktov, to je direktnega produkta grafov. Določimo nekaj zgornjih mej za $r$-ojačitveno število direktnega produkta dveh grafov in karakteriziramo grafe, ki dosežejo dve zgornji meji v primeru praga $r=2$. Določimo tudi natančne vrednosti za $r$-ojačitveno število produkta dveh poti poljubnih dolžin in med drugim okarakteriziramo tiste direktne produkte grafov, katerih $2$-ojačitveno število je enako redu enega izmed faktorjev. Četrti in zadnji del doktorske disertacije posvetimo vpeljavi in preučevanju pojma razširjanje. Posplošimo do sedaj znane rezultate iz procesov pronicanja in $k$-prisile ter zapolnimo nekatere vrzeli pri rezultatih o kartezičnih mrežah in dokažemo, da je problem razširjanja NP-težek. Z vidika razširjanja dodatno preučujemo kubične grafe brez krempljev, kjer določimo bodisi natančne vrednosti, bodisi meje za vse variante razširjevalnega števila, in drevesa, kjer predstavimo algoritem za iskanje najmanjše širitvene množice poljubnega drevesa.
Ključne besede: ojačano pronicanje, ojačitveno število pronicanja, razširjanje, kartezični produkt, direktni produkt, krepki produkt, mreža, kubični graf, drevo.
Objavljeno v DKUM: 06.10.2025; Ogledov: 0; Prenosov: 16
Celotno besedilo (581,56 KB)

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: 9
Celotno besedilo (98,49 KB)
Gradivo ima več datotek! Več...

Opis: We propose a new coloring game on a graph, called the independence coloring game, which is played by two players with opposite goals. The result of the game is a proper coloring of vertices of a graph G, and Alice’s goal is that as few colors as possible are used during the game, while Bob wants to maximize the number of colors. The game consists of rounds, and in round i, where i = 1, 2,, … , the players are taking turns in selecting a previously unselected vertex of G and giving it color i (hence, in each round the selected vertices form an independent set). The game ends when all vertices of G are selected (and thus colored), and the total number of rounds during the game when both players are playing optimally with respect to their goals, is called the independence game chromatic number, χig(G), of G. In fact, four different versions of the independence game chromatic number are considered, which depend on who starts a game and who starts next rounds. We prove that the new invariants lie between the chromatic number of a graph and the maximum degree plus 1, and characterize the graphs in which each of the four versions of the game invariant equals 2. We compare the versions of the independence game chromatic number among themselves and with the classical game chromatic number. In addition, we prove that the independence game chromatic number of a tree can be arbitrarily large.
Ključne besede: graph, coloring, coloring game, competition-independence game, game chromatic number, tree
Objavljeno v DKUM: 09.08.2024; Ogledov: 99; Prenosov: 10
Celotno besedilo (852,33 KB)
Gradivo ima več datotek! Več...

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: 11
Povezava na celotno besedilo

Opis: Mavrično dominacijo na grafu $G$, z (neprazno) množico vozlišč in povezav ter množico s $k$ barvami, opišemo kot funkcijo $f$, ki vsako vozlišče označi s poljubno podmnožico barv tako, da imajo vsa tista vozlišča, ki jim je prirejena prazna množica, v svoji soseščini vseh $k$ barv. Funkciji $f$ tedaj pravimo $k$-mavrična dominantna funkcija grafa $G$. Vsota moči vseh oznak na vozliščih je vrednost $k$-mavrično dominantne funkcije. Najmanjša vrednost izmed vseh takih funkcij na grafu $G$ se imenuje $k$-mavrično dominantno število grafa $G$. V magistrskem delu podamo nekaj točnih vrednosti in zgornjih mej za $k$-mavrična dominantna števila. Večji poudarek damo na meje za 2- in 3-mavrično dominantna števila. Dokažemo dve splošni zgornji meji 2-mavrično dominantnega števila ter opišemo meje za 3-mavrično dominantna števila. Na koncu dela sledijo meje za $k$-mavrično dominantna števila, za katera je $k > 3$. V nekaterih primerih opišemo družine grafov, ki dosežejo enakost meje in jih dokažemo.
Ključne besede: graf, dominantno število, mavrična dominantna funkcija, mavrično dominantno število
Objavljeno v DKUM: 02.02.2023; Ogledov: 766; Prenosov: 59
Celotno besedilo (3,91 MB)