Computing the permanental polynomials of bipartite graphs by Pfaffian orientation

DOI10.1016/J.DAM.2012.04.007zbMATH Open1246.05100arXiv1010.1113OpenAlexW2089593901MaRDI QIDQ442233FDOQ442233

Authors: Heping Zhang, Wei Li 

Publication date: 10 August 2012

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

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.

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

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

zbMATH Keywords

determinantPfaffian orientationpermanental polynomialpermanent1-cycle resonant

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• Matching theory
• Title not available (Why is that?)
• A characterization of convertible (0,1)-matrices
• The complexity of computing the permanent
• Permanental polynomials of graphs
• On the permanental polynomials of some graphs
• Title not available (Why is that?)
• Title not available (Why is that?)
• Plane elementary bipartite graphs
• Reducible chains of planar 1-cycle resonant graphs
• Even circuits of prescribed clockwise parity
• \(k\)-cycle resonant graphs
• Planar \(k\)-cycle resonant graphs with \(k=1,2\)
• An efficient algorithm for computing permanental polynomials of graphs

Cited In (30)

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