587 research outputs found
Note on Nordhaus-Gaddum Problems for Colin de Verdière type Parameters
No full textWe 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.This article is published as Barrett, Wayne, Shaun M. Fallat, H. Tracy Hall, and Leslie Hogben. "Note on Nordhaus-Gaddum Problems for Colin de Verdière type Parameters." The Electronic Journal of Combinatorics 20, no. 3 (2013): P56. DOI: 10.37236/2570. Posted with permission.</p
Minimum Rank, Maximum Nullity, and Zero Forcing Number of Graphs
No full textThis chapter represents an overview of research related to a notion of the “rank of a graph" and the dual concept known as the “nullity of a graph," from the point of view of associating a fixed collection of symmetric or Hermitian matrices to a given graph. This topic and related questions have enjoyed a fairly large history within discrete mathematics, and have become very popular among linear algebraists recently, partly based on its connection to certain inverse eigenvalue problems, but also because of the many interesting applications (e.g., to communication complexity in computer science and to control of quantum systems in mathematical physics) and implications to several facets of graph theory.
This chapter is divided into eight parts, beginning in Section 1 with what we feel is the standard minimum rank problem concerning symmetric matrices over the real numbers associated with a simple graph. We continue with important variants of the standard minimum rank problem and related parameters, including the concept of minimum rank over other fields (Section 2), the positive semidefinite minimum rank of a graph (Section 3), graph coloring parameters known as zero forcing numbers (Section 4) and the more classical and celebrated parameters due to Y. Colin de Verdière (Section 5). Section 6 contains more advanced topics relevant to the previous five sections, and Section 7 discusses two well-known conjectures related to minimum rank. Whereas the first seven sections concern primarily symmetric matrices and the diagonal of the matrix is free, in Section 8 we discuss minimum rank problems with no symmetry assumption but the diagonal constrained.
NB: The topics discussed in this chapter are in an active research area and the facts presented here represent the state of knowledge as of the writing of this chapter in 2012.This is an Accepted Manuscript of the book chapter Fallat, Shaun M., and Leslie Hogben. "Minimum Rank, Maximum Nullity, and Zero Forcing Number of Graphs." In Handbook of Linear Algebra, Second Edition, edited by Leslie Hogben. Boca Raton, Florida : CRC Press/Taylor & Francis Group, 2014: 46-1 to 46-36. Posted with permission.</p
The Inverse Eigenvalue Problem of a Graph, Zero Forcing, and Related Parameters
No full textThe dynamics of many physical systems can be distilled from the eigenvalues and eigenfunctions of a corresponding operator. For example, possible vibrations of a thin membrane can be described in terms of the eigenvalues and eigenfunctions of the Laplace operator on the membrane. Kac’s famous question “Can you hear the shape of a drum?” is a type of inverse eigenvalue problem, that is, a problem that asks what are the properties of the system if the eigenvalues of the corresponding operator are known. For example, the eigenvalues of the Laplacian determine the area of the membrane but don’t (uniquely) determine the shape of the membrane (up to isometry). In this context, we can view the inverse eigenvalue problem of a graph as, “What possible collection of sounds (that is, eigenvalues) can a drum of your shape, that is, a matrix whose off-diagonal nonzero pattern is described by the edges of , make?”This article is published as Fallat, Shaun M., Leslie Hogben, Jephian C-H. Lin, and Bryan L. Shader. "The inverse eigenvalue problem of a graph, zero forcing, and related parameters." Notices of the American Mathematical Society 67, no. 2 (2020). DOI: https://doi.org/10.1090/noti203
The Inverse Eigenvalue Problem of a Graph
No full textInverse eigenvalue problems appear in various contexts throughout mathematics and engineering, and refer to determining all possible lists of eigenvalues (spectra) for matrices fitting some description. The inverse eigenvalue problem of a graph refers to determining the possible spectra of real symmetric matrices whose pattern of nonzero off-diagonal entries is described by the edges of a given graph (precise definitions of this and other terms are given in the next paragraph). This problem and related variants have been of interest for many years and were originally approached through the study of ordered multiplicity lists.This report resulted from the Banff International Research Station Focused Research Groups and is published as Barrett, Wayne, Steve Butler, Shaun Fallat, H. Tracy Hall, Leslie Hogben, Jephian CH Lin, Bryan Shader, and Michael Young. "The inverse eigenvalue problem of a graph." Banff International Research Station: The Inverse Eigenvalue Problem of a Graph, 2016. Posted with permission.</p
Time out
No full textCatalogue essay by Shaun Wilson.
Published to accompany the exhibition held at s.p.a.c.e. Gallery, Launceston, Tasmania, 6-20 July 2007
On the class of graphs ZP
No full textA Thesis Submitted to the Faculty of Graduate Studies and Research In Partial Fulfillment of the Requirements for the Degree of Master of Science in Mathematics, University of Regina. vii, 60 p.The following research was primarily focused on the class of graphs denoted by ZP.
Let G = (V,E) be a graph made up of vertices V and edges E. The path cover number
and zero forcing number are two graph parameters that have been of recent research
interests and are closely related. Zero forcing at it’s most rudimentary, is a graph
colouring game. There is a significant preexisting body of work on zero forcing, which
includes relations between zero forcing and path cover numbers (denoted by Z(G)
and P(G), respectively), as well as a relation between zero forcing and a notion of
maximum nullity of a graph. One natural question along these lines that emerged was
to impose equality conditions between Z(G) and P(G), and assuming these equality
constraints hold for both G and all induced subgraphs of G, what class of graphs
might arise and what is special about said graphs? Thus, we study the class ZP in
which the zero forcing number and the path cover number are equal over all induced
subgraphs. As many graphs are known to belong to ZP, such a trees, cycles, and
cacti, these graphs are an excellent starting point for study. Hence, the cycle graph,
denoted by Cn, provide the primary point of study early on in the research process.
As Cn is a graph known to belong to ZP, we add interior chords to the cycle graph
in many different orientations and in many numbers, then examine the resulting
changes in both Z(G) and P(G). We then consider analyzing graphs that belong to
ZP by conditioning on possible values of the path cover number, namely assuming
P(G) = 2 and P(G) = 3. Finally, graph operations and their effect on graphs in ZP
are considered. Of particular importance are the vertex and edge-sum operations.
Ultimately, we are able to prove that the vertex or edge-sums of graphs in ZP do
indeed remain in the class ZP.Studentye
COVID-19 housing assistance / analyst: Shaun McGann
No full text1 online resource (2 unnumbered pages)"November 24, 2020."; Includes bibliographical references (2nd unnumbered page)Discusses federal government and Connecticut's state lending authority temporary relief to public student loan borrowers during the COVID-19 pandemi
Parameters Related to Tree-Width, Zero Forcing, and Maximum Nullity of a Graph
No full textTree-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 path-width are each characterized in terms of a minor monotone floor of a certain zero forcing parameter defined by a color change rule.This is the peer-reviewed version of the following article: Barioli, Francesco, Wayne Barrett, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Bryan Shader, Pauline van den Driessche, and Hein Van Der Holst. "Parameters Related to Tree‐Width, Zero Forcing, and Maximum Nullity of a Graph." Journal of Graph Theory 72, no. 2 (2013): 146-177, which has been published in final form at DOI: 10.1002/jgt.21637. This article may be used for non-commercial purposes in accordance with Wiley Terms and Conditions for Self-Archiving. Posted with permission.</p
Interview with Shaun Tan
No full textShaun Tan is a Melbourne-based artist and author, whose work is celebrated worldwide for the beautiful, dynamic, and mesmerizing story worlds that it offers readers and viewers. In 2011, Tan received the prestigious Astrid Lindgren Memorial Award in honour of his contribution to international children’s literature, and an Academy Award for the short animated film adaptation of The Lost Thing (Ruheman and Tan 2011), which he directed with Andrew Ruhemann. Tan’s work ranges from drawing and painting, to sculpture and animation, whose complex themes, and sensitive nuances resist easy classification. Instead, his sometimes surreal, playful, and evocative stories immerse readers into new and productively strange places
The inverse eigenvalue problem of a graph: Multiplicities and minors
No full textThe inverse eigenvalue problem of a given graph G is to determine all possible spectra of real symmetric matrices whose off-diagonal entries are governed by the adjacencies in G. Barrett et al. introduced the Strong Spectral Property (SSP) and the Strong Multiplicity Property (SMP) in [Generalizations of the Strong Arnold Property and the minimum number of distinct eigenvalues of a graph. Electron. J. Combin., 2017]. In that paper it was shown that if a graph has a matrix with the SSP (or the SMP) then a supergraph has a matrix with the same spectrum (or ordered multiplicity list) augmented with simple eigenvalues if necessary, that is, subgraph monotonicity. In this paper we extend this to a form of minor monotonicity, with restrictions on where the new eigenvalues appear. These ideas are applied to solve the inverse eigenvalue problem for all graphs of order five, and to characterize forbidden minors of graphs having at most one multiple eigenvalue.This is a manuscript of an article published as Barrett, Wayne, Steve Butler, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Jephian C-H. Lin, Bryan L. Shader, and Michael Young. 142 "The inverse eigenvalue problem of a graph: Multiplicities and minors." Journal of Combinatorial Theory, Series B (2020): 276-306. DOI: 10.1016/j.jctb.2019.10.005. Posted with permission.</p
- …
