Counting Hexagonal Patches and Independent Sets in Circle Graphs

Details Counting Hexagonal Patches and Independent Sets in Circle Graphs Counting Hexagonal Patches and Independent Sets in Circle Graphs

2008-08-28

arxiv.org/abs/0808.3881v2

Computer Science

Discrete Mathematics

Scientific paper

A hexagonal patch is a plane graph in which inner faces have length 6, inner vertices have degree 3, and boundary vertices have degree 2 or 3. We consider the following counting problem: given a sequence of twos and threes, how many hexagonal patches exist with this degree sequence along the outer face? This problem is motivated by the study of benzenoid hydrocarbons and fullerenes in computational chemistry. We give the first polynomial time algorithm for this problem. We show that it can be reduced to counting maximum independent sets in circle graphs, and give a simple and fast algorithm for this problem.

Affiliated with

Also associated with

No associations

Rating

Counting Hexagonal Patches and Independent Sets in Circle Graphs does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Counting Hexagonal Patches and Independent Sets in Circle Graphs, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Counting Hexagonal Patches and Independent Sets in Circle Graphs will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-327202