1. |
2. 1-factors and characterization of reducible faces of plane elementary bipartite graphsAndrej Taranenko, Aleksander Vesel, 2012, izvirni znanstveni članek Opis: As a general case of molecular graphs of benzenoid hydrocarbons, we study plane bipartite graphs with Kekulé structures (1-factors). A bipartite graph ▫$G$▫ is called elementary if ▫$G$▫ is connected and every edge belongs to a 1-factor of ▫$G$▫. Some properties of the minimal and the maximal 1-factor of a plane elementary graph are given. A peripheral face ▫$f$▫ of a plane elementary graph is reducible, if the removal of the internal vertices and edges of the path that is the intersection of ▫$f$▫ and the outer cycle of ▫$G$▫ results in an elementary graph. We characterize the reducible faces of a plane elementary bipartite graph. This result generalizes the characterization of reducible faces of an elementary benzenoid graph.
Ključne besede: mathematics, graph theory, plane elementary bipartite graph, reducible face, benzenoid graph
Objavljeno v DKUM: 31.03.2017; Ogledov: 1132; Prenosov: 418
 Celotno besedilo (139,73 KB)
Gradivo ima več datotek! Več... |
3. 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 |
4. Binary coding of algebraic Kekulé structures of catacondensed benzenoid graphsDamir Vukičević, Petra Žigert Pleteršek, 2008, izvirni znanstveni članek Opis: Algebraična Kekuléjeva struktura končnega katakondenziranega benzenoidnega grafa s ▫$h$▫ šestkotniki je podana z binarno kodo dolžine ▫$h$▫. Postopek je obrnljiv in sicer lahko iz binarne kode rekonstruiramo algebraično Kekuléjevo strukturo.
Ključne besede: matematika, kemijska teorija grafov, benzenoidni ogljikovodiki, benzenoidni grafi, Kekuléjeve strukture, Randićeve strukture, 1-faktor, binarno kodiranje, mathematics, chemical graph theory, benzenoid hydrocarbons, benzenoid graph, Kekulé structures, algebraic Kekulé structures, Randić structures, 1-factor, binary coding
Objavljeno v DKUM: 10.07.2015; Ogledov: 1256; Prenosov: 100
Povezava na celotno besedilo |
5. On the role of hypercubes in the resonance graphs of benzenoid graphsKhaled Salem, Sandi Klavžar, Ivan Gutman, 2006, drugi znanstveni članki Opis: The resonance graph ▫$R(B)$▫ of a benzenoid graph ▫$B$▫ has the perfect matchings of ▫$B$▫ as vertices, two perfect matchings being adjacent if their symmetric difference forms the edge set of a hexagon of ▫$B$▫. A family ▫$mathscr{P}$▫ of pair-wise disjoint hexagons of a benzenoid graph ▫$B$▫ is resonant in ▫$B$▫ if ▫$B -- mathscr{P}$▫ contains at least one perfect matching, or if ▫$B -- mathscr{P}$▫ is empty. It is proven that there exists a surjective map ▫$f$▫ from the set of hypercubes of ▫$R(B)$▫ onto the resonant sets of B such that a ▫$k$▫-dimensional hypercube is mapped into a resonant set of cardinality ▫$k$▫.
Ključne besede: matematika, teorija grafov, benzenoidni graf, popolno prirejanje, resonančni graf, hiperkocka, mathematics, graph theory, benzenoid graph, perfect matching, resonance graph, hypercube
Objavljeno v DKUM: 10.07.2015; Ogledov: 1589; Prenosov: 79
Povezava na celotno besedilo |
6. Ivanciuc, Ovidiu; Ivanciuc, Teodora; Klein, Douglas J.: Intrinsic graph distances compared to Euclidean distances for correspondent graph embedding. - Match No. 44 (2001), 251-278Sandi Klavžar, 2002, recenzija, prikaz knjige, kritika Ključne besede: matematika, teorija grafov, razdalja v grafu, evklidska razdalja, benzenoidni sistemi, mathematics, graph theory, graph distance functions, Euclidean distances, benzenoid systems
Objavljeno v DKUM: 10.07.2015; Ogledov: 1281; Prenosov: 47
Povezava na celotno besedilo |
7. Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphsAndrej Taranenko, Aleksander Vesel, 2008, izvirni znanstveni članek 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 v DKUM: 07.06.2012; Ogledov: 1924; Prenosov: 95
Povezava na celotno besedilo |
