Open Access. Powered by Scholars. Published by Universities.®
- Publication Type
Articles 1 - 9 of 9
Full-Text Articles in Mathematics
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, …
Sign Pattern Matrices That Require Almost Unique Rank, Assefa D. Merid
Sign Pattern Matrices That Require Almost Unique Rank, Assefa D. Merid
Mathematics Theses
A sign pattern matrix is a matrix whose entries are from the set {+,-, 0}. For a real matrix B, sgn(B) is the sign pattern matrix obtained by replacing each positive respectively, negative, zero) entry of B by + (respectively, -, 0). For a sign pattern matrixA, the sign pattern class of A, denoted Q(A), is defined as { B : sgn(B)= A }. The minimum rank mr(A)(maximum rank MR(A)) of a sign pattern matrix A is the minimum (maximum) of the ranks of the real matrices in Q(A). Several results concerning sign patterns A that require almost …
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 …
Rational Realizations Of The Minimum Rank Of A Sign Pattern Matrix, Selcuk Koyuncu
Rational Realizations Of The Minimum Rank Of A Sign Pattern Matrix, Selcuk Koyuncu
Mathematics Theses
A sign pattern matrix is a matrix whose entries are from the set {+,-,0}. The minimum rank of a sign pattern matrix A is the minimum of the rank of the real matrices whose entries have signs equal to the corresponding entries of A. It is conjectured that the minimum rank of every sign pattern matrix can be realized by a rational matrix. The equivalence of this conjecture to several seemingly unrelated statements are established. For some special cases, such as when A is entrywise nonzero, or the minimum rank of A is at most 2, or the minimum rank …
Graphs Whose Minimal Rank Is Two: The Finite Fields Case, Wayne Barrett, Hein Van Der Holst, Raphael Loewy
Graphs Whose Minimal Rank Is Two: The Finite Fields Case, Wayne Barrett, Hein Van Der Holst, Raphael Loewy
Faculty Publications
Let F be a finite field, G = (V,E) be an undirected graph on n vertices, and let S(F,G) be the set of all symmetric n × n matrices over F whose nonzero off-diagonal entries occur in exactly the positions corresponding to the edges of G. Let mr(F,G) be the minimum rank of all matrices in S(F,G). If F is a finite field with p^t elements, p does not = 2, it is shown that mr(F,G) ≤ 2 if and only if the complement of G is the join of a complete graph with either the union of at most …