Andrej Taranenko (Author), Aleksander Vesel (Author)

Abstract

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.

Keywords

matematika;teorija grafov;benzenoidni grafi;1-faktor;šestkotniška mreža;mathematics;graph theory;benzenoid graphs;1-factor;hexagons;reducible hexagons;reducible face decomposition;

Data

Language: English
Year of publishing:
Typology: 1.01 - Original Scientific Article
Organization: UM FNM - Faculty of Natural Sciences and Mathematics
UDC: 519.17
COBISS: 16140552 Link will open in a new window
ISSN: 0166-218X
Views: 1445
Downloads: 79
Average score: 0 (0 votes)
Metadata: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Other data

Secondary language: English
Secondary keywords: matematika;teorija grafov;benzenoidni grafi;1-faktor;šestkotniška mreža;
URN: URN:SI:UM:
Pages: str. 1711-1724
Volume: ǂVol. ǂ156
Issue: ǂiss. ǂ10
Chronology: 2008
DOI: 10.1016/j.dam.2007.08.029
ID: 8724032