Search

Throttling in graphs optimizes a sum or product of resources used, such as the number of vertices in an initial set, and time required, such as the propagation time, to complete a given task. We introduce a new technique to establish sharp upper bounds in terms of graph order for sum throttling and initial cost product throttling for power domination. Furthermore, we establish sharp bounds on possible changes of the product throttling number, both with and without initial cost, caused by certain graph operations for standard zero forcing, positive semidefinite forcing, and power domination.

The parameter $q(G)$ of an $n$-vertex graph $G$ is the minimum number of distinct eigenvalues over the family of symmetric matrices described by $G$. We show that all $G$ with $e(\overline{G}) = |E(\overline{G})| \leq \lfloor n/2 \rfloor -1$ have $q(G)=2$. We conjecture that any $G$ with $e(\overline{G}) \leq n-3$ satisfies $q(G) = 2$. We show that this conjecture is true if $\overline{G}$ is bipartite and in other sporadic cases. Furthermore, we characterize $G$ with $\overline{G}$ bipartite and $e(\overline{G}) = n-2$ for which $q(G) > 2$.

We consider bounds on maximum nullity of a graph via transversal numbers of compatible collections of forts. Results include generalizations of theorems from symmetric to combinatorially symmetric matrices, special bases of matrix nullspaces derived from transversal sets, and examples of issues that arise when considering only minimal forts and how to avoid them. We also show an important difference between constructing symmetric and combinatorially symmetric matrices associated to a graph whose nullspaces are supported on collections of disjoint forts.

We investigate the sparsity of null vectors of real symmetric matrices whose off-diagonal pattern of zero and nonzero entries is described by the adjacencies of a graph. We use the definition of the spark of a matrix, the smallest number of nonzero coordinates of any null vector, to define the spark of a graph as the smallest possible spark of a corresponding matrix. We study connections of graph spark to well-known concepts including minimum rank, forts, orthogonal representations, Parter and Fiedler vertices, and vertex connectivity., Comment: 20 pages, 2 figures

For an $n \times n$ matrix $A$, let $q(A)$ be the number of distinct eigenvalues of $A$. If $G$ is a connected graph on $n$ vertices, let $\mathcal{S}(G)$ be the set of all real symmetric $n \times n$ matrices $A=[a_{ij}]$ such that for $i\neq j$, $a_{ij}=0$ if and only if $\{i,j\}$ is not an edge of $G$. Let $q(G)={\rm min}\{q(A)\,:\,A \in \mathcal{S}(G)\}$. Studying $q(G)$ has become a fundamental sub-problem of the inverse eigenvalue problem for graphs, and characterizing the case for which $q(G)=2$ has been especially difficult. This paper considers the problem of determining the regular graphs $G$ that satisfy $q(G)=2$. The resolution is straightforward if the degree of regularity is $1, 2,$ or $3$. However, the $4$-regular graphs with $q(G)=2$ are much more difficult to characterize. A connected $4$-regular graph has $q(G)=2$ if and only if either $G$ belongs to a specific infinite class of graphs, or else $G$ is one of fifteen $4$-regular graphs whose number of vertices ranges from $5$ to $16$. This technical result gives rise to several intriguing questions., Comment: AMS subject classification: 05C50, 15A29, 15A18

The parameter $q(G)$ of a graph $G$ is the minimum number of distinct eigenvalues over the family of symmetric matrices described by $G$. It is shown that the minimum number of edges necessary for a connected graph $G$ to have $q(G)=2$ is $2n-4$ if $n$ is even, and $2n-3$ if $n$ is odd. In addition, a characterization of graphs for which equality is achieved in either case is given., Comment: 13 pages

Dual multiplicity graphs are those simple, undirected graphs that have a weighted Hermitian adjacency matrix with only two distinct eigenvalues. From the point of view of frame theory, their characterization can be restated as which graphs have a representation by a tight frame. In this paper, we classify certain line graphs that are tight frame graphs and improve a previous result on the embedding of frame graphs in tight frame graphs., Comment: 14 pages, 6 figures. Version 2 of this paper adds a reference, adds a figure, and includes minor corrections and revisions

This paper extends three results from classical finite frame theory over real or complex numbers to binary frames for the vector space ${\mathbb Z}_2^d$. Without the notion of inner products or order, we provide an analog of the "fundamental inequality" of tight frames. In addition, we prove the binary analog of the characterization of dual frames with given inner products and of general frames with prescribed norms and frame operator., Comment: Version 2 of this paper corrects a mistake in the last sentence of the paragraph following Theorem 2.4. The mistake remains in the published version (Involve); however, it is not consequential

The upper and lower Nordhaus-Gaddum bounds over all graphs for the power domination number follow from known bounds on the domination number and examples. In this note we improve the upper sum bound for the power domination number substantially for graphs having the property that both the graph and its complement must be connected. For these graphs, our bound is tight and is also significantly better than the corresponding bound for domination number. We also improve the product upper bound for the power domination number for graphs with certain properties.

The power domination number arises from the monitoring of electrical networks and its determination is an important problem. Upper bounds for power domination numbers can be obtained by constructions. Lower bounds for the power domination number of several families of graphs are known, but they usually arise from specific properties of each family and the methods do not generalize. In this paper we exploit the relationship between power domination and zero forcing to obtain the first general lower bound for the power domination number. We apply this bound to obtain results for both the power domination of tensor products and the zero-forcing number of lexicographic products of graphs. We also establish results for the zero forcing number of tensor products and Cartesian products of graphs.

We discuss how generalized multiresolution analyses (GMRAs), both classical and those defined on abstract Hilbert spaces, can be classified by their multiplicity functions $m$ and matrix-valued filter functions $H$. Given a natural number valued function $m$ and a system of functions encoded in a matrix $H$ satisfying certain conditions, a construction procedure is described that produces an abstract GMRA with multiplicity function $m $ and filter system $H$. An equivalence relation on GMRAs is defined and described in terms of their associated pairs $(m,H)$. This classification system is applied to classical examples in $L^2 (\mathbb R^d)$ as well as to previously studied abstract examples., Comment: 18 pages including bibliograph

We study generalized filters that are associated to multiplicity functions and homomorphisms of the dual of an abelian group. These notions are based on the structure of generalized multiresolution analyses. We investigate when the Ruelle operator corresponding to such a filter is a pure isometry, and then use that characterization to study the problem of when a collection of closed subspaces, which satisfies all the conditions of a GMRA except the trivial intersection condition, must in fact have a trivial intersection. In this context, we obtain a generalization of a theorem of Bownik and Rzeszotnik., Comment: 20 pages including bibliography