Open Access. Powered by Scholars. Published by Universities.®
Articles 1 - 6 of 6
Full-Text Articles in Entire DC Network
Counting Threshold Graphs And Finding Inertia Sets, Christopher Abraham Guzman
Counting Threshold Graphs And Finding Inertia Sets, Christopher Abraham Guzman
Theses and Dissertations
This thesis is separated into two parts: threshold graphs and inertia sets. First we present an algorithmic approach to finding the minimum rank of threshold graphs and then progress to counting the number of threshold graphs with a specific minimum rank. Second, we find an algorithmic and more automated way of determining the inertia set of graphs with seven or fewer vertices using theorems and lemmata found in previous papers. Inertia sets are a relaxation of the inverse eigenvalue problem. Instead of determining all the possible eigenvalues that can be obtained by matrices with a specific zero/nonzero pattern we restrict …
Minimum Rank Problems For Cographs, Nicole Andrea Malloy
Minimum Rank Problems For Cographs, Nicole Andrea Malloy
Theses and Dissertations
Let G be a simple graph on n vertices, and let S(G) be the class of all real-valued symmetric nxn matrices whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. The smallest rank achieved by a matrix in S(G) is called the minimum rank of G, denoted mr(G). The maximum nullity achieved by a matrix in S(G) is denoted M(G). For each graph G, there is an associated minimum rank class, MR(G) consisting of all matrices A in S(G) with rank A = mr(G). Although no restrictions are applied to the diagonal entries of …
The Minimum Rank Problem For Outerplanar Graphs, John Henry Sinkovic
The Minimum Rank Problem For Outerplanar Graphs, John Henry Sinkovic
Theses and Dissertations
Given a simple graph G with vertex set V(G)={1,2,...,n} define S(G) to be the set of all real symmetric matrices A such that for all i not equal to j, the ijth entry of A is nonzero if and only if ij is in E(G). The range of the ranks of matrices in S(G) is of interest and can be determined by finding the minimum rank. The minimum rank of a graph, denoted mr(G), is the minimum rank achieved by a matrix in S(G). The maximum nullity of a graph, denoted M(G), is the maximum nullity achieved by a matrix …
The Minimum Rank, Inverse Inertia, And Inverse Eigenvalue Problems For Graphs, Mark Condie Kempton
The Minimum Rank, Inverse Inertia, And Inverse Eigenvalue Problems For Graphs, Mark Condie Kempton
Theses and Dissertations
For a graph G we define S(G) to be the set of all real symmetric n by n matrices whose off-diagonal zero/nonzero pattern is described by G. We show how to compute the minimum rank of all matrices in S(G) for a class of graphs called outerplanar graphs. In addition, we obtain results on the possible eigenvalues and possible inertias of matrices in S(G) for certain classes of graph G. We also obtain results concerning the relationship between two graph parameters, the zero forcing number and the path cover number, related to the minimum rank problem.
Properties Of The Zero Forcing Number, Kayla Denise Owens
Properties Of The Zero Forcing Number, Kayla Denise Owens
Theses and Dissertations
The zero forcing number is a graph parameter first introduced as a tool for solving the minimum rank problem, which is: Given a simple, undirected graph G, and a field F, let S(F,G) denote the set of all symmetric matrices A=[a_{ij}] with entries in F such that a_{ij} doess not equal 0 if and only if ij is an edge in G. Find the minimum possible rank of a matrix in S(F,G). It is known that the zero forcing number Z(G) provides an upper bound for the maximum nullity of a graph. I investigate properties of the zero forcing number, …
The Minimum Rank Problem Over Finite Fields, Jason Nicholas Grout
The Minimum Rank Problem Over Finite Fields, Jason Nicholas Grout
Theses and Dissertations
We have two main results. Our first main result is a sharp bound for the number of vertices in a minimal forbidden subgraph for the graphs having minimum rank at most 3 over the finite field of order 2. We also list all 62 such minimal forbidden subgraphs and show that many of these are minimal forbidden subgraphs for any field. Our second main result is a structural characterization of all graphs having minimum rank at most k for any k over any finite field. This characterization leads to a very strong connection to projective geometry and we apply projective …