pith. sign in

arxiv: 1010.1113 · v1 · pith:KCOVTYGPnew · submitted 2010-10-06 · 🧮 math.CO

Computing the permanental polynomials of bipartite graphs by Pfaffian orientation

classification 🧮 math.CO
keywords bipartitegraphevenpermanentalsubdivisioncontainscyclegraphs
0
0 comments X
read the original abstract

The permanental polynomial of a graph $G$ is $\pi(G,x)\triangleq\mathrm{per}(xI-A(G))$. From the result that a bipartite graph $G$ admits an orientation $G^e$ such that every cycle is oddly oriented if and only if it contains no even subdivision of $K_{2,3}$, Yan and Zhang showed that the permanental polynomial of such a bipartite graph $G$ can be expressed as the characteristic polynomial of the skew adjacency matrix $A(G^e)$. In this paper we first prove that this equality holds only if the bipartite graph $G$ contains no even subdivision of $K_{2,3}$. Then we prove that such bipartite graphs are planar. Further we mainly show that a 2-connected bipartite graph contains no even subdivision of $K_{2,3}$ if and only if it is planar 1-cycle resonant. This implies that each cycle is oddly oriented in any Pfaffian orientation of a 2-connected bipartite graph containing no even subdivision of $K_{2,3}$. As applications, permanental polynomials for some types of bipartite graphs are computed.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.