A Most General Edge Elimination Polynomial - Thickening of Edges

Details A Most General Edge Elimination Polynomial - Thickening of Edges A Most General Edge Elimination Polynomial - Thickening of Edges

2008-01-10

arxiv.org/abs/0801.1600v1

Mathematics

Combinatorics

5 pages

Scientific paper

We consider a graph polynomial \xi(G;x,y,z) introduced by Averbouch, Godlin, and Makowsky (2007). This graph polynomial simultaneously generalizes the Tutte polynomial as well as a bivariate chromatic polynomial defined by Dohmen, Poenitz and Tittmann (2003). We derive an identity which relates the graph polynomial of a thicked graph (i.e. a graph with each edge replaced by k copies of it) to the graph polynomial of the original graph. As a consequence, we observe that at every point (x,y,z), except for points lying within some set of dimension 2, evaluating \xi is #P-hard.

Affiliated with

Also associated with

No associations

Rating

A Most General Edge Elimination Polynomial - Thickening of Edges 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 A Most General Edge Elimination Polynomial - Thickening of Edges, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and A Most General Edge Elimination Polynomial - Thickening of Edges will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-436471