AKCE International Journal of Graphs and Combinatorics (Jan 2023)
A study on determination of some graphs by Laplacian and signless Laplacian permanental polynomials
Abstract
AbstractThe permanent of an n × n matrix [Formula: see text] is defined as [Formula: see text] where the sum is taken over all permutations σ of [Formula: see text] The permanental polynomial of M, denoted by [Formula: see text] is [Formula: see text] where In is the identity matrix of order n. Let G be a simple undirected graph on n vertices and its Laplacian and signless Laplacian matrices be L(G) and Q(G) respectively. The permanental polynomials [Formula: see text] and [Formula: see text] are called the Laplacian permanental polynomial and signless Laplacian permanental polynomial of G respectively. A graph G is said to be determined by its (signless) Laplacian permanental polynomial if all the graphs having the same (signless) Laplacian permanental polynomial with G are isomorphic to G. A graph G is said to be combinedly determined by its Laplacian and signless Laplacian permanental polynomials if all the graphs having (i) the same Laplacian permanental polynomial as [Formula: see text] and (ii) the same signless Laplacian permanental polynomial as [Formula: see text] are isomorphic to G. In this article we investigate the determination of some graphs, namely, star, wheel, friendship graphs and a particular kind of caterpillar graph [Formula: see text] (whose all r non-pendant vertices have the same degree n) by their Laplacian and signless Laplacian permanental polynomials. We show that a kind of caterpillar graphs [Formula: see text] (for [Formula: see text]), wheel graph (up to 7 vertices) and friendship graph (up to 7 vertices) are determined by their (signless) Laplacian permanental polynomials. Further we prove that all friendship graphs and wheel graphs are combinedly determined by their Laplacian and signless Laplacian permanental polynomials.
Keywords
