Showing 1–7 of 7 results for author: Grout, J

Zero forcing for inertia sets

Authors: Steve Butler, Jason Grout, H. Tracy Hall

Abstract: Zero forcing is a combinatorial game played on a graph with a goal of turning all of the vertices of the graph black while having to use as few "unforced" moves as possible. This leads to a parameter known as the zero forcing number which can be used to give an upper bound for the maximum nullity of a matrix associated with the graph. We introduce a new variation on the zero forcing game which c… ▽ More Zero forcing is a combinatorial game played on a graph with a goal of turning all of the vertices of the graph black while having to use as few "unforced" moves as possible. This leads to a parameter known as the zero forcing number which can be used to give an upper bound for the maximum nullity of a matrix associated with the graph. We introduce a new variation on the zero forcing game which can be used to give an upper bound for the maximum nullity of a matrix associated with a graph that has $q$ negative eigenvalues. This gives some limits to the number of positive eigenvalues that such a graph can have and so can be used to form lower bounds for the inertia set of a graph. △ Less

Submitted 19 November, 2012; originally announced November 2012.

Comments: 16 pages, lots of figures

A construction of cospectral graphs for the normalized Laplacian

Authors: Steve Butler, Jason Grout

Abstract: We give a method to construct cospectral graphs for the normalized Laplacian by a local modification in some graphs with special structure. Namely, under some simple assumptions, we can replace a small bipartite graph with a cospectral mate without changing the spectrum of the entire graph. We also consider a related result for swapping out biregular bipartite graphs for the matrix $A+tD$. We pr… ▽ More We give a method to construct cospectral graphs for the normalized Laplacian by a local modification in some graphs with special structure. Namely, under some simple assumptions, we can replace a small bipartite graph with a cospectral mate without changing the spectrum of the entire graph. We also consider a related result for swapping out biregular bipartite graphs for the matrix $A+tD$. We produce (exponentially) large families of non-bipartite, non-regular graphs which are mutually cospectral, and also give an example of a graph which is cospectral with its complement but is not self-complementary. △ Less

Submitted 26 January, 2012; v1 submitted 21 August, 2010; originally announced August 2010.

Comments: 21 pages; lots of figures; includes SAGE code

MSC Class: 05C50

Journal ref: S. Butler and J. Grout, A construction of cospectral graphs for the normalized Laplacian, Electronic Journal of Combinatorics 18 (2011), #231, 20pp

Program for calculating bounds on the minimum rank of a graph using Sage

Authors: Laura DeLoss, Jason Grout, Tracy McKay, Jason Smith, Geoff Tims

Abstract: The minimum rank of a simple graph $G$ is defined to be the smallest possible rank over all symmetric real matrices whose $ij$th entry (for $i\neq j$) is nonzero whenever $\{i,j\}$ is an edge in $G$ and is zero otherwise. Minimum rank is a difficult parameter to compute. However, there are now a number of known reduction techniques and bounds that can be programmed on a computer; we have develop… ▽ More The minimum rank of a simple graph $G$ is defined to be the smallest possible rank over all symmetric real matrices whose $ij$th entry (for $i\neq j$) is nonzero whenever $\{i,j\}$ is an edge in $G$ and is zero otherwise. Minimum rank is a difficult parameter to compute. However, there are now a number of known reduction techniques and bounds that can be programmed on a computer; we have developed a program using the open-source mathematics software Sage to implement several techniques. In this note, we provide the source code for this program. △ Less

Submitted 9 December, 2008; originally announced December 2008.

Comments: 30 pages, 1 Sage program

MSC Class: 05C50; 15A03

Table of minimum ranks of graphs of order at most 7 and selected optimal matrices

Authors: Laura DeLoss, Jason Grout, Leslie Hogben, Tracy McKay, Jason Smith, Geoff Tims

Abstract: The minimum rank of a simple graph $G$ is defined to be the smallest possible rank over all symmetric real matrices whose $ij$th entry (for $i\neq j$) is nonzero whenever $\{i,j\}$ is an edge in $G$ and is zero otherwise. Minimum rank is a difficult parameter to compute. However, there are now a number of known reduction techniques and bounds that can be programmed on a computer; we have develop… ▽ More The minimum rank of a simple graph $G$ is defined to be the smallest possible rank over all symmetric real matrices whose $ij$th entry (for $i\neq j$) is nonzero whenever $\{i,j\}$ is an edge in $G$ and is zero otherwise. Minimum rank is a difficult parameter to compute. However, there are now a number of known reduction techniques and bounds that can be programmed on a computer; we have developed a program using the open-source mathematics software Sage to implement several techniques. We have also established several additional strategies for computation of minimum rank. These techniques have been used to determine the minimum ranks of all graphs of order 7. This paper contains a list of minimum ranks for all graphs of order at most 7. We also present selected optimal matrices. △ Less

Submitted 4 December, 2008; originally announced December 2008.

Comments: 54 pages, 1 spreadsheet, 1 Sage program

MSC Class: 05C50; 15A03

The minimum rank problem over finite fields

Authors: Jason Grout

Abstract: The structure of all graphs having minimum rank at most k over a finite field with q elements is characterized for any possible k and q. A strong connection between this characterization and polarities of projective geometries is explained. Using this connection, a few results in the minimum rank problem are derived by applying some known results from projective geometry. The structure of all graphs having minimum rank at most k over a finite field with q elements is characterized for any possible k and q. A strong connection between this characterization and polarities of projective geometries is explained. Using this connection, a few results in the minimum rank problem are derived by applying some known results from projective geometry. △ Less

Submitted 18 January, 2008; originally announced January 2008.

Comments: 23 pages, 5 figures, 1 Sage program

MSC Class: 05C50; 05C75; 15A03; 05B25; 51E20

Graphs with extremal energy should have a small number of distinct eigenvalues

Authors: Dragos Cvetkovic, Jason Grout

Abstract: The sum of the absolute values of the eigenvalues of a graph is called the energy of the graph. We study the problem of finding graphs with extremal energy within specified classes of graphs. We develop tools for treating such problems and obtain some partial results. Using calculus, we show that an extremal graph ``should'' have a small number of distinct eigenvalues. However, we also present d… ▽ More The sum of the absolute values of the eigenvalues of a graph is called the energy of the graph. We study the problem of finding graphs with extremal energy within specified classes of graphs. We develop tools for treating such problems and obtain some partial results. Using calculus, we show that an extremal graph ``should'' have a small number of distinct eigenvalues. However, we also present data that shows in many cases that extremal graphs can have a large number of distinct eigenvalues. △ Less

Submitted 30 October, 2007; originally announced October 2007.

Comments: 17 pages; contains a SAGE program and minor grammatical corrections that are not contained in the published version

MSC Class: 05C50

Journal ref: Cvetkovi\' c D., Grout J., Maximal energy graphs should have a small number of distinct eigenvalues, Bull. Acad. Serbe Sci. Arts, Cl. Sci. Math. Natur., Sci. Math., 134(2007), No. 32, 43-57

The minimum rank problem over the finite field of order 2: minimum rank 3

Authors: Wayne Barrett, Jason Grout, Raphael Loewy

Abstract: Our 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. We conclude by exploring how some of these results over the finite field of order 2 extend to arbitrary fields and demonstrate that at least one third of the 62 are minimal… ▽ More Our 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. We conclude by exploring how some of these results over the finite field of order 2 extend to arbitrary fields and demonstrate that at least one third of the 62 are minimal forbidden subgraphs over an arbitrary field for the class of graphs having minimum rank at most 3 in that field. △ Less

Submitted 3 September, 2008; v1 submitted 12 December, 2006; originally announced December 2006.

Comments: 40 pages, added Sage program and improvements from referee process

MSC Class: 05C50; 05C75; 15A03