Constructing non-isomorphic signless Laplacian cospectral graphs

DOI10.1016/J.DISC.2019.111783MaRDI QIDQ2297737zbMATH OpenOpenAlexWikidataFDO

Authors Supriyo Dutta

Publication date 20 February 2020

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

graph isomorphism problemnon-isomorphic cospectral graphspartial transposesignless-Laplacian matrix

Mathematics Subject Classification ID

Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.) (05C60)

Abstract: In this article, we generate large families of non-isomorphic and signless Lalacian cospectral graphs using partial transpose on graphs. Our constructions are significantly powerful. More than $70\mathrm{\%}$ of non-isomorphic signless-Laplacian cospectral graphs can be generated with partial transpose when number of vertices is $le8$. We have also produced numerous examples of non-isomorphic signless Laplacian cospectral graphs.

Recommendations

• Construction of cospectral graphs
• On adjacency and Laplacian cospectral non-isomorphic signed graphs
• Exponentially many graphs have a \(Q\)-cospectral mate
• A construction of cospectral graphs for the normalized Laplacian
• On the construction of cospectral graphs for the adjacency and the normalized Laplacian matrices

Cites work

• Combinatorial laplacians and positivity under partial transpose
• Conditions for separability in generalized Laplacian matrices and diagonally dominant matrices as density matrices
• Constructing cospectral graphs
• Exponentially many graphs have a \(Q\)-cospectral mate
• Graph isomorphism in quasipolynomial time (extended abstract)
• scientific article; zbMATH DE number 3482386 (Why is no real title available?)
• Separability criterion and inseparable mixed states with positive partial transposition.
• Separability Criterion for Density Matrices
• Signless Laplacians of finite graphs
• Spektren endlicher Grafen
• Towards a spectral theory of graphs based on the signless Laplacian. I
• Which graphs are determined by their spectrum?

Cited in

(9)

• Permutation symmetric hypergraph states and multipartite quantum entanglement
• Connected \(Q\)-integral graphs with maximum edge-degree less than or equal to 8
• Non-isomorphic graphs with cospectral symmetric powers
• \(A_\alpha\) spectra of graphs obtained by two corona operations and \(A_\alpha\) cospectral graphs
• On adjacency and Laplacian cospectral non-isomorphic signed graphs
• Construction of cospectral graphs, signed graphs and \(\mathbb{T}\)-gain graphs via partial transpose
• Constructing cospectral graphs via exotic graph products
• Cospectral graphs obtained by edge deletion
• Graphs of order n with exactly n+1 complementarity eigenvalues

Describes a project that uses

Uses Software

• SciPy
• NetworkX

This page was built for publication: Constructing non-isomorphic signless Laplacian cospectral graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2297737)