| | SLO | ENG | Cookies and privacy

Bigger font | Smaller font
First page > Show document

Show document Help

Title:Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphs
Authors:ID Taranenko, Andrej (Author)
ID Vesel, Aleksander (Author)
Files:URL http://dx.doi.org/10.1016/j.dam.2007.08.029
 
Language:English
Work type:Unknown
Typology:1.01 - Original Scientific Article
Organization:FNM - Faculty of Natural Sciences and Mathematics
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(n2) time. Moreover, we present an algorithm which decomposes an elementary benzenoid graph with at most one pericondensed component in linear time.
Keywords:mathematics, graph theory, benzenoid graphs, 1-factor, hexagons, reducible hexagons, reducible face decomposition
Year of publishing:2008
PID:20.500.12556/DKUM-35731 New window
UDC:519.17
ISSN on article:0166-218X
COBISS.SI-ID:16140552 New window
NUK URN:URN:SI:UM:DK:VMCNDQJE
Publication date in DKUM:07.06.2012
Views:1924
Downloads:95
Metadata:XML DC-XML DC-RDF
Categories:Misc.
:
TARANENKO, Andrej and VESEL, Aleksander, 2008, Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphs. Discrete applied mathematics [online]. 2008. [Accessed 4 April 2025]. Retrieved from: http://dx.doi.org/10.1016/j.dam.2007.08.029
Copy citation
  
Average score:
0.5
1
1.5
2
2.5
3
3.5
4
4.5
5
(0 votes)
Your score:Voting is allowed only for logged in users.
Share:Bookmark and Share


Hover the mouse pointer over a document title to show the abstract or click on the title to get all document metadata.

Record is a part of a journal

Title:Discrete applied mathematics
Shortened title:Discrete appl. math.
Publisher:Elsevier
ISSN:0166-218X
COBISS.SI-ID:25342464 New window

Secondary language

Language:English
Keywords:matematika, teorija grafov, benzenoidni grafi, 1-faktor, šestkotniška mreža


Comments

Leave comment

You must log in to leave a comment.

Comments (0)
0 - 0 / 0
 
There are no comments!

Back
Logos of partners University of Maribor University of Ljubljana University of Primorska University of Nova Gorica