Institution: | San Diego State University |
---|---|
Department: | |
Year: | 2015 |
Record ID: | 2060561 |
Full text PDF: | http://hdl.handle.net/10211.3/134852 |
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 v = v??? ??? v??? ??? ..., ??? vn > 0 be the Perron vector of A. We formulate a parameter r (G ) = v1 [over] vn 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 ) ??? the square root of ( d1 [over] dn and r ( G ) ??? the square root of (n - 1) where d??? , d??? , ....., d n 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..