Computing the permanental polynomials of bipartite graphs by Pfaffian orientation

DOI10.1016/J.DAM.2012.04.007MaRDI QIDQ442233zbMATH OpenOpenAlexFDO

Authors Heping Zhang, Wei Li

Publication date 10 August 2012

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1010.1113

zbMATH Keywords

determinantPfaffian orientationpermanental polynomialpermanent1-cycle resonant

Mathematics Subject Classification ID

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50)

Abstract: The permanental polynomial of a graph $G$ is $pi(G,x)riangleqmathrmper(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.

Recommendations

• On the permanental polynomials of some graphs
• On the skew-permanental polynomials of orientation graphs
• scientific article; zbMATH DE number 1559555
• Pfaffian orientations for a type of bipartite graph
• On the theory of Pfaffian orientations. I: Perfect matchings and permanents

Cites work

• scientific article; zbMATH DE number 3929044 (Why is no real title available?)
• scientific article; zbMATH DE number 3717357 (Why is no real title available?)
• scientific article; zbMATH DE number 1890155 (Why is no real title available?)
• A characterization of convertible (0,1)-matrices
• An efficient algorithm for computing permanental polynomials of graphs
• Even circuits of prescribed clockwise parity
• Graph theory
• Matching theory
• On the permanental polynomials of some graphs
• Permanental polynomials of graphs
• Planar \(k\)-cycle resonant graphs with \(k=1,2\)
• Plane elementary bipartite graphs
• Reducible chains of planar 1-cycle resonant graphs
• The complexity of computing the permanent
• \(k\)-cycle resonant graphs

Cited in

(30)

• On the permanental polynomials of matrices
• A note on graphs with purely imaginary per-spectrum
• A study on determination of some graphs by Laplacian and signless Laplacian permanental polynomials
• On the bivariate permanent polynomials of graphs
• Extremal octagonal chains with respect to the coefficients sum of the permanental polynomial
• On the permanental sum of graphs
• Extremal hexagonal chains with respect to the coefficients sum of the permanental polynomial
• On the skew-permanental polynomials of orientation graphs
• Sharp bounds on the permanental sum of a graph
• The graphs whose permanental polynomials are symmetric
• On the matching and permanental polynomials of graphs
• On the permanental sum of bicyclic graphs
• On the Permanental Polynomial and Permanental Sum of Signed Graphs
• On the permanental polynomials of some graphs
• Some extremal graphs with respect to permanental sum
• Per-spectral characterizations of some edge-deleted subgraphs of a complete graph
• Constructing graphs which are permanental cospectral and adjacency cospectral
• Characterizing properties of permanental polynomials of lollipop graphs
• Per-spectral characterizations of graphs with extremal per-nullity
• Graphs determined by the (signless) Laplacian permanental polynomials
• Enumeration of permanental sums of lattice graphs
• On the normalized Laplacian permanental polynomial of a graph
• Computing the permanental polynomials of graphs
• Per-spectral and adjacency spectral characterizations of a complete graph removing six edges
• On the permanental nullity and matching number of graphs
• The coefficients of the immanantal polynomial
• Unicyclic graphs with second largest and second smallest permanental sums
• Per-spectral characterizations of some bipartite graphs
• A note on the permanental roots of bipartite graphs
• On the skew spectra of Cartesian products of graphs

This page was built for publication: Computing the permanental polynomials of bipartite graphs by Pfaffian orientation

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q442233)