Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5773265 | Linear Algebra and its Applications | 2017 | 18 Pages |
Abstract
In 1980, Balasubramanian and Parthasarathy introduced the bivariate permanent polynomials of graphs and conjectured that this polynomial is a graph characterizing polynomial, that is, any two graphs with the same bivariate permanent polynomial are isomorphic. In this paper, we give counterexamples to this conjecture by a computer search. Furthermore, we show that several well-known families of graphs are determined by the bivariate permanent polynomial: complete graphs, complete bipartite graphs, regular complete multipartite graphs, cycles and their complements.
Related Topics
Physical Sciences and Engineering
Mathematics
Algebra and Number Theory
Authors
Shunyi Liu,