Geodesic
Per-Spectral Characterizations Of Some Bipartite Graphs
Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 935-951.

Voir la notice de l'article provenant de la source Library of Science

A graph is said to be characterized by its permanental spectrum if there is no other non-isomorphic graph with the same permanental spectrum. In this paper, we investigate when a complete bipartite graph Kp,p with some edges deleted is determined by its permanental spectrum. We first prove that a graph obtained from Kp,p by deleting all edges of a star K1,l, provided l lt; p, is determined by its permanental spectrum. Furthermore, we show that all graphs with a perfect matching obtained from Kp,p by removing five or fewer edges are determined by their permanental spectra.
Keywords: permanent, permanental polynomial, per-spectrum, cospectral 
@article{DMGT_2017_37_4_a5,
     author = {Wu, Tingzeng and Zhang, Heping},
     title = {Per-Spectral {Characterizations} {Of} {Some} {Bipartite} {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {935--951},
     publisher = {mathdoc},
     volume = {37},
     number = {4},
     year = {2017},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a5/}
}
TY  - JOUR
AU  - Wu, Tingzeng
AU  - Zhang, Heping
TI  - Per-Spectral Characterizations Of Some Bipartite Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2017
SP  - 935
EP  - 951
VL  - 37
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a5/
LA  - en
ID  - DMGT_2017_37_4_a5
ER  - 
%0 Journal Article
%A Wu, Tingzeng
%A Zhang, Heping
%T Per-Spectral Characterizations Of Some Bipartite Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2017
%P 935-951
%V 37
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a5/
%G en
%F DMGT_2017_37_4_a5
Wu, Tingzeng; Zhang, Heping. Per-Spectral Characterizations Of Some Bipartite Graphs. Discussiones Mathematicae. Graph Theory, Tome 37 (2017) no. 4, pp. 935-951. http://geodesic.mathdoc.fr/item/DMGT_2017_37_4_a5/

[1] F. Belardo, V. De Filippis and S.K. Simić, Computing the permanental polynomial of a matrix from a combinatorial viewpoint, MATCH Commun. Math. Comput. Chem. 66 (2011) 381-396.

[2] M. Borowiecki and T. Jóźwiak, A note on characteristic and permanental polyno- mials of multigraphs, in: Proc. Graph Theory ( Lag´ow 1981) M. Borowiecki, J.W. Kennedy and M.M. Sys lo (Eds.), Springer-Verlag, Berlin (1983) 75-78.

[3] M. Borowiecki and T. Jóźwiak, Computing the permanental polynomial of a multi- graph, Discuss. Math. 5 (1982) 9-16.

[4] M. Borowiecki, On spectrum and per-spectrum of graphs, Publ. Inst. Math. (Beograd) 38 (1985) 31-33.

[5] G.G. Cash, The permanental polynomial, J. Chem. Inf. Comput. Sci. 40 (2000) 1203-1206. doi: 10.1021/ci000031d

[6] G.G. Cash, Permanental polynomials of smaller fullerenes, J. Chem. Inf. Comput. Sci. 40 (2000) 1207-1209. doi: 10.1021/ci0000326

[7] R. Chen, A note on the relations between the permanental and characteristic poly- nomials of coronoid hydrocarbons, MATCH Commun. Math. Comput. Chem. 51 (2004) 137-148.

[8] Q. Chou, H. Liang and F. Bai, Computing the permanental polynomial of the high level fullerene C70 with high precision, MATCH Commun. Math. Comput. Chem. 73 (2015) 327-336.

[9] E.R. van Dam and W.H. Haemers, Which graphs are determined by their spectrum?, Linear Algebra Appl. 373 (2003) 241-272. doi: 10.1016/S0024-3795(03)00483-X

[10] E.R. van Dam and W.H. Haemers, Developments on spectral characterizations of graphs, Discrete Math. 309 (2009) 576-586. doi: 10.1016/j.disc.2008.08.019

[11] E.J. Farrell, J.M. Guo and G.M. Constantine, On matching coefficients, Discrete Math. 89 (1991) 203-210. doi: 10.1016/0012-365X(91)90369-D

[12] I. Gutman and G.G. Cash, Relations between the permanental and characteristic polynomials of fullerenes and benzenoid hydrocarbons, MATCH Commun. Math. Comput. Chem. 45 (2002) 55-70.

[13] F. Harary, C. King, A. Mowshowitz and R.C. Read, Cospectral graphs and digraphs, Bull. Lond. Math. Soc. 3 (1971) 321-328. doi: 10.1112/blms/3.3.321

[14] D. Kasum, N. Trinajstić and I. Gutman, Chemical graph theory III. On permanental polynomial, Croat. Chem. Acta. 54 (1981) 321-328.

[15] S. Liu and H. Zhang, On the characterizing properties of the permanental polyno- mials of graphs, Linear Algebra Appl. 438 (2013) 157-172. doi: 10.1016/j.laa.2012.08.026

[16] S. Liu and H. Zhang, Characterizing properties of permanental polynomials of lol- lipop graphs, Linear Multilinear Algebra 62 (2014) 419-444. doi: 10.1080/03081087.2013.779271

[17] L. Lovasz, Combinatorial Problems and Exercises, 2nd Edition (Budapest, Akadé- miai Kiad´o, 1993).

[18] R. Merris, K.R. Rebman and W. Watkins, Permanental polynomials of graphs, Linear Algebra Appl. 38 (1981) 273-288. doi: 10.1016/0024-3795(81)90026-4

[19] L.G. Valiant, The complexity of computing the permanent, Theoret. Comput. Sci. 8 (1979) 189-201. doi: 10.1016/0304-3975(79)90044-6

[20] T. Wu and H. Zhang, Per-spectral characterizations of graphs with extremal per- nullity, Linear Algebra Appl. 484 (2015) 13-26. doi: 10.1016/j.laa.2015.06.018

[21] T. Wu and H. Zhang, Some analytical properties of the permanental polynomial of a graph, Ars Combin. CXXIII (2015) 261-267.

[22] T. Wu and H. Zhang, Per-spectral and adjacency spectral characterizations of a complete graph removing six edges, Discrete Applied Math. 203 (2016) 158-176. doi: 10.1016/j.dam.2015.09.014

[23] W. Yan and F. Zhang, On the permanental polynomial of some graphs, J. Math. Chem. 35 (2004) 175-188. doi: 10.1023/B:JOMC.0000033254.54822.f8

[24] H. Zhang and W. Li, Computing the permanental polynomials of bipartite graphs by Pfaffian orientation, Discrete Appl. Math. 160 (2012) 2069-2074. doi: 10.1016/j.dam.2012.04.007

[25] H. Zhang, S. Liu and W. Li, A note on the permanental roots of bipartite graphs, Discuss. Math. Graph Theory 34 (2014) 49-56. doi: 10.7151/dmgt.1704

[26] H. Zhang, T. Wu and H. Lai, Per-spectral characterizations of some edge-deleted subgraphs of a complete graph, Linear Multilinear Algebra 63 (2015) 397-410. doi: 10.1080/03081087.2013.869592