| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font

Search the digital library catalog Help

Query: search in
search in
search in
search in
* old and bologna study programme

Options:
  Reset


1 - 10 / 109
First pagePrevious page12345678910Next pageLast page
1.
A survey on packing colorings
Boš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: 7
.pdf Full text (98,49 KB)
This document has many files! More...

2.
A new framework to approach Vizing's conjecture
Boštjan Brešar, Bert L. Hartnell, Michael A. Henning, Kirsti Kuenzel, Douglas F. Rall, 2021, original scientific article

Abstract: We introduce a new setting for dealing with the problem of the domination number of the Cartesian product of graphs related to Vizing's conjecture. The new framework unifies two different approaches to the conjecture. The most common approach restricts one of the factors of the product to some class of graphs and proves the inequality of the conjecture then holds when the other factor is any graph. The other approach utilizes the so-called Clark-Suen partition for proving a weaker inequality that holds for all pairs of graphs. We demonstrate the strength of our framework by improving the bound of Clark and Suen as follows: ɣ(X◻Y) ≥ max{1/2ɣ(X) ɣt(Y), 1/2ɣt(X) ɣ(Y)}, where ɣ stands for the domination number, ɣt is the total domination number, and X◻Y is the Cartesian product of graphs X and Y.
Keywords: Cartesian product, total domination, Vizing's conjecture, Clark and Suen bound
Published in DKUM: 09.08.2024; Views: 86; Downloads: 11
.pdf Full text (179,75 KB)
This document has many files! More...

3.
The independence coloring game on graphs
Boštjan Brešar, Daša Mesarič Štesl, 2022, original scientific article

Abstract: 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.
Keywords: graph, coloring, coloring game, competition-independence game, game chromatic number, tree
Published in DKUM: 09.08.2024; Views: 99; Downloads: 10
.pdf Full text (852,33 KB)
This document has many files! More...

4.
On Grundy total domination number in product graphs
Boš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
.pdf Full text (248,02 KB)
This document has many files! More...

5.
Packings in bipartite prisms and hypercubes
Boš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: 10
URL Link to full text

6.
Orientable domination in product-like graphs
Sarah Anderson, Boštjan Brešar, Sandi Klavžar, Kirsti Kuenzel, Douglas F. Rall, 2023, original scientific article

Abstract: The orientable domination number, ▫${\rm DOM}(G)$▫, of a graph ▫$G$▫ is the largest domination number over all orientations of ▫$G$▫. In this paper, ▫${\rm DOM}$▫ is studied on different product graphs and related graph operations. The orientable domination number of arbitrary corona products is determined, while sharp lower and upper bounds are proved for Cartesian and lexicographic products. A result of Chartrand et al. from 1996 is extended by establishing the values of ▫${\rm DOM}(K_{n_1,n_2,n_3})$▫ for arbitrary positive integers ▫$n_1,n_2$▫ and ▫$n_3$▫. While considering the orientable domination number of lexicographic product graphs, we answer in the negative a question concerning domination and packing numbers in acyclic digraphs posed in [Domination in digraphs and their direct and Cartesian products, J. Graph Theory 99 (2022) 359-377].
Keywords: digraph, domination, orientable domination number, packing, graph product, corona graph
Published in DKUM: 09.08.2023; Views: 446; Downloads: 54
.pdf Full text (419,38 KB)
This document has many files! More...

7.
Meje za mavrična dominantna števila : magistrsko delo
Klavdija Zelko, 2023, master's thesis

Abstract: 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.
Keywords: graf, dominantno število, mavrična dominantna funkcija, mavrično dominantno število
Published in DKUM: 02.02.2023; Views: 766; Downloads: 58
.pdf Full text (3,91 MB)

8.
Grafi, ki dosežejo enakost v vizingovi domnevi : magistrsko delo
Anamarija Lakner, 2022, master's thesis

Abstract: Vizing je leta 1968 postavil domnevo, da je dominantno število kartezičnega produkta dveh grafov večje ali enako produktu njunih dominantnih števil. V magistrskem delu obravnavamo družine grafov, ki v tej domnevi dosežejo enakost. V prvem delu magistrske naloge smo navedli pojme in trditve, ki jih potrebujemo za razumevanje glavnega problema naloge. Drugo poglavje se nanaša na različne meje dominantnega števila kartezičnega produkta dveh grafov in družine grafov, ki zadoščajo Vizingovi domnevi. V tretjem poglavju obravnavamo družine grafov, ki pod določenimi pogoji dosežejo enakost v Vizingovi domnevi, ter znane rezultate podamo v tabeli.
Keywords: dominantno število, dominantna množica, Vizingova domneva, enakost v Vizingovi domnevi
Published in DKUM: 28.10.2022; Views: 573; Downloads: 55
.pdf Full text (568,89 KB)

9.
Sodobne igre barvanj in sorodne igre na grafih
Daša Štesl, 2022, doctoral dissertation

Abstract: V doktorski disertaciji obravnavamo v zadnjih letih vpeljane variacije klasične igre barvanja in njim sorodne igre na grafih. Doktorsko delo sestoji iz štirih delov, znotraj katerih predstavimo nova spoznanja na omenjeno temo. V prvem delu disertacije obravnavamo indicirano igro barvanja kartezičnih produktov grafov. Natančneje, določimo indicirano igralno kromatično število kartezičnih produktov grafov, katerih indicirano kromatično število znaša 3, s polnim dvodelnim grafom. Dodatno obravnavamo indicirano kromatično število kartezičnih produktov bločnih grafov in dreves ter indicirano kromatično število kartezičnega produkta dveh ciklov. V drugem delu disertacije se posvetimo študiji štirih variacij neodvisnostne igre barvanja, ki so posebna oblika klasične igre barvanja, pri kateri igralca ne preideta na višjo raven, dokler ne izčrpata vseh možnosti za uporabo dane barve. Dobljene igralne invariante primerjamo med seboj in s klasičnim igralnim kromatičnim številom. Poleg tega ugotovimo, da neodvisnostno igralno kromatično število v razredu dreves ni omejeno. V tretjem delu preučujemo vozliščno kritične grafe glede na klasično igralno kromatično število, glede na indicirano kromatično število in glede na A-neodvisnostno ter AB-neodvisnostno igralno kromatično število. Med drugim obravnavamo vprašanje povezanosti grafov, ki so kritični glede na omenjene igralne grafovske invariante, obnašanje dane igralne invariante ob odstranitvi poljubnega vozlišča iz igralno vozliščno kritičnega grafa ter karakteriziramo igralno vozliščno kritične grafe, ki imajo majhno vrednost pripadajoče invariante. Zadnji del doktorske disertacije posvetimo neodvisni dominacijski igri s preprečevanjem. Določimo neodvisni dominantni števili s preprečevanjem za poti in cikle. Poleg tega postavimo meje za obe variaciji omenjene igre ter karakteriziramo (povezane) grafe, ki dosežejo dobljeni meji. Dodatno opozorimo na tesno povezavo med neodvisno dominacijsko igro s preprečevanjem in pakirno igro barvanja v grafih z diametrom 2.
Keywords: igra barvanja, indicirana igra barvanja, neodvisnostna igra barvanja, neodvisna dominacijska igra, pakirna igra barvanja, kartezični produkt, drevo, vozliščno kritičen graf
Published in DKUM: 25.10.2022; Views: 703; Downloads: 76
.pdf Full text (614,26 KB)

10.
1-perfectly orientable K[sub]4-minor-free and outerplanar graphs
Boštjan Brešar, Tatiana Romina Hartinger, Tim Kos, Martin Milanič, 2018, original scientific article

Abstract: A graph ▫$G$▫ is said to be 1-perfectly orientable if it has an orientation ▫$D$▫ such that for every vertex ▫$v \in V(G)$▫, the out-neighborhood of ▫$v$▫ in ▫$D$▫ is a clique in ▫$G$▫. D. J. Skrien [J. Graph Theory 6, 309--316 (1982)] posed the problem of characterizing the class of 1-perfectly orientable graphs. This graph class forms a common generalization of the classes of chordal and circular arc graphs; however, while polynomially recognizable via a reduction to 2-SAT, no structural characterization of this intriguing class of graphs is known. Based on a reduction of the study of 1-perfectly orientable graphs to the biconnected case, we characterize, both in terms of forbidden induced minors and in terms of composition theorems, the classes of 1-perfectly orientable ▫$K_4$▫-minor-free graphs and of 1-perfectly orientable outerplanar graphs. As part of our approach, we introduce a class of graphs defined similarly as the class of 2-trees and relate the classes of graphs under consideration to two other graph classes closed under induced minors studied in the literature: cyclically orientable graphs and graphs of separability at most 2.
Keywords: 1-perfectly orientable graph, ▫$K_4$▫-minor-free graph, outerplanar graph
Published in DKUM: 20.09.2022; Views: 488; Downloads: 16
URL Link to full text

Search done in 0.1 sec.
Back to top
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica