On Q-Integral Graphs

Many problems in real life can be transformed into problems in graph theo-ry. In computer science, problems in networks of communication, computational devices, data organization, flow calculation, and so on, can be represented by graphs. Graph theory is not only applied to the study of molecular chemistry and physics, but also widely used in biology and sociology. Because of its wide applications, graph theory has been a branch developing rapidly in applied math-ematics.Let G=(V, E) be an undirected simple graph with n vertices, where V(G)= {u1,u2,…, vn} is the vertex set and E(G)={e1, e2,…, em} is the edge set of G. The adjacency matrix of G is an n × n 0-1 matrix A(G)={aij}, with aij=1 if and only if ui and uj are adjacent. The Laplacian matrix of G is defined to be L(G)=D(G)-A(G), where D(G)=diag(d(v1),d(v2),d(vn)) is the diagonal matrix of vertex degrees, and Q(G)=D(G)+A(G) is the signless Laplacian matrix (Q-matrix) of G. The characteristic polynomial of Q-matrix (Q-polynomial) is denoted by PQ(G, x). G is said to be Q-integral if PQ(G,x) has only integral roots.This thesis is devoted to the hunting of Q-integral graphs. Several classes of graphs are chosen as the targets, their Q-polynomial are computed, and the Q-integrality is analyzed, which leads to the discovery of infinitely many new Q-integral graphs. It consists of the following chapters:In Chapter 1, we first introduce the background of the research, provide necessary terminology, definitions, and symbols. We then present useful compu-tations of eigenvalues and characteristic polynomials of relevant matrices. The current status of the research topic is also outlined at the end of this chapter.Chapter 2 contains the computations and proofs of Q-polynomials of several classes of graphs, which include:the line graph of the subdivision of complete graphs, complete multipartite graphs, joined graphs and Cartesian product of graphs.The main results are given in Chapter 3. It contains a thorough analysis of the Q-integrality of complete 3,4,5-partite graphs. A couple of necessary and sufficient conditions are obtained for a complete partite graph to be Q-integral (t<5). Necessary and sufficient conditions are also established for special joined graphs to be Q-integral, and infinitely many new Q-integral graphs are con-structed by "joining". Lastly, the Q-integrality is verified for the line graph of subdivision of complete graphs and Cartesian product of some graphs.