Andrej Taranenko (Avtor), Aleksander Vesel (Avtor)

Povzetek

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

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

Podatki

Jezik: Angleški jezik
Leto izida:
Tipologija: 1.01 - Izvirni znanstveni članek
Organizacija: UM FNM - Fakulteta za naravoslovje in matematiko
UDK: 519.17
COBISS: 16140552 Povezava se bo odprla v novem oknu
ISSN: 0166-218X
Št. ogledov: 1445
Št. prenosov: 79
Ocena: 0 (0 glasov)
Metapodatki: JSON JSON-RDF JSON-LD TURTLE N-TRIPLES XML RDFA MICRODATA DC-XML DC-RDF RDF

Ostali podatki

Sekundarni jezik: Angleški jezik
Sekundarne ključne besede: matematika;teorija grafov;benzenoidni grafi;1-faktor;šestkotniška mreža;
URN: URN:SI:UM:
Strani: str. 1711-1724
Letnik: ǂVol. ǂ156
Zvezek: ǂiss. ǂ10
Čas izdaje: 2008
DOI: 10.1016/j.dam.2007.08.029
ID: 8724032