The Combinatorial Structure Of The Eigenvectors Of Graphs

Finite or at most countable objects can be represented as a graph model if there exist relation between them. Graph theory mainly studies the nature of the internal structure of such a model and express using graph parameters. However, the computational complexity of some parameters for which have broad application prospects is NPH or NPC problem. Henceforth, the method of algebraic combinatorial analysis plays an important role on the reasch of the structural properties of a graph. Spectral graph theory describe its own structural parameters in terms of the spectrum and the eigenspace of the matrix corresponding to a graph, which reflects the view of the representation theory of modern mathematics. In this thesis, we mainly study the combinatorial structural properties of the eigenvectors corresponding to nonzero eigenvalues of the matrices of a graph, and extend those results to the general eigenvectors. In addition, the combinatorial structural properties of the eigenvectors will be applied on the graph partitioning problem.The extreme eigenvalues, such as the spectral radius and the least nonzero eigenvalue, play an important role on the characterization of the graph parameters. Simultaneously, the eigenvectors corresponding to those extreme eigenvalues are also important to discuss the global structural properties of a graph. In 1975, Fiedler gives the combinatorial struc-tural properties of the eigenvectors (known as Fiedler vector) corresponding to the least nonzero eigenvalues(known as algebraic connectivity) of the Laplacian matrix of a graph. The structural property of a graph can be looked into the diversification of the signs and the values of its Fiedler vectors. Based on the changing of the signs of the Fiedler vec-tors, Merris introduce the concept the characteristic set in 1987(its elememts are called the characteristic elememts), and show that, for any tree, its characteristic set contains exactly one characteristic element, and such a characteristic element is fixed, regardless the chose of the Fiedler vectors. In 1998, Bapat and Pati extend the characteristic set to a general graph and give a upper bound on the cardinality of the characteristic set. In par-ticular, they also characterize the structural property of the Fiedler vectors of an unicyclic graph. In 2002, Pati extends the characteristic set to the eigenvectors corresponding to the third least eigenvalue of the Laplacian matrix of a graph. However, those eigenvectors of a tree no longer have the nature as that of its Fiedler vector, i.e., both the characteristic set and its cardinality are related on the chose of its eigenvectors.For a graph G on n vertices, suppose its Laplacian eigenvalues are arranged as follows: Denote by C(G, Y) the characteristic set with respect to the eigenvector Y of G. For convenience, we call eigenvector Y is aκ-vector of G if the eigenvalueλκ(G) associated by Y satisfyingλκ(G)>λκ-1(G). Obviously, each Fiedler vector is a 2-vector. Fiedler show that, for a tree T,|C(T, Y)|=κ-1 if each entry of the eigenvector Y corresponding toλκ(T) is different to zero. Note that such an eigenvector Y is aκ-vector. In fact, with respect to anyκ-vector Y of a tree T, we have 1≤|C(T, Y)|≤κ-1.Studying the invariance of the characteristic set and its cardinality is one of the main work of this thesis. For a given integerκ, whether there exists a tree T such that |C(T, Y)|= 1 with respect to its anyκ-vector Y? Such a tree is called aκ-simple tree. Our answer is positive and an equivalent condition forκ-simple trees is also expored. At the same time, we find that, for anyκ-simple tree T, C(T, Y) is fixed, which is consistent to the property of that of its Fiedler vector, since each tree is 2-simple.Another main work of this thesis is investigation the maximality of the cardinality of the characteristic set. For a given tree, the characteristic set with respect to differentκ-vectors may change. However, whether the characteristic set would be change? If we only consider theκ-vectors for which maximizes the the cardinality of the characteristic set. The vector mentioned above is called theκ-maximal vector. We show that the characteristic set with respect to eachκ-vector is contained in the characteristic set with respect to anyκ-maximal vector. Hence, the characteristic set with respect to any k-maximal vector is fixed, which is consistent to the property of that of its Fiedler vector, since each Fiedler vector is a 2-maximal vector.In our real life, there are many application backgrounds on the mixed graph, for which is obtained from a simple graph by oriented some of its edges. In 1999, Bapat et.al. introduce the Laplacian matrix of a mixed graph and generalize the classical Matrix-Tree Theorem. In 2002, X. D. Zhang and J. S. Li study the spectrum of a mixed graph and give a upper bound on its spectral radius. In 2005, taking into account the Laplace spectrum of singular mixed graph is essentially equivalent to the classical Laplace spectrum, Y. Z. Fan discuss the least eigenvector of nonsingular mixed graphs and characterize the com-binatorial structural properties of the eigenvectors corresponding to this eigenvalue. In addition, an open problem is posed in that paper, i.e., how to characterize the nonsingu-lar unicyclic mixed graph(s) which minimizes the least eigenvalue among all nonsingular unicyclic mixed graphs with fixed order and girth.This thesis focuses on this question. We extend the characteristic set to the eigenvec-tor corresponding to the least eigenvalue of the Laplacian matrix of a mixed graph. We give the possible cardinality of the characteristic set and characterize its characteristic el-ements. Applying those properties, we obtained the change of the signs of this eigenvector and resolve this open problem finally.In the last section, we apply the structural property of theκ-vectors on graph par-tition problem. The main goal of graph partition is to decompose a graph into several subgraphs and is subject to a balance constraint minizing the price or weight among them. It is widely used on the image segmentation and clustering. Based on the classical max-imum flow-minimum cut theorem, decomposition a graph into two subgraphs (i.e., two partition) can be accomplished. In 1992, considering the size of the balance decomposition, Hagen and Kahng propose the ratio cut criteria and introduce a graph partition method based on the structural property of Fiedler vectors. Forκ-partition problem, Chan, Schlag and Zien generalize the ratio cut criteria in 1994 and decompose a graph based on the first k eigenvectors of the Laplacian matrix of a graph. In addition, Shi and Malik propose the normal cut criteria in 2000, and decompose a graph based on the eigenvectorcorrespond-ing to least nonzero eigenvalue of the normal Laplacian matrix of a graph. based on the property of the change of the signs ofκ-vector, we propose a newκ-parpition method. Compared with Fiedler vector can only achieve two partition,κ-vector can accomplishκ-partition. Compared with Chan-Schlag-Zien method, our method can save computation. Experiment also reflects that our method has a good effect.