Hostname: page-component-74656f9884-c52kr Total loading time: 0 Render date: 2026-11-09T04:28:14.966Z Has data issue: false hasContentIssue false

Evaluating the Rank Generating Function of a Graphic 2-Polymatroid

Published online by Cambridge University Press:  07 April 2006

S. D. NOBLE
Affiliation:
Department of Mathematical Sciences, Brunel University, Kingston Lane, Uxbridge UB8 3PH, UK (e-mail: mastsdn@brunel.ac.uk)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Copyright
2006 Cambridge University Press