1. Mutual-visibility sets in cartesian products of paths and cyclesDanilo Korže, Aleksander Vesel, 2024, izvirni znanstveni članek Opis: For a given graph G, the mutual-visibility problem asks for the largest set of vertices M ⊆ V (G) with the property that for any pair of vertices u, v ∈ M there exists a shortest u, v-path of G that does not pass through any other vertex in M. The mutual-visibility problem for Cartesian products of a cycle and a path, as well as for Cartesian products of two cycles, is considered. Optimal solutions are provided for the majority of Cartesian products of a cycle and a path, while for the other family of graphs, the problem is completely solved.
Ključne besede: mutual-visibility set, supermutual-visibility number, Cartesian product
Objavljeno v DKUM: 14.08.2024; Ogledov: 73; Prenosov: 3
 Celotno besedilo (596,74 KB) |
2. Binary coding of resonance graphs of catacondensed polyhexesAleksander Vesel, 2023, izvirni znanstveni članek Opis: A catacondensed polyhex H is a connected subgraph of a hexagonal system such that any edge of H lies in a hexagon of H, any triple of hexagons of H has an empty intersection and the inner dual of H is a cactus graph. A perfect matching M of a catacondensed polyhex H is relevant if every cycle of the inner dual of H admitsa vertex that corresponds to the hexagon which contributes three edges in M. The vertex set of the graph R˜(H) consists of all relevant perfect matchings of H, two perfect matchings being adjacent whenever their symmetric difference forms the edge set of a hexagon of H. A labeling that assigns in linear time a binary string to every relevant perfect matching of a catacondensed polyhex is presented. The introduced labeling defines an isometric embedding of R˜(H)
into a hypercube.
Ključne besede: graphs, graph theory, resonance graphs
Objavljeno v DKUM: 07.06.2024; Ogledov: 99; Prenosov: 6
Celotno besedilo (518,69 KB)
Gradivo ima več datotek! Več... |
3. General Position Sets in Two Families of Cartesian Product GraphsDanilo Korže, Aleksander Vesel, 2023, izvirni znanstveni članek Opis: For a given graph G, the general position problem asks for the largest set of vertices S⊆V(G) , such that no three distinct vertices of S belong to a common shortest path of G. The general position problem for Cartesian products of two cycles as well as for hypercubes is considered. The problem is completely solved for the first family of graphs, while for the hypercubes, some partial results based on reduction to SAT are given.
Ključne besede: general position set, cartesian product, hypercube, SAT
Objavljeno v DKUM: 02.04.2024; Ogledov: 256; Prenosov: 21
Celotno besedilo (405,17 KB)
Gradivo ima več datotek! Več... |
4. Barvanje povezav grafa z najmanjšim številom palet : na študijskem programu Izobraževalna matematika in izobraževalno računalništvoKarmen Bregač, 2023, magistrsko delo Opis: V magistrskem delu obravnavamo paletno barvanje povezav in paletni indeks različnih družin grafov. Dobro barvanje povezav je barvanje, pri katerem velja, da nobeni incidenčni povezavi nista pobarvani z enako barvo. Dobro barvanje povezav grafa za vsako vozlišče definira množico barv incidenčnih povezav. Takšno množico imenujemo paleta vozlišča. V literaturi se avtorji večinoma osredotočajo na barvanje povezav grafov, pri katerem je uporabljeno največje možno število palet. Mi se bomo osredotočili na iskanje takšnega barvanja povezav grafa, za katerega bo veljalo, da je barvanje dobro in pri katerem bo uporabljeno najmanjše možno število palet, ki ga imenujemo paletni indeks grafa.
Na začetku spoznamo osnove teorije grafov, ki nam pomagajo pri nadaljnjem razumevanju teorije. V osrednjem delu magistrske dela ugotovimo, da nas dobro barvanje z najmanjšim številom možnih barv ne pripelje vedno do najmanjšega števila palet. Spoznamo tudi, kako poiskati paletne indekse nekaterih znanih družin grafov in posebnih primerov grafov, pri katerih namesto minimalnega barvanja povezav uporabimo barvanje z večjim številom barv.
Ključne besede: Barvanje povezav, paletno barvanje povezav, paletni indeks.
Objavljeno v DKUM: 07.09.2023; Ogledov: 423; Prenosov: 24
Celotno besedilo (5,34 MB) |
5. (d, n)-pakirno barvanje za posplošene grafe Sierpińskega : magistrsko deloAnže Jeromel, 2019, magistrsko delo Opis: 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.
Ključne besede: Sierpiński, pakirno barvanje, pakirno kromatično število
Objavljeno v DKUM: 04.06.2019; Ogledov: 1488; Prenosov: 119
Celotno besedilo (4,27 MB) |
6. Linear recognition of generalized Fibonacci cubes $Q_h (111)$Yoomi Rho, Aleksander Vesel, 2016, izvirni znanstveni članek Opis: 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.
Ključne besede: graph theory, Fibonacci cubes, recognition algorithm
Objavljeno v DKUM: 10.07.2017; Ogledov: 1386; Prenosov: 213
Celotno besedilo (803,81 KB)
Gradivo ima več datotek! Več... |
7. L(2,1)-labeling of the strong product of paths and cyclesZehui Shao, Aleksander Vesel, 2014, izvirni znanstveni članek Opis: 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.
Ključne besede: mathematics, graph theory
Objavljeno v DKUM: 15.06.2017; Ogledov: 1227; Prenosov: 347
Celotno besedilo (2,31 MB)
Gradivo ima več datotek! Več... |
8. 1-factors and characterization of reducible faces of plane elementary bipartite graphsAndrej Taranenko, Aleksander Vesel, 2012, izvirni znanstveni članek Opis: 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.
Ključne besede: mathematics, graph theory, plane elementary bipartite graph, reducible face, benzenoid graph
Objavljeno v DKUM: 31.03.2017; Ogledov: 1132; Prenosov: 397
Celotno besedilo (139,73 KB)
Gradivo ima več datotek! Več... |
9. Fibonaccijeva dimenzija resonančnih grafov katakondenziranih benzenoidnih grafovJanja Rebernik, 2016, magistrsko delo Opis: 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.
Ključne besede: benzenoidni graf, katakondenzirani benzenoidni graf, Fibonaccijeva dimenzija, 1-faktor, resonančni graf
Objavljeno v DKUM: 12.05.2016; Ogledov: 1225; Prenosov: 152
Celotno besedilo (1,32 MB) |
10. Hibridni algoritmi za barvanje grafovMartin Duh, 2016, magistrsko delo Opis: 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.
Ključne besede: algoritmi, grafi, barvanje grafa, lokalno iskanje, variabilno lokalno iskanje, evolucijski algoritmi, hibridni algoritmi
Objavljeno v DKUM: 15.02.2016; Ogledov: 1822; Prenosov: 153
Celotno besedilo (715,10 KB) |
