Please use this identifier to cite or link to this item: http://bura.brunel.ac.uk/handle/2438/818
 Title: Evaluating the rank generating function of a graphic 2-polymatroid Authors: Noble, SD Keywords: Polymatroid;Rank generating function;Matroid;Computational complexity;#P-hard;Graph Issue Date: 2006 Publisher: Cambridge University Press Citation: Combinatorics, Probability and Computing 15: 449-461, May 2006 Abstract: We consider the complexity of the two-variable rank generating function, $S$, of a graphic 2-polymatroid. For a graph $G$, $S$ is the generating function for the number of subsets of edges of $G$ having a particular size and incident with a particular number of vertices of $G$. We show that for any $x,y \in \mathbb{Q}$ with $xy \not = 1$, it is $\#$P-hard to evaluate $S$ at $(x,y)$. We also consider the $k$-thickening of a graph and computing $S$ for the $k$-thickening of a graph. URI: http://bura.brunel.ac.uk/handle/2438/818 ISSN: 0963-5483 Appears in Collections: Mathematical ScienceComputer Science

Files in This Item:
File Description SizeFormat