1. An asymptotic relation between the wirelength of an embedding and the Wiener indexK. Jagadeesh Kumar, Sandi Klavžar, R. Sundara Rajan, Indra Rajasingh, T. M. Rajalaxmi, 2021, izvirni znanstveni članek Opis: Wirelength is an important criterion to validate the quality of an embedding of a graph into a host graph and is used in particular in VLSI (Very-Large-Scale Integration) layout designs. Wiener index plays a significant role in mathematical chemistry, cheminformatics, and elsewhere. In this note these two concepts are related by proving that the Wiener index of a host graph is an upper bound for the wirelength of a given embedding. The wirelength of embedding complete ▫$2^p$▫-partite graphs into Cartesian products of paths and/or cycles as the function of the Wiener index is determined. The result is an asymptotic approximation of the general upper bound.
Ključne besede: Wiener index, embedding, wirelength, complete 2p-partite graph, Cartesian product of graphs, integer labeling
Objavljeno v DKUM: 23.09.2024; Ogledov: 0; Prenosov: 0
 Celotno besedilo (365,63 KB)
Gradivo ima več datotek! Več... |
2. 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: 99; Prenosov: 3
Celotno besedilo (852,33 KB)
Gradivo ima več datotek! Več... |
3. 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: 96; Prenosov: 7
Celotno besedilo (248,02 KB)
Gradivo ima več datotek! Več... |
4. |
5. |
6. 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č... |
7. 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: 98; Prenosov: 6
Celotno besedilo (213,47 KB)
Gradivo ima več datotek! Več... |
8. |
9. 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: 234; Prenosov: 3
 Povezava na celotno besedilo |
10. 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: 290; Prenosov: 9
Povezava na celotno besedilo |
