کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
418955 | 681728 | 2008 | 14 صفحه PDF | دانلود رایگان |
![عکس صفحه اول مقاله: Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphs Characterization of reducible hexagons and fast decomposition of elementary benzenoid graphs](/preview/png/418955.png)
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)O(n2) time. Moreover, we present an algorithm which decomposes an elementary benzenoid graph with at most one pericondensed component in linear time.
Journal: Discrete Applied Mathematics - Volume 156, Issue 10, 28 May 2008, Pages 1711–1724