| | 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 / 47
First pagePrevious page12345Next pageLast page
1.
(d, n)-pakirno barvanje za posplošene grafe Sierpińskega
Anže Jeromel, 2019, master's thesis

Abstract: V magistrski nalogi so opisani grafi Sierpińskega in njihove posplošitve, (d, n)-pakirno barvanje grafov ter računsko iskanje (d, n)-pakirnih kromatičnih števil. Razvili smo algoritem za generiranje grafov Sierpińskega z osnovo 4 ter implementirali štiri metode barvanja grafov. Našli smo točna (d, n)-pakirna kromatična števila za različne kombinacije (d, n) pri grafih stopnje 2, pri grafih višjih stopenj pa njihove zgornje meje. Prav tako smo našli točna (1, 1)-pakirna kromatična števila dveh izbranih posplošenih grafov Sierpińskega do vključno stopnje 5.
Keywords: Sierpiński, pakirno barvanje, pakirno kromatično število
Published: 04.06.2019; Views: 529; Downloads: 51
.pdf Full text (4,27 MB)

2.
Linear recognition of generalized Fibonacci cubes $Q_h (111)$
Yoomi Rho, Aleksander Vesel, 2016, original scientific article

Abstract: The generalized Fibonacci cube $Q_h(f)$ is the graph obtained from the $h$-cube $Q_h$ by removing all vertices that contain a given binary string $f$ as a substring. In particular, the vertex set of the 3rd order generalized Fibonacci cube $Q_h(111)$ is the set of all binary strings $b_1b_2 ... b_h$ containing no three consecutive 1’s. We present a new characterization of the 3rd order generalized Fibonacci cubes based on their recursive structure. The characterization is the basis for an algorithm which recognizes these graphs in linear time.
Keywords: graph theory, Fibonacci cubes, recognition algorithm
Published: 10.07.2017; Views: 553; Downloads: 83
.pdf Full text (803,81 KB)
This document has many files! More...

3.
L(2,1)-labeling of the strong product of paths and cycles
Zehui Shao, Aleksander Vesel, 2014, original scientific article

Abstract: An L(2,1)-labeling of a graph G = (V, E) is a function f from the vertex set V(G) to the set of nonnegative integers such that the labels on adjacent vertices differ by at least two and the labels on vertices at distance two differ by at least one. The span of f is the difference between the largest and the smallest numbers in f(V). The ƛ-number of G, denoted by ƛ(G), is the minimum span over all L(2,1)-labelings of G. We consider the ƛ-number of Pn ☒ Cm and for n ≤ 11 the ƛ-number of Cn ☒ Cm. We determine ƛ-numbers of graphs of interest with the exception of a finite number of graphs and we improve the bounds on the ƛ-number of Cn ☒ Cm, m ≥ 24 and n ≥ 26.
Keywords: mathematics, graph theory
Published: 15.06.2017; Views: 585; Downloads: 266
.pdf Full text (2,31 MB)
This document has many files! More...

4.
1-factors and characterization of reducible faces of plane elementary bipartite graphs
Andrej Taranenko, Aleksander Vesel, 2012, original scientific article

Abstract: As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekulé structures (1-factors). A bipartite graph ▫$G$▫ is called elementary if ▫$G$▫ is connected and every edge belongs to a 1-factor of ▫$G$▫. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given. A peripheral face ▫$f$▫ of a plane elementary graph is reducible, if the removal of the internal vertices and edges of the path that is the intersection of ▫$f$▫ and the outer cycle of ▫$G$▫ results in an elementary graph. We characterize the reducible faces of a plane elementary bipartite graph. This result generalizes the characterization of reducible faces of an elementary benzenoid graph.
Keywords: mathematics, graph theory, plane elementary bipartite graph, reducible face, benzenoid graph
Published: 31.03.2017; Views: 545; Downloads: 294
.pdf Full text (139,73 KB)
This document has many files! More...

5.
Fibonaccijeva dimenzija resonančnih grafov katakondenziranih benzenoidnih grafov
Janja Rebernik, 2016, master's thesis

Abstract: Tema magistrskega dela je Fibonaccijeva dimenzija resonančnih grafov katakondenziranih benzenoidnih grafov. V delu predstavimo katakondenzirane benzenoidne grafe in problem določitve Fibonaccijeve dimenzije grafa, pri tem namenimo posebno pozornost določitvi Fibonaccijeve dimenzije resonančnih grafov katakondenziranih benzenoidnih grafov, za katere je opisan in implementiran tudi algoritem, ki izračuna Fibonaccijevo dimenzijo. V sklopu magistrskega dela je predstavljen in implementiran tudi algoritem, ki določi kanonično vložitev resonančnega grafa katakondenziranega benzenoidnega grafa v hiperkocko. Delo je razdeljeno na pet delov. V prvem delu so opisani osnovni pojmi in definicije. V drugem delu so predstavljeni katakondenzirani benzenoidni grafi in algoritem, ki določi kanonično vložitev resonančnega grafa katakondenziranega benzenoidnega grafa v hiperkocko. V tretjem delu je predstavljen problem določitve Fibonaccijeve dimenzije grafa. V četrtem delu pa ta problem omejimo na katakondenzirane benzenoidne grafe ter predstavimo algoritem za izračun Fibonaccijeve dimenzije resonančnih grafov katakondenziranih benzenoidnih grafov, ki ima linearno časovno zahtevnost. V petem delu opišemo implementacijo omenjenih algoritmov v programskem jeziku C++ in na primeru pokažemo delovanje programa.
Keywords: benzenoidni graf, katakondenzirani benzenoidni graf, Fibonaccijeva dimenzija, 1-faktor, resonančni graf
Published: 12.05.2016; Views: 627; Downloads: 98
.pdf Full text (1,32 MB)

6.
Hibridni algoritmi za barvanje grafov
Martin Duh, 2016, master's thesis

Abstract: Tema magistrskega dela je barvanje grafov s pomoˇcjo hibridnih algoritmov. V magistrskem delu predstavimo algoritem za barvanje grafa z variabilnim lokalnim iskanjem in hibridni algoritem za barvanje grafa, ki združuje evolucijski algoritem z lokalnim iskanjem. Nazadnje še predstavimo hibridni algoritem za barvanje grafa, ki deluje po principu algoritma za variabilno lokalno iskanje. Magistrsko delo je razdeljeno v osem sklopov. V prvem sklopu so navedeni osnovni pojmi in definicije. V drugem sklopu sledi pregled hevristiˇcnih metod za barvanje grafa. V tretjem sklopu je opisan standardni algoritem za variabilno lokalno iskanje. V ˇcetrtem sklopu je predstavljen prilagojen algoritem za variabilno lokalno iskanje za optimizacijski problem barvanja grafa. V petem sklopu so predstavljeni evolucijski algoritmi. V šestem sklopu so predstavljeni splošni hibridni algoritmi za barvanje grafa. Sklop zakljuˇcimo s hibridnim algoritmom za barvanje grafa, ki deluje po principu algoritma za variabilno lokalno iskanje. V sedmem sklopu je opis programa v programskem jeziku C++. V zadnjem sklopu so predstavljeni rezultati algoritmov za reševanje problema barvanja grafa na nekaterih izbranih primerih.
Keywords: algoritmi, grafi, barvanje grafa, lokalno iskanje, variabilno lokalno iskanje, evolucijski algoritmi, hibridni algoritmi
Published: 15.02.2016; Views: 1015; Downloads: 95
.pdf Full text (715,10 KB)

7.
8.
A note on the chromatic number of the square of the Cartesian product of two cycles
Zehui Shao, Aleksander Vesel, 2013, short scientific article

Abstract: The square ▫$G^2$▫ of a graph ▫$G$▫ is obtained from ▫$G$▫ by adding edges joining all pairs of nodes at distance 2 in ▫$G$▫. In this note we prove that ▫$chi((C_mBox C_n)^2) le 6$ for $m, n ge 40$▫. This confirms Conjecture 19 stated in [É. Sopena, J. Wu, Coloring the square of the Cartesian product of two cycles, Discrete Math. 310 (2010) 2327-2333].
Keywords: matematika, teorija grafov, kromatično število, kartezični produkt, označevanje grafov, kvadrat grafa, mathematics, graph theory, chromatic number, Cartesian product, graph labeling, square if a graph
Published: 10.07.2015; Views: 724; Downloads: 66
URL Link to full text

9.
Fibonacci dimension of the resonance graphs of catacondensed benzenoid graphs
Aleksander Vesel, 2013, original scientific article

Abstract: The Fibonacci dimension ▫$text{fdim}(G)$▫ of a graph ▫$G$▫ was introduced [in S. Cabello, D. Eppstein, S. Klavžar, The Fibonacci dimension of a graph Electron. J. Combin., 18 (2011) P 55, 23 pp] as the smallest integer ▫$d$▫ such that ▫$G$▫ admits an isometric embedding into ▫$Gamma_d$▫, the ▫$d$▫-dimensional Fibonacci cube. The Fibonacci dimension of the resonance graphs of catacondensed benzenoid systems is studied. This study is inspired by the fact, that the Fibonacci cubes are precisely the resonance graphs of a subclass of the catacondensed benzenoid systems. Our results show that the Fibonacci dimension of the resonance graph of a catacondensed benzenoid system ▫$G$▫ depends on the inner dual of ▫$G$▫. Moreover, we show that computing the Fibonacci dimension can be done in linear time for a graph of this class.
Keywords: Fibonaccijeva dimenzija, benzenoidni sistemi, resonančni grafi, algoritem, Fibonacci dimension, benzenoid systems, resonance graphs, algorithm
Published: 10.07.2015; Views: 616; Downloads: 68
URL Link to full text

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