Generalized permanental polynomials of graphs
Summary: The search for complete graph invariants is an important problem in graph theory and computer science. Two networks with a different structure can be distinguished from each other by complete graph invariants. In order to find a complete graph invariant, we introduce the generalized permanental polynomials of graphs. Let \(G\) be a graph with adjacency matrix \(A(G)\) and degree matrix \(D(G)\). The generalized permanental polynomial of \(G\) is defined by \(P_G(x, \mu) = \operatorname{per}(x I -(A(G) - \mu D(G)))\). In this paper, we compute the generalized permanental polynomials for all graphs on at most 10 vertices, and we count the numbers of such graphs for which there is another graph with the same generalized permanental polynomial. The present data show that the generalized permanental polynomial is quite efficient for distinguishing graphs. Furthermore, we can write \(P_G(x, \mu)\) in the coefficient form \(\sum_{i = 0}^n c_{\mu i}(G) x^{n - i}\) and obtain the combinatorial expressions for the first five coefficients \(c_{\mu i}(G)\) (\(i = 0, 1, \ldots, 4\)) of \(P_G(x, \mu)\).
- A computational approach to construct a multivariate complete graph invariant
- Characterizing properties of permanental polynomials of lollipop graphs
- Cospectral graphs and the generalized adjacency matrix
- Encoding structural information uniquely with polynomial-based descriptors by employing the Randić matrix
- Graph characterising polynomials
- Graph measures with high discrimination power revisited: a random polynomial approach
- Graph polynomials
- Graphs determined by polynomial invariants
- Highly unique network descriptors based on the roots of the permanental polynomial
- scientific article; zbMATH DE number 3783048 (Why is no real title available?)
- scientific article; zbMATH DE number 2010146 (Why is no real title available?)
- scientific article; zbMATH DE number 6181058 (Why is no real title available?)
- nauty
- On the bivariate permanent polynomials of graphs
- On the characterizing properties of the permanental polynomials of graphs
- Per-spectral and adjacency spectral characterizations of a complete graph removing six edges
- Per-spectral characterizations of graphs with extremal per-nullity
- Per-spectral characterizations of some edge-deleted subgraphs of a complete graph
- Permanental polynomials of graphs
- Permanental roots and the star degree of a graph
- Practical graph isomorphism. II.
- The complexity of computing the permanent
- Graph characterising polynomials
- The graphs whose permanental polynomials are symmetric
- Immanantal invariants of graphs
- Highly unique network descriptors based on the roots of the permanental polynomial
- On the bivariate permanent polynomials of graphs
- Measuring similarity between connected graphs: the role of induced subgraphs and complementarity eigenvalues
- The permanental polynomials of certain graphs
- scientific article; zbMATH DE number 2130890 (Why is no real title available?)
- scientific article; zbMATH DE number 1195749 (Why is no real title available?)
- Polynomial invariants for cactuses
This page was built for publication: Generalized permanental polynomials of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2311039)
