Computation Of Minimal Rank And Path Cover Number For Certain Graphs, 2017 University of Regina

#### Computation Of Minimal Rank And Path Cover Number For Certain Graphs, Francesco Barioli, Shaun Fallat, Leslie Hogben

*Leslie Hogben*

For a given undirected graph G, the minimum rank of G is defined to be the smallest possible rank over all real symmetric matrices A whose (i, j)th entry is non-zero whenever i ≠ j and {i, j} is an edge in G. The path cover number of G is the minimum number of vertex-disjoint paths occurring as induced subgraphs of G that cover all the vertices of G. For trees, the relationship between minimum rank and path cover number is completely understood. However, for non-trees only sporadic results are known. We derive formulae for the minimum rank and path ...

Matrix Completion Problems For Pairs Of Related Classes Of Matrices, 2017 Iowa State University

#### Matrix Completion Problems For Pairs Of Related Classes Of Matrices, Leslie Hogben

*Leslie Hogben*

For a class X of real matrices, a list of positions in an n×n matrix (a pattern) is said to have X-completion if every partial X-matrix that specifies exactly these positions can be completed to an X-matrix. If X and X0 are classes that satisfy the conditions any partial X-matrix is a partial X0-matrix, for any X0-matrix A and ε>0, A+εI is a X-matrix, and for any partial X-matrix A, there exists δ>0 such that A−δĨ is a partial X-matrix (where Ĩ is the partial identity matrix specifying the same pattern as A) then any ...

Parameters Related To Tree-Width, Zero Forcing, And Maximum Nullity Of A Graph, 2017 University of Tennessee, Chattanooga

#### Parameters Related To Tree-Width, Zero Forcing, And Maximum Nullity Of A Graph, Francesco Barioli, Wayne Barrett, Shaun M. Fallat, Leslie Hogben, Bryan Shader, P. Van Den Driessche, Hein Van Der Holst

*Leslie Hogben*

Tree-width, and variants that restrict the allowable tree decompositions, play an important role in the study of graph algorithms and have application to computer science. The zero forcing number is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by a graph. We establish relationships between these parameters, including several Colin de Verdière type parameters, and introduce numerous variations, including the minor monotone floors and ceilings of some of these parameters. This leads to new graph parameters and to new characterizations of existing graph parameters. In particular, tree-width, largeur d'arborescence, path-width, and proper ...

Techniques For Determining The Minimum Rank Of A Small Graph, 2017 Iowa State University

#### Techniques For Determining The Minimum Rank Of A Small Graph, Laura Deloss, Jason Grout, Leslie Hogben, Tracy Mckay, Jason Smith, Geoff Tims

*Leslie Hogben*

The minimum rank of a simple graph G is defined to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i≠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 ...

Zero Forcing Parameters And Minimum Rank Problems, 2017 University of Tennessee, Chattanooga

#### Zero Forcing Parameters And Minimum Rank Problems, Francesco Barioli, Wayne Barrett, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Bryan Shader, P. Van Den Driessche, Hein Van Der Holst

*Leslie Hogben*

The zero forcing number Z(G), which is the minimum number of vertices in a zero forcing set of a graph G, is used to study the maximum nullity/minimum rank of the family of symmetric matrices described by G. It is shown that for a connected graph of order at least two, no vertex is in every zero forcing set. The positive semidefinite zero forcing number Z+(G) is introduced, and shown to be equal to |G|-OS(G), where OS(G) is the recently defined ordered set number that is a lower bound for minimum positive semidefinite rank ...

Propagation Time For Zero Forcing On A Graph, 2017 Iowa State University

#### Propagation Time For Zero Forcing On A Graph, Leslie Hogben, My Huynh, Nicole Kingsley, Sarah Meyer, Shanise Walker, Michael Young

*Leslie Hogben*

Zero forcing (also called graph infection) on a simple, undirected graph G is based on the color-change rule: if each vertex of G is colored either white or black, and vertex v is a black vertex with only one white neighbor w, then change the color of w to black. A minimum zero forcing set is a set of black vertices of minimum cardinality that can color the entire graph black using the color change rule. The propagation time of a zero forcing set B of graph G is the minimum number of steps that it takes to force all ...

Zero Forcing, Linear And Quantum Controllability For Systems Evolving On Networks, 2017 Aberystwyth University

#### Zero Forcing, Linear And Quantum Controllability For Systems Evolving On Networks, Daniel Burgarth, Domenico D'Alessandro, Leslie Hogben, Simone Severini, Michael Young

*Leslie Hogben*

We study the dynamics of systems on networks from a linear algebraic perspective. The control theoretic concept of controllability describes the set of states that can be reached for these systems. Our main result says that controllability in the quantum sense, expressed by the Lie algebra rank condition, and controllability in the sense of linear systems, expressed by the controllability matrix rank condition, are equivalent conditions. We also investigate how the graph theoretic concept of a zero forcing set impacts the controllability property; if a set of vertices is a zero forcing set, the associated dynamical system is controllable. These ...

Positive Semidefinite Zero Forcing, 2017 Iowa State University

#### Positive Semidefinite Zero Forcing, Jason Ekstrand, Craig Erickson, H. Tracy Hall, Diana Hay, Leslie Hogben, Ryan Johnson, Nicole Kingsley, Steven Osborne, Travis Peters, Jolie Roat, Arianne Ross, Darren D. Row, Nathan Warnberg, Michael Young

*Leslie Hogben*

The positive semidefinite zero forcing number Z+(G) of a graph G was introduced in [4]. We establish a variety of properties of Z+(G): Any vertex of G can be in a minimum positive semidefinite zero forcing set (this is not true for standard zero forcing). The graph parameters tw(G) (tree-width), Z+(G), and Z(G) (standard zero forcing number) all satisfy the Graph Complement Conjecture (see [3]). Graphs having extreme values of the positive semidefinite zero forcing number are characterized. The effect of various graph operations on positive semidefinite zero forcing number and connections with other graph ...

A Linear Algebraic View Of Partition Regular Matrices, 2017 Iowa State University

#### A Linear Algebraic View Of Partition Regular Matrices, Leslie Hogben, Jillian Mcleod

*Leslie Hogben*

Rado showed that a rational matrix is partition regular over N if and only if it satisfies the columns condition. We investigate linear algebraic properties of the columns condition, especially for oriented (vertex-arc) incidence matrices of directed graphs and for sign pattern matrices. It is established that the oriented incidence matrix of a directed graph Γ has the columns condition if and only if Γ is strongly connected, and in this case an algorithm is presented to find a partition of the columns of the oriented incidence matrix with the maximum number of cells. It is shown that a sign ...

On The Graph Complement Conjecture For Minimum Rank, 2017 University of Tennessee, Chattanooga

#### On The Graph Complement Conjecture For Minimum Rank, Francesco Barioli, Wayne Barrett, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Hein Van Der Holst

*Leslie Hogben*

The minimum rank of a graph has been an interesting and well studied parameter investigated by many researchers over the past decade or so. One of the many unresolved questions on this topic is the so-called graph complement conjecture, which grew out of a workshop in 2006. This conjecture asks for an upper bound on the sum of the minimum rank of a graph and the minimum rank of its complement, and may be classified as a Nordhaus–Gaddum type problem involving the graph parameter minimum rank. The conjectured bound is the order of the graph plus two. Other variants ...

Note On Von Neumann And Rényi Entropies Of A Graph, 2017 Iowa State University

#### Note On Von Neumann And Rényi Entropies Of A Graph, Michael Dairyko, Leslie Hogben, Jephian C.H. Lin, Joshua Lockhart, David Roberson, Simone Severini, Michael Young

*Leslie Hogben*

We conjecture that all connected graphs of order n have von Neumann entropy at least as great as the star K1;n1 and prove this for almost all graphs of order n. We show that connected graphs of order n have Renyi 2-entropy at least as great as K1;n1 and for > 1, Kn maximizes Renyi -entropy over graphs of order n. We show that adding an edge to a graph can lower its von Neumann entropy.

Expected Values Of Parameters Associated With The Minimum Rank Of A Graph, 2017 Brigham Young University

#### Expected Values Of Parameters Associated With The Minimum Rank Of A Graph, H. Tracy Hall, Leslie Hogben, Ryan R. Martin, Bryan Shader

*Leslie Hogben*

We investigate the expected value of various graph parameters associated with the minimum rank of a graph, including minimum rank/maximum nullity and related Colin de Verdière-type parameters. Let G(v,p) denote the usual Erdős-Rényi random graph on v vertices with edge probability p. We obtain bounds for the expected value of the random variables mr(G(v,p)), M(G(v,p)), ν(G(v,p)) and ξ(G(v,p)), which yield bounds on the average values of these parameters over all labeled graphs of order v.

An Upper Bound For The Minimum Rank Of A Graph, 2017 Technion-Israel Institute of Technology

#### An Upper Bound For The Minimum Rank Of A Graph, Avi Berman, Shmuel Friedland, Leslie Hogben, Uriel G. Rothblum, Bryan Shader

*Leslie Hogben*

For a graph G of order n, the minimum rank of G is defined to be the smallest possible rank over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. We prove an upper bound for minimum rank in terms of minimum degree of a vertex is valid for many graphs, including all bipartite graphs, and conjecture this bound is true over for all graphs, and prove a related bound for all zero-nonzero patterns of (not necessarily symmetric) matrices. Most ...

Note On Nordhaus-Gaddum Problems For Colin De Verdière Type Parameters, 2017 Brigham Young University

#### Note On Nordhaus-Gaddum Problems For Colin De Verdière Type Parameters, Wayne Barrett, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben

*Leslie Hogben*

We establish the bounds 4 3 6 b 6 b 6 p 2, where b and b are the Nordhaus-Gaddum sum upper bound multipliers, i.e., (G)+(G) 6 bjGj and (G)+(G) 6 bjGj for all graphs G, and and are Colin de Verdiere type graph parameters. The Nordhaus-Gaddum sum lower bound for and is conjectured to be jGj 2, and if these parameters are replaced by the maximum nullity M(G), this bound is called the Graph Complement Conjecture in the study of minimum rank/maximum nullity problems.

On The Distance Spectra Of Graphs, 2017 Kharazmi University

#### On The Distance Spectra Of Graphs, Ghodratollah Aalipour, Aida Abiad, Zhanar Berikkyzy, Jay Cummings, Jessica De Silva, Wei Gao, Kristin Heysse, Leslie Hogben, Franklin H.J. Kenter, Jephian C.H. Lin, Michael Tait

*Leslie Hogben*

The distance matrix of a graph G is the matrix containing the pairwise distances between vertices. The distance eigenvalues of G are the eigenvalues of its distance matrix and they form the distance spectrum of G. We determine the distance spectra of double odd graphs and Doob graphs, completing the determination of distance spectra of distance regular graphs having exactly one positive distance eigenvalue. We characterize strongly regular graphs having more positive than negative distance eigenvalues. We give examples of graphs with few distinct distance eigenvalues but lacking regularity properties. We also determine the determinant and inertia of the distance ...

Recursive Robust Pca Or Recursive Sparse Recovery In Large But Structured Noise, 2017 Iowa State University

#### Recursive Robust Pca Or Recursive Sparse Recovery In Large But Structured Noise, Chenlu Qiu, Namrata Vaswani, Brian Lois, Leslie Hogben

*Leslie Hogben*

This paper studies the recursive robust principal components analysis problem. If the outlier is the signal-of-interest, this problem can be interpreted as one of recursively recovering a time sequence of sparse vectors, St, in the presence of large but structured noise, Lt. The structure that we assume on Lt is that Lt is dense and lies in a low-dimensional subspace that is either fixed or changes slowly enough. A key application where this problem occurs is in video surveillance where the goal is to separate a slowly changing background (Lt) from moving foreground objects (St) on-the-fly. To solve the above ...

Rainbow Arithmetic Progressions, 2017 Iowa State University

#### Rainbow Arithmetic Progressions, Steve Butler, Craig Erickson, Leslie Hogben, Kirsten Hogenson, Lucas Kramer, Richard Kramer, Jephian C. H. Lin, Ryan R. Martin, Derrick Stolee, Nathan Warnberg, Michael Young

*Leslie Hogben*

In this paper, we investigate the anti-Ramsey (more precisely, anti-van der Waerden) properties of arithmetic progressions. For positive integers n and k, the expression aw([n]; k) denotes the smallest number of colors with which the integers f1; : : : ; ng can be colored and still guarantee there is a rainbow arithmetic progression of length k. We establish that aw([n]; 3) = (log n) and aw([n]; k) = n1o(1) for k 4. For positive integers n and k, the expression aw(Zn; k) denotes the smallest number of colors with which elements of the cyclic group of order n can be ...

Note On Power Propagation Time And Lower Bounds For The Power Domination Number, 2017 Texas State University

#### Note On Power Propagation Time And Lower Bounds For The Power Domination Number, Daniela Ferrero, Leslie Hogben, Franklin H. J. Kenter, Michael Young

*Leslie Hogben*

We present a counterexample to a lower bound for the power domination number given in Liao (J Comb Optim 31:725–742, 2016). We also define the power propagation time, using the power domination propagation ideas in Liao and the (zero forcing) propagation time in Hogben et al. (Discrete Appl Math 160:1994–2005, 2012).

The Enhanced Principal Rank Characteristic Sequence, 2017 Iowa State University

#### The Enhanced Principal Rank Characteristic Sequence, Steve Butler, Minerva Catral, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, P. Van Den Driessche, Michael Young

*Leslie Hogben*

The enhanced principal rank characteristic sequence (epr-sequence) of a symmetric n×n matrix is a sequence ℓ1ℓ2⋯ℓn where ℓk is A, S, or N according as all, some, or none of its principal minors of order k are nonzero. Such sequences give more information than the (0,1) pr-sequences previously studied (where basically the kth entry is 0 or 1 according as none or at least one of its principal minors of order k is nonzero). Various techniques including the Schur complement are introduced to establish that certain subsequences such as NAN are forbidden in epr-sequences over fields of ...

Fractional Zero Forcing Via Three-Color Forcing Games, 2017 Iowa State University

#### Fractional Zero Forcing Via Three-Color Forcing Games, Leslie Hogben, Kevin F. Palmowski, David E. Roberson, Michael Young

*Leslie Hogben*

An r-fold analogue of the positive semidefinite zero forcing process that is carried out on the r-blowup of a graph is introduced and used to define the fractional positive semidefinite forcing number. Properties of the graph blowup when colored with a fractional positive semidefinite forcing set are examined and used to define a three-color forcing game that directly computes the fractional positive semidefinite forcing number of a graph. We develop a fractional parameter based on the standard zero forcing process and it is shown that this parameter is exactly the skew zero forcing number with a three-color approach. This approach ...