×

Construction of cospectral graphs. (English) Zbl 1447.05121

Summary: Construction of non-isomorphic cospectral graphs is a nontrivial problem in spectral graph theory especially for large graphs. In this paper, we establish that graph theoretical partial transpose of a graph is a potential tool to create non-isomorphic cospectral graphs by considering a graph as a partitioned graph.

MSC:

05C50 Graphs and linear algebra (matrices, eigenvalues, etc.)
05C60 Isomorphism problems in graph theory (reconstruction conjecture, etc.) and homomorphisms (subgraph embedding, etc.)
05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
15A18 Eigenvalues, singular values, and eigenvectors
15A24 Matrix equations and identities

Software:

NetworkX; SciPy
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Cordella, L.P., Foggia, P., Sansone, C., Vento, M.: An improved algorithm for matching large graphs. In: 3rd IAPR-TC15 Workshop on Graph-Based Representations in Pattern Recognition, pp. 149-159 (2001)
[2] Cvetkovic, DM; Doob, M.; Sachs, H., Spectra of Graphs: Theory and Application (1980), New York: Academic Press, New York · Zbl 0458.05042
[3] Cvetkovic, DM; Doob, M.; Gutman, I.; Torgašev, A., Recent results in the theory of graph spectra (1988), Amsterdam: Elsevier, Amsterdam · Zbl 0634.05054
[4] Dutta, S.; Adhikari, B.; Banerjee, S.; Srikanth, R., Bipartite separability and nonlocal quantum operations on graphs, Phys. Rev. A, 94, 012306 (2016)
[5] Dutta, S.; Adhikari, B.; Banerjee, S., Quantum discord of states arising from graphs, Quantum Inf. Process., 16, 8, 183 (2017) · Zbl 1387.81051
[6] Dutta, S.; Adhikari, B.; Banerjee, S., Condition for zero and nonzero discord in graph Laplacian quantum states, Int. J. Quantum Inf., 17, 2, 1950018 (2019) · Zbl 1412.81016
[7] Fujii, H.; Katsuda, A., Isospectral graphs and isoperimetric constants, Discrete Math., 207, 1-3, 33-52 (1999) · Zbl 1131.05309
[8] Garcia, SR; Tener, JE, Unitary equivalence of a matrix to its transpose, J. Operat. Theor., 68, 1, 179-203 (2012) · Zbl 1274.15026
[9] Godsil, CD; McKay, BD, Constructing cospectral graphs, Aequationes Math., 25, 2-3, 257-268 (1982) · Zbl 0527.05051
[10] Haemers, W.H.: Seidel switching and graph energy. Center discussion paper series no. 21012-023 (2012). https://papers.ssrn.com/sol3/papers.cfm?abstract_id=2026916. Accessed 27 Mar 2012 · Zbl 1289.05290
[11] Haemers, WH; Spence, E., Enumeration of cospectral graphs, European J. Combin., 25, 2, 199-211 (2004) · Zbl 1033.05070
[12] Halbeisen, L.; Hungerbühler, N., Generation of isospectral graphs, J. Graph Theory, 31, 3, 255-265 (1999) · Zbl 0932.05053
[13] Harary, F.; King, C.; Mowshowitz, A.; Read, RC, Cospectral graphs and digraphs, Bull. Lond. Math. Soc., 3, 3, 321-328 (1971) · Zbl 0224.05125
[14] Hildebrand, R.; Mancini, S.; Severini, S., Combinatorial laplacians and positivity under partial transpose, Math. Structures Comput. Sci., 18, 1, 205-219 (2008) · Zbl 1138.05047
[15] Horn, RA; Johnson, CR, Matrix Analysis (2012), Cambridge: Cambridge University Press, Cambridge
[16] Horodecki, P., Separability criterion and inseparable mixed states with positive partial transposition, Phys. Lett. A, 232, 5, 333-339 (1997) · Zbl 1053.81504
[17] http://www.openproblemgarden.org
[18] Knuth, DE, Partitioned tensor products and their spectra, J. Algebraic Combin., 6, 3, 259-267 (1997) · Zbl 0882.05090
[19] Peres, A., Separability criterion for density matrices, Phys. Rev. Lett., 77, 8, 1413 (1996) · Zbl 0947.81003
[20] Rowlinson, P., The characteristic polynomials of modified graphs, Discrete Appl. Math., 67, 1-3, 209-219 (1996) · Zbl 0851.05076
[21] Schult, D.A., Swart, P: Exploring network structure, dynamics, and function using NetworkX. In: Proceedings of the 7th Python in Science Conferences (SciPy 2008), vol. 2008, pp. 11-16 (2008)
[22] Schwenk, AJ; Harary, F., Almost all trees are cospectral, New Directions in the Theory of Graphs, 275-307 (1973), New York: Academic Press, New York · Zbl 0261.05102
[23] Schwenk, AJ; Herndon, WC; Ellzey, ML, The construction of cospectral composite graphs, Ann. New York Acad. Sci., 319, 1, 490-496 (1979) · Zbl 0481.05044
[24] Seidel, J.J.: Graphs and two-graphs. In: Proceedings of the Fifth Southeastern Conference on Combinatorics, Graph Theory and Computing (Florida Atlantic University, Boca Raton, FL, 1974). Congressus Numerantium, No. X, pp. 125-143. Utilitas Mathemtica Publ. Inc, Winnipeg (1974) · Zbl 0308.05120
[25] van Dam, ER; Haemers, WH, Which graphs are determined by their spectrum?, Linear Algebra Appl., 373, 241-272 (2003) · Zbl 1026.05079
[26] Wu, CW, Conditions for separability in generalized laplacian matrices and diagonally dominant matrices as density matrices, Phys. Lett. A, 351, 1, 18-22 (2006) · Zbl 1234.81063
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.