Counterexamples to a conjecture of Balasubramanian and Parthasarathy

2015/02/06 by Shunyi Liu, Liu, Shunyi
Computer Science · Mathematics · #05C31 #05C50 #15A15 #Advanced Combinatorial Mathematics #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph theory and applications

paper · pdf · doi:10.48550/arxiv.1502.01886

openalex publication_date 2015/02/06 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In 1980, Balasubramanian and Parthasarathy introduced the bivariate permanent polynomials of graphs and conjectured that this graph polynomial is a graph characterising polynomial, that is, any two graphs with the same bivariate permanent polynomial are isomorphic. In this note, we give counter examples to this conjecture.

Related

• Computing the permanental polynomials of bipartite graphs by Pfaffian orientation
• The characterizing properties of (signless) Laplacian permanental polynomials of bicyclic graphs
• Enumeration of copermanental graphs
• The Bipartition Polynomial of a Graph: Reconstruction, Decomposition, and Applications
• Complete r-partite graphs determined by their domination polynomial