1. Resonance graphs and a binary coding of perfect matchings of outerplane bipartite graphsSimon Brezovnik, Niko Tratnik, Petra Žigert Pleteršek, 2023, izvirni znanstveni članek Opis: The aim of this paper is to investigate resonance graphs of $2$-connected outerplane bipartite graphs, which include various families of molecular graphs. Firstly, we present an algorithm for a binary coding of perfect matchings of these graphs. Further, $2$-connected outerplane bipartite graphs with isomorphic resonance graphs are considered. In particular, it is shown that if two $2$-connected outerplane bipartite graphs are evenly homeomorphic, then its resonance graphs are isomorphic. Moreover, we prove that for any $2$-connected outerplane bipartite graph $G$ there exists a catacondensed even ring systems $H$ such that the resonance graphs of $G$ and $H$ are isomorphic. We conclude with the characterization of $2$-connected outerplane bipartite graphs whose resonance graphs are daisy cubes.
Ključne besede: graph theory, resonance graphs, bipartite graphs
Objavljeno v DKUM: 10.12.2024; Ogledov: 0; Prenosov: 11
 Povezava na celotno besedilo
Gradivo ima več datotek! Več... |
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: 14
 Celotno besedilo (518,69 KB)
Gradivo ima več datotek! Več... |
3. 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: 11
Povezava na celotno besedilo |
4. Fibonacci dimension of the resonance graphs of catacondensed benzenoid graphsAleksander Vesel, 2013, izvirni znanstveni članek Opis: 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.
Ključne besede: Fibonaccijeva dimenzija, benzenoidni sistemi, resonančni grafi, algoritem, Fibonacci dimension, benzenoid systems, resonance graphs, algorithm
Objavljeno v DKUM: 10.07.2015; Ogledov: 1171; Prenosov: 87
Povezava na celotno besedilo |
5. On the Fibonacci dimension of partial cubesAleksander Vesel, 2009 Opis: The Fibonacci dimension fdim▫$(G)$▫ of a graph ▫$G$▫ was introduced in [S. Cabello, D. Eppstein and S. Klavžar, The Fibonacci dimension of a graph, submitted] as the smallest integer ▫$d$▫ such that $G$ admits an isometric embedding into ▫$Q_d$▫, the ▫$d$▫-dimensional Fibonacci cube. A somewhat new combinatorial characterization of the Fibonacci dimension is given, which enables more comfortable proofs of some previously known results. In the second part of the paper 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. The main result shows 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.
Ključne besede: matematika, teorija grafov, Fibonaccijeva dimenzija, delne kocke, resonančni grafi, benzenoidni sistemi, mathematics, graph theory, Fibonacci dimension, partial cubes, resonance graphs, benzenoid systems
Objavljeno v DKUM: 10.07.2015; Ogledov: 1223; Prenosov: 44
Povezava na celotno besedilo |
