Open Access. Powered by Scholars. Published by Universities.®

Discrete Mathematics and Combinatorics Commons

Open Access. Powered by Scholars. Published by Universities.®

610 Full-Text Articles 755 Authors 54052 Downloads 72 Institutions

All Articles in Discrete Mathematics and Combinatorics

Faceted Search

610 full-text articles. Page 1 of 20.

Differentiating Between A Protein And Its Decoy Using Nested Graph Models And Weighted Graph Theoretical Invariants, Hannah E. Green 2017 East Tennessee State University

Differentiating Between A Protein And Its Decoy Using Nested Graph Models And Weighted Graph Theoretical Invariants, Hannah E. Green

Electronic Theses and Dissertations

To determine the function of a protein, we must know its 3-dimensional structure, which can be difficult to ascertain. Currently, predictive models are used to determine the structure of a protein from its sequence, but these models do not always predict the correct structure. To this end we use a nested graph model along with weighted invariants to minimize the errors and improve the accuracy of a predictive model to determine if we have the correct structure for a protein.


On T-Restricted Optimal Rubbling Of Graphs, Kyle Murphy 2017 East Tennessee State University

On T-Restricted Optimal Rubbling Of Graphs, Kyle Murphy

Electronic Theses and Dissertations

For a graph G = (V;E), a pebble distribution is defined as a mapping of the vertex set in to the integers, where each vertex begins with f(v) pebbles. A pebbling move takes two pebbles from some vertex adjacent to v and places one pebble on v. A rubbling move takes one pebble from each of two vertices that are adjacent to v and places one pebble on v. A vertex x is reachable under a pebbling distribution f if there exists some sequence of rubbling and pebbling moves that places a pebble on x. A pebbling distribution where ...


"Returning To The Root" Of The Problem: Improving The Social Condition Of African Americans Through Science And Mathematics Education, Vanessa R. Pitts Bannister, Julius Davis, Jomo Mutegi, LaTasha Thompson, Deborah Lewis 2017 Florida A&M University

"Returning To The Root" Of The Problem: Improving The Social Condition Of African Americans Through Science And Mathematics Education, Vanessa R. Pitts Bannister, Julius Davis, Jomo Mutegi, Latasha Thompson, Deborah Lewis

Catalyst: A Social Justice Forum

The underachievement and underrepresentation of African Americans in STEM (Science, Technology, Engineering and Mathematics) disciplines have been well documented. Efforts to improve the STEM education of African Americans continue to focus on relationships between teaching and learning and factors such as culture, race, power, class, learning preferences, cultural styles and language. Although this body of literature is deemed valuable, it fails to help STEM teacher educators and teachers critically assess other important factors such as pedagogy and curriculum. In this article, the authors argue that both pedagogy and curriculum should be centered on the social condition of African Americans – thus ...


Does Logic Help Us Beat Monty Hall?, Adam J. Hammett, Nathan A. Harold, Tucker R. Rhodes 2017 Cedarville University

Does Logic Help Us Beat Monty Hall?, Adam J. Hammett, Nathan A. Harold, Tucker R. Rhodes

The Research and Scholarship Symposium

The classical Monty Hall problem entails that a hypothetical game show contestant be presented three doors and told that behind one door is a car and behind the other two are far less appealing prizes, like goats. The contestant then picks a door, and the host (Monty) is to open a different door which contains one of the bad prizes. At this point in the game, the contestant is given the option of keeping the door she chose or changing her selection to the remaining door (since one has already been opened by Monty), after which Monty opens the chosen ...


Six Septembers: Mathematics For The Humanist, Patrick Juola, Stephen Ramsay 2017 Duquesne University

Six Septembers: Mathematics For The Humanist, Patrick Juola, Stephen Ramsay

Zea E-Books

Scholars of all stripes are turning their attention to materials that represent enormous opportunities for the future of humanistic inquiry. The purpose of this book is to impart the concepts that underlie the mathematics they are likely to encounter and to unfold the notation in a way that removes that particular barrier completely. This book is a primer for developing the skills to enable humanist scholars to address complicated technical material with confidence. This book, to put it plainly, is concerned with the things that the author of a technical article knows, but isn’t saying. Like any field, mathematics ...


Fractional Zero Forcing Via Three-Color Forcing Games, Leslie Hogben, Kevin F. Palmowski, David E. Roberson, Michael Young 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 ...


Minimum Rank Of Skew-Symmetric Matrices Described By A Graph, Mary Allison, Elizabeth Bodine, Luz Maria DeAlba, Joyati Debnath, Laura DeLoss, Colin Garnett, Jason Grout, Leslie Hogben, Bokhee Im, Hana Kim, Reshmi Nair, Olga Pryporova, Kendrick Savage, Bryan Shader, Amy Wangsness Wehe 2017 University of Wyoming

Minimum Rank Of Skew-Symmetric Matrices Described By A Graph, Mary Allison, Elizabeth Bodine, Luz Maria Dealba, Joyati Debnath, Laura Deloss, Colin Garnett, Jason Grout, Leslie Hogben, Bokhee Im, Hana Kim, Reshmi Nair, Olga Pryporova, Kendrick Savage, Bryan Shader, Amy Wangsness Wehe

Leslie Hogben

The minimum (symmetric) rank of a simple graph G over a field F is the smallest possible rank among all symmetric matrices over F whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. The problem of determining minimum (symmetric) rank has been studied extensively. We define the minimum skew rank of a simple graph G to be the smallest possible rank among all skew-symmetric matrices over F whose ijth entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. We apply ...


The Copositive Completion Problem: Unspecified Diagonal Entries, Leslie Hogben 2017 Iowa State University

The Copositive Completion Problem: Unspecified Diagonal Entries, Leslie Hogben

Leslie Hogben

In [L. Hogben, C.R. Johnson, R. Reams, The copositive matrix completion problem, Linear Algebra Appl. 408 (2005) 207–211] it was shown that any partial (strictly) copositive matrix all of whose diagonal entries are specified can be completed to a (strictly) copositive matrix. In this note we show that every partial strictly copositive matrix (possibly with unspecified diagonal entries) can be completed to a strictly copositive matrix, but there is an example of a partial copositive matrix with an unspecified diagonal entry that cannot be completed to a copositive matrix.


The Symmetric M-Matrix And Symmetric Inverse M-Matrix Completion Problems, Leslie Hogben 2017 Iowa State University

The Symmetric M-Matrix And Symmetric Inverse M-Matrix Completion Problems, Leslie Hogben

Leslie Hogben

The symmetric M-matrix and symmetric M0-matrix completion problems are solved and results of Johnson and Smith [Linear Algebra Appl. 290 (1999) 193] are extended to solve the symmetric inverse M-matrix completion problem: (1) A pattern (i.e., a list of positions in an n×n matrix) has symmetric M-completion (i.e., every partial symmetric M-matrix specifying the pattern can be completed to a symmetric M-matrix) if and only if the principal subpattern R determined by its diagonal is permutation similar to a pattern that is block diagonal with each diagonal block complete, or, in graph theoretic terms, if and only ...


Potentially Eventually Exponentially Positive Sign Patterns, Marie Archer, Minerva Catral, Craig Erickson, Rana Haber, Leslie Hogben, Xavier Martinez-Rivera, Antonio Ochoa 2017 Columbia College

Potentially Eventually Exponentially Positive Sign Patterns, Marie Archer, Minerva Catral, Craig Erickson, Rana Haber, Leslie Hogben, Xavier Martinez-Rivera, Antonio Ochoa

Leslie Hogben

We introduce the study of potentially eventually exponentially positive (PEEP) sign patterns and establish several results using the connections between these sign patterns and the potentially eventually positive (PEP) sign patterns. It is shown that the problem of characterizing PEEP sign patterns is not equivalent to that of characterizing PEP sign patterns. A characterization of all 2×2 and 3×3 PEEP sign patterns is given.


Recursive Robust Pca Or Recursive Sparse Recovery In Large But Structured Noise, Chenlu Qiu, Namrata Vaswani, Brian Lois, Leslie Hogben 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 ...


Spectrally Arbitrary Patterns: Reducibility And The 2n Conjecture For N = 5, Luz M. DeAlba, Irvin R. Hentzel, Leslie Hogben, Judith McDonald, Rana Mikkelson, Olga Pryporova, Bryan Shader, Kevin N. Vander Meulen 2017 Drake University

Spectrally Arbitrary Patterns: Reducibility And The 2n Conjecture For N = 5, Luz M. Dealba, Irvin R. Hentzel, Leslie Hogben, Judith Mcdonald, Rana Mikkelson, Olga Pryporova, Bryan Shader, Kevin N. Vander Meulen

Leslie Hogben

A sign pattern Z (a matrix whose entries are elements of {+, −, 0}) is spectrally arbitrary if for any self-conjugate spectrum there is a real matrix with sign pattern Z having the given spectrum. Spectrally arbitrary sign patterns were introduced in [J.H. Drew, C.R. Johnson, D.D. Olesky, P. van den Driessche, Spectrally arbitrary patterns, Linear Algebra Appl. 308 (2000) 121–137], where it was (incorrectly) stated that if a sign pattern Z is reducible and each of its irreducible components is a spectrally arbitrary sign pattern, then Z is a spectrally arbitrary sign pattern, and it was conjectured ...


The Copositive Completion Problem, Leslie Hogben, Charles R. Johnson, Robert Reams 2017 Iowa State University

The Copositive Completion Problem, Leslie Hogben, Charles R. Johnson, Robert Reams

Leslie Hogben

An n × n real symmetric matrix A is called (strictly) copositive if xTAx ⩾ 0 (>0) whenever x ∈ Rn satisfies x ⩾ 0 (x ⩾ 0 and x ≠ 0). The (strictly) copositive matrix completion problem asks which partial (strictly) copositive matrices have a completion to a (strictly) copositive matrix. We prove that every partial (strictly) copositive matrix has a (strictly) copositive matrix completion and give a lower bound on the values used in the completion. We answer affirmatively an open question whether an n × n copositive matrix A = (aij) with all diagonal entries aii = 1 stays copositive if each off-diagonal entry of A ...


The Minimum Rank Of Symmetric Matrices Described By A Graph: A Survey, Shaun M. Fallat, Leslie Hogben 2017 University of Regina

The Minimum Rank Of Symmetric Matrices Described By A Graph: A Survey, Shaun M. Fallat, Leslie Hogben

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. This paper surveys the current state of knowledge on the problem of determining the minimum rank of a graph and related issues.


Orthogonal Representations, Minimum Rank, And Graph Complements, Leslie Hogben 2017 Iowa State University

Orthogonal Representations, Minimum Rank, And Graph Complements, Leslie Hogben

Leslie Hogben

Orthogonal representations are used to show that complements of certain sparse graphs have (positive semidefinite) minimum rank at most 4. This bound applies to the complement of a 2-tree and to the complement of a unicyclic graph. Hence for such graphs, the sum of the minimum rank of the graph and the minimum rank of its complement is at most two more than the order of the graph. The minimum rank of the complement of a 2-tree is determined exactly.


Minimum Rank Problems, Leslie Hogben 2017 Iowa State University

Minimum Rank Problems, Leslie Hogben

Leslie Hogben

A graph describes the zero–nonzero pattern of a family of matrices, with the type of graph (undirected or directed, simple or allowing loops) determining what type of matrices (symmetric or not necessarily symmetric, diagonal entries free or constrained) are described by the graph. The minimum rank problem of the graph is to determine the minimum among the ranks of the matrices in this family; the determination of maximum nullity is equivalent. This problem has been solved for simple trees [P.M. Nylen, Minimum-rank matrices with prescribed graph, Linear Algebra Appl. 248 (1996) 303–316, C.R. Johnson, A. Leal ...


On The Difference Between The Maximum Multiplicity And Path Cover Number For Tree-Like Graphs, Francesco Barioli, Shaun Fallat, Leslie Hogben 2017 Carleton University

On The Difference Between The Maximum Multiplicity And Path Cover Number For Tree-Like Graphs, Francesco Barioli, Shaun Fallat, Leslie Hogben

Leslie Hogben

For a given undirected graph G, the maximum multiplicity of G is defined to be the largest multiplicity of an eigenvalue 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. We derive a formula for the path cover number of a vertex-sum of graphs, and use it to prove that the vertex-sum of so-called non-deficient graphs is non-deficient. For ...


Path Cover Number, Maximum Nullity, And Zero Forcing Number Of Oriented Graphs And Other Simple Digraphs, Adam Berliner, Cora Brown, Joshua Carlson, Nathanael Cox, Leslie Hogben, Jason Hu, Katrina Jacobs, Kathryn Manternach, Travis Peters, Nathan Warnberg, Michael Young 2017 Saint Olaf College

Path Cover Number, Maximum Nullity, And Zero Forcing Number Of Oriented Graphs And Other Simple Digraphs, Adam Berliner, Cora Brown, Joshua Carlson, Nathanael Cox, Leslie Hogben, Jason Hu, Katrina Jacobs, Kathryn Manternach, Travis Peters, Nathan Warnberg, Michael Young

Leslie Hogben

An oriented graph is a simple digraph obtained from a simple graph by choosing exactly one of the two arcs (u,v)(u,v) or (v,u)(v,u) to replace each edge {u,v}{u,v}. A simple digraph describes the zero-nonzero pattern of off-diagonal entries of a family of (not necessarily symmetric) matrices. The minimum rank of a simple digraph is the minimum rank of this family of matrices; maximum nullity is defined analogously. The simple digraph zero forcing number and path cover number are related parameters. We establish bounds on the range of possible values of all ...


Minimum Rank, Maximum Nullity And Zero Forcing Number For Selected Graph Families, Edgard Almodovar, Laura DeLoss, Leslie Hogben, Kirsten Hogenson, Kaitlyn Murphy, Travis Peters, Camila A. Ramírez 2017 University of Puerto Rico, Río Piedras Campus

Minimum Rank, Maximum Nullity And Zero Forcing Number For Selected Graph Families, Edgard Almodovar, Laura Deloss, Leslie Hogben, Kirsten Hogenson, Kaitlyn Murphy, Travis Peters, Camila A. Ramírez

Leslie Hogben

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≠j) is nonzero whenever {i,j}{i,j} is an edge in G and is zero otherwise. Maximum nullity is taken over the same set of matrices, and the sum of maximum nullity and minimum rank is the order of the graph. The zero forcing number is the minimum size of a zero forcing set of vertices and bounds the maximum nullity from above. This paper defines the graph families ciclos and estrellas and ...


Rational Realization Of Maximum Eigenvalue Multiplicity Of Symmetric Tree Sign Patterns, Atoshi Chowdhury, Leslie Hogben, Jude Melancon, Rana Mikkelson 2017 Princeton University

Rational Realization Of Maximum Eigenvalue Multiplicity Of Symmetric Tree Sign Patterns, Atoshi Chowdhury, Leslie Hogben, Jude Melancon, Rana Mikkelson

Leslie Hogben

A sign pattern is a matrix whose entries are elements of {+, −, 0}; it describes the set of real matrices whose entries have the signs in the pattern. A graph (that allows loops but not multiple edges) describes the set of symmetric matrices having a zero-nonzero pattern of entries determined by the absence or presence of edges in the graph. DeAlba et al. [L.M. DeAlba, T.L. Hardy, I.R. Hentzel, L. Hogben, A. Wangsness, Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns, Linear Algebra Appl., in press, doi:10.1016/j.laa.2006.02.018.] gave ...


Digital Commons powered by bepress