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: 10.07.2015; Ogledov: 616; Prenosov: 68 Povezava na celotno besedilo

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: 10.07.2015; Ogledov: 554; Prenosov: 21 Povezava na celotno besedilo

Opis: A benzenoid graph is a finite connected plane graph with no cut vertices in which every interior region is bounded by a regular hexagon of a side length one. A benzenoid graph G is elementary if every edge belongs to a 1-factor of G. A hexagon h of an elementary benzenoid graph is reducible, if the removal of boundary edges and vertices of h results in an elementary benzenoid graph. We characterize the reducible hexagons of an elementary benzenoid graph. The characterization is the basis for an algorithm which finds the sequence of reducible hexagons that decompose a graph of this class in ▫$O(n^2)$▫ time. Moreover, we present an algorithm which decomposes an elementary benzenoid graph with at most one pericondensed component in linear time. Ključne besede:mathematics, graph theory, benzenoid graphs, 1-factor, hexagons, reducible hexagons, reducible face decomposition Objavljeno: 07.06.2012; Ogledov: 1301; Prenosov: 73 Povezava na celotno besedilo