Computing the permanental polynomials of bipartite graphs by Pfaffian orientation

Details Computing the permanental polynomials of bipartite graphs by Pfaffian orientation Computing the permanental polynomials of bipartite graphs by Pfaffian orientation

2010-10-06

arxiv.org/abs/1010.1113v1

Mathematics

Combinatorics

17 pages, 5 figures

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Computing the permanental polynomials of bipartite graphs by Pfaffian orientation 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 Computing the permanental polynomials of bipartite graphs by Pfaffian orientation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Computing the permanental polynomials of bipartite graphs by Pfaffian orientation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-427456