Jump to navigation

Graph Eigenvectors

Varma, Ratna Haritha

Interlando, CarmeloHui, StefenRoot, William

2014-10-29

Fall 2014

Thesis

48 pages

This thesis concerns Perron vectors of the adjacency matrices of simple connected graphs on n vertices. Perron's 1907 theorem provides the insight into the eigensystems of entrywise positive matrices. This result was extended to nonnegative irreducible matrices by Frobenius. In our context the nonnegative irreducible matrix is A, the adjacency matrix of a simple connected graph G on n vertices. Let _ = __ _ __ _ ..., _ _n > 0 be the Perron vector of A. We formulate a parameter r(G) = __/_n as a measure of the regularity of G. We note that r(G) _ 1 and r(G) = 1 iff G is a regular graph. We make two conjectures concerning the upper bounds for r(G) as r(G) ≤ √(d_/dn) and r(G)≤ √(n_1) where d_, d_, ....., dn is the decreasing sequence of the degrees of graph G. The degree of a vertex of a graph is the number of edges incident to the vertex. To verify our conjectures, we draw simple connected graphs for two or more vertices. We write a basic program in MATLAB to calculate the eigenvalues and eigenvectors of the adjacency matrix A(G). For n = 2, 3 the conjectures are true, but for graphs with four or more vertices the conjecture fails. Hence, for n = 4 we have six simple connected graphs where both the conjectures are good for four out of six graphs.

English

Applied Mathematics

Mathematics and Statistics

Sciences

Master of Science (M.S.) San Diego State University, 2014

QA2.2

http://hdl.handle.net/20.500.11929/sdsu:2688