Studies On Permanental Spectral Characterization Problems Of Graphs

The permanental polynomial of graph G was introduced in mathematics and chemistry almost simultaneously by Merris et al. and Kasum et al., respectively, which is defined by computing the permanent of matrix xI - A(G), where I and A(G) are the identity matrix and adjacency matrix of G, respectively. However, Valiant proved that computing the permanent of a matrix is #P-complete.Characterizing kinds of graphs which are uniquely determined by their spectra is a classical problem in the theory of graph spectra, van Dam and Haemers systemati-cally studied the problem, and they conjectured that almost all graphs are determined by their adjacency spectra. The permanental spectrum (per-spectrum for short) of a graph is the multiset of all roots (together with their multiplicities) of the permanen-tal polynomial of the graph. Merris et al. first proposed per-spectral characterization problem of graphs, i.e., which graphs are determined by their per-spectra? A graph G is said to be determined by its per-spectrum (DPS for short) if there is no non-isomorphic graph H with the same per-spectrum as G. And they formulated that the per-spectrum seems a little better than the adjacency spectrum when it comes to distinguish graphs which are not trees. Recently, Liu and Zhang investigated some graphs which are DPS, and they showed that star, complete graph, regular complete bipartite graph and odd cycle are DPS. They pointed out that graph determined by the adjacency spectrum is not necessarily determined by the per-spectrum. Two graphs are per-cospectral if they share the same per-spectrum. Borowiecki and Jozwiak first considered to construct per-cospectral graphs, and they investigated which graph pairs are per-cospectral and adjacency cospectral simultaneously.In this thesis, we systematically study the problems of per-spectral characteriza-tions of graphs. We show that a complete graph with some edges deleted is DPS. In particular, we propose the per-nullity of graphs, i.e., the multiplicity of the number zero in per-spectrum. Using the per-nullity, we show that graphs with extremal per-nullity are DPS. And we also show that the complete bipartite graphs are determined by their per-spectra. Furthermore, by the relation between per-nullity and matching number of graphs, we also prove that a balanced complete bipartite graph with some edges deleted is DPS. Finally, we give some methods to construct graph pairs which are per-cospectral and adjacency cospectral simultaneously.In Chapter 1, we introduce the research backgrounds of permanental polynomials of graphs, and we also summarize some research progress of the per-spectra and permanental polynomials of graphs in this thesis.In Chapter 2, motivated by Merris et al.’s statement, we investigate when a complete graph with some edges removed is DPS. Precisely, we show that all graphs obtained from a complete graph by removing at most five edges are DPS. However, Camara and Haemers’ results show that there is exactly one pair of graphs in these graphs that are not determined by their adjacency spectra. Furthermore, we obtain that if we delete edges form a star, a matching, or the disjoint union of a matching and a path P3 in a complete graph, then the resulting graphs are DPS.In Chapter 3, we show that all graphs obtained by removing six edges from a complete graph are DPS, and we also consider the adjacency spectral characterization problem of such graphs. We find a relation between closed walks of length 4 and fourth coefficient of permanental polynomial of a graph. Using the relation, we expand Camara and Haemers’. Precisely, we prove that there exist exactly two pairs of adjacency cospectral graphs in all such graphs, which are K5-E(K4) and K5-E(B), and Kn-E(C6) and Kn-E(T2,2,2), respectively, where B is a bowtie graph, and n> 7.In Chapter 4, we introduce the per-nullity of graphs, and give some basic prop-erties of the per-nullity. Then, we determine all graphs of order n whose per-nullities are n - 2, n - 3, n - 4 and n - 5, respectively. These graphs belong to the class of graphs with three, four, five or six distinct permanental roots. We show that the graphs of order n with the per-nullity n-2, n - 3, or n-5, and all non-bipartite graphs of order n with the per-nullity n - 4 are DPS. In particular, using per-nullity of graphs, we prove that the complete bipartite graphs are DPS.In Chapter 5, by the relation of per-nullity and matching number of graphs, we prove that a graph obtained from a balanced complete bipartite graph Kp,p by deleting all edges of a star K1,l provided l< p is DPS. And we show that all graphs with the matching number p obtained from Kp,p by removing five or fewer edges are DPS.In the last chapter, we discuss which graph pairs are not only per-cospectral but also adjacency cospectral. We give a construction method to get infinite pairs of forests which are such graphs. Additionally, using the coalescence operation of graphs, we can construct infinite pairs of graphs which are per-cospectral and adjacency cospectral. Finally, we show that the derivative of permanental polynomial of G is expressed as the sum of permanental polynomials of all vertex-deleted subgraphs of G. Furthermore, we discuss and answer permanental polynomial version of Gutman’s problem and give a solution.