1. |
2. Efficient proper embedding of a daisy cubeAleksander Vesel, 2021, original scientific article Abstract: For a set ▫$X$▫ of binary words of length ▫$h$▫ the daisy cube ▫$Q_h(X)$▫ is defined as the subgraph of the hypercube ▫$Q_h$▫ induced by the set of all vertices on shortest paths that connect vertices of ▫$X$▫ with the vertex ▫$0^h$▫. A vertex in the intersection of all of these paths is a minimal vertex of a daisy cube. A graph ▫$G$▫ isomorphic to a daisy cube admits several isometric embeddings into a hypercube. We show that an isometric embedding is proper if and only if the label ▫$0^h$▫ is assigned to a minimal vertex of ▫$G$▫. This result allows us to devise an algorithm which finds a proper embedding of a graph isomorphic to a daisy cube into a hypercube in linear time.
Keywords: daisy cube, partial cube, isometric embedding, proper embedding
Published in DKUM: 29.11.2024; Views: 0; Downloads: 3
 Full text (293,91 KB)
This document has many files! More... |
3. Linear algorithms for the Hosoya index and Hosoya matrix of a treeAleksander Vesel, 2021, original scientific article Abstract: The Hosoya index of a graph is defined as the total number of its independent edge sets. This index is an important example of topological indices, a molecular-graph based structure descriptor that is of significant interest in combinatorial chemistry. The Hosoya index inspires the introduction of a matrix associated with a molecular acyclic graph called the Hosoya matrix. We propose a simple linear-time algorithm, which does not require pre-processing, to compute the Hosoya index of an arbitrary tree. A similar approach allows us to show that the Hosoya matrix can be computed in constant time per entry of the matrix.
Keywords: Hosoya index, Hosoya matrix, optimal algorithm
Published in DKUM: 18.10.2024; Views: 0; Downloads: 3
Full text (260,38 KB)
This document has many files! More... |
4. Mutual-visibility sets in cartesian products of paths and cyclesDanilo Korže, Aleksander Vesel, 2024, original scientific article Abstract: 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.
Keywords: mutual-visibility set, supermutual-visibility number, Cartesian product
Published in DKUM: 14.08.2024; Views: 73; Downloads: 14
Full text (596,74 KB) |
5. Binary coding of resonance graphs of catacondensed polyhexesAleksander Vesel, 2023, original scientific article Abstract: 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.
Keywords: graphs, graph theory, resonance graphs
Published in DKUM: 07.06.2024; Views: 99; Downloads: 14
Full text (518,69 KB)
This document has many files! More... |
6. General Position Sets in Two Families of Cartesian Product GraphsDanilo Korže, Aleksander Vesel, 2023, original scientific article Abstract: 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.
Keywords: general position set, cartesian product, hypercube, SAT
Published in DKUM: 02.04.2024; Views: 256; Downloads: 22
Full text (405,17 KB)
This document has many files! More... |
7. Barvanje povezav grafa z najmanjšim številom palet : na študijskem programu Izobraževalna matematika in izobraževalno računalništvoKarmen Bregač, 2023, master's thesis Abstract: 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.
Keywords: Barvanje povezav, paletno barvanje povezav, paletni indeks.
Published in DKUM: 07.09.2023; Views: 423; Downloads: 29
Full text (5,34 MB) |
8. (d, n)-pakirno barvanje za posplošene grafe Sierpińskega : magistrsko deloAnž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 in DKUM: 04.06.2019; Views: 1488; Downloads: 123
Full text (4,27 MB) |
9. 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 in DKUM: 10.07.2017; Views: 1386; Downloads: 225
Full text (803,81 KB)
This document has many files! More... |
10. L(2,1)-labeling of the strong product of paths and cyclesZehui 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 in DKUM: 15.06.2017; Views: 1227; Downloads: 354
Full text (2,31 MB)
This document has many files! More... |
