1. The independence coloring game on graphsBoštjan Brešar, Daša Mesarič Štesl, 2022, izvirni znanstveni članek 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: 90; Prenosov: 3 Celotno besedilo (852,33 KB) Gradivo ima več datotek! Več... |
2. On Grundy total domination number in product graphsBoš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, izvirni znanstveni članek Opis: 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. Ključne besede: total domination, Grundy total domination number, graph product Objavljeno v DKUM: 07.08.2024; Ogledov: 89; Prenosov: 3 Celotno besedilo (248,02 KB) Gradivo ima več datotek! Več... |
3. |
4. |
5. 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: 91; Prenosov: 6 Celotno besedilo (518,69 KB) Gradivo ima več datotek! Več... |
6. Span of a graph : keeping the safety distanceIztok Banič, Andrej Taranenko, 2023, izvirni znanstveni članek Opis: Inspired by Lelek's idea from [Disjoint mappings and the span of spaces, Fund. Math. 55 (1964), 199 -- 214], we introduce the novel notion of the span of graphs. Using this, we solve the problem of determining the \emph{maximal safety distance} two players can keep at all times while traversing a graph. Moreover, their moves must be made with respect to certain move rules. For this purpose, we introduce different variants of a span of a given connected graph. All the variants model the maximum safety distance kept by two players in a graph traversal, where the players may only move with accordance to a specific set of rules, and their goal: visit either all vertices, or all edges. For each variant, we show that the solution can be obtained by considering only connected subgraphs of a graph product and the projections to the factors. We characterise graphs in which it is impossible to keep a positive safety distance at all moments in time. Finally, we present a polynomial time algorithm that determines the chosen span variant of a given graph. Ključne besede: strong span of a graph, direct span of a graph, Cartesian span of a graph, safety distance Objavljeno v DKUM: 07.06.2024; Ogledov: 86; Prenosov: 6 Celotno besedilo (213,47 KB) Gradivo ima več datotek! Več... |
7. |
8. Generalized cut method for computing Szeged-like polynomials with applications to polyphenyls and carbon nanoconesSimon Brezovnik, Niko Tratnik, 2023, izvirni znanstveni članek Opis: Szeged, Padmakar-Ivan (PI), and Mostar indices are some of the most investigated distance-based Szeged-like topological indices. On the other hand, the polynomials related to these topological indices were also introduced, for example the Szeged polynomial, the edge- Szeged polynomial, the PI polynomial, the Mostar polynomial, etc. In this paper, we introduce a concept of the general Szeged-like polynomial for a connected strength-weighted graph. It turns out that this concept includes all the above mentioned polynomials and also infinitely many other graph polynomials. As the main result of the paper, we prove a cut method which enables us to efficiently calculate a Szeged-like polynomial by using the corresponding polynomials of strength-weighted quotient graphs obtained by a partition of the edge set that is coarser than ▫$\Theta^*$▫-partition. To the best of our knowledge, this represents the first implementation of the famous cut method to graph polynomials. Finally, we show how the deduced cut method can be applied to calculate some Szeged-like polynomials and corresponding topological indices of para-polyphenyl chains and carbon nanocones. Ključne besede: graph theory, carbon nanocone, topological indices Objavljeno v DKUM: 25.03.2024; Ogledov: 232; Prenosov: 3 Povezava na celotno besedilo |
9. Outerplane bipartite graphs with isomorphic resonance graphsSimon Brezovnik, Zhongyuan Che, Niko Tratnik, Petra Žigert Pleteršek, 2024, izvirni znanstveni članek Opis: We present novel results related to isomorphic resonance graphs of 2-connected outerplane bipartite graphs. As the main result, we provide a structure characterization for 2-connected outerplane bipartite graphs with isomorphic resonance graphs. Three additional characterizations are expressed in terms of resonance digraphs, via local structures of inner duals, as well as using distributive lattices on the set of order ideals of posets defined on inner faces of 2-connected outerplane bipartite graphs. Ključne besede: distributive lattice, inner dual, isomorphic resonance graphs, order ideal, 2-connected outerplane bipartite graph Objavljeno v DKUM: 29.02.2024; Ogledov: 285; Prenosov: 9 Povezava na celotno besedilo |
10. Knowledge Graph Completion with Triple Structure and Text RepresentationShuang Liu, Yufeng Qin, Man Xu, Simon Kolmanič, 2023, izvirni znanstveni članek Opis: Knowledge Graphs (KGs) describe objective facts in the form of RDF triples, each triple contains sufficient semantic information and triple structure information. Knowledge Graph Completion (KGC) is to acquire new knowledge by predicting hidden relationships between entities and adding the new knowledge to the KG. At present, the mainstream KGC approaches only applied the triple structure information or only utilized the semantic information of the text. This paper proposes an approach (TSTR) using BERT and deep neural networks to fully extract the semantic information of knowledge, and designs an aggregated re-ranking scheme that incorporates existing graph embedding approach to learn the structural information of triples. In experiments, the approach achieves state-of-the-art performance on three benchmark datasets, and outperforms recent KGC approaches on sparsely connected datasets. Ključne besede: knowledge graph completion, BERT, deep convolutional architecture, re-ranking Objavljeno v DKUM: 19.02.2024; Ogledov: 222; Prenosov: 18 Celotno besedilo (1,03 MB) Gradivo ima več datotek! Več... |