Results 21 to 30 of about 13,009 (241)
Three-connected graphs whose maximum nullity is at most three
Linear Algebra and its Applications, 2008 Let \(G=(V,E)\) be a graph with \(V=\{1,2,\dots,n\}\). Define \(\mathcal S(G)\) as the set of all \(n\times n\) real-valued symmetric matrices \(A=[a_{i,j}]\) with \(a_{i,j}\neq 0\), \(i\neq j\), if and only if \(ij\in E\). The maximum nullity of \(G\), denoted by \(M(G)\), is the largest possible nullity of any matrix \(A\in\mathcal S(G)\).
Hein van der Holst
openalex +4 more sources
Minimum rank, maximum nullity and zero forcing number for selected graph families [PDF]
Involve, a Journal of Mathematics, 2010 The minimum rank of a simple graph G is dened to be the smallest possible rank over all symmetric real matrices whose ijth entry (for i 6 j) is nonzero whenever fi;jg 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.
Edgard Almodovar +6 more
openalex +4 more sources
Maximum nullity and zero forcing number on cubic graphs [PDF]
, 2017 Let $G$ be a graph. The maximum nullity of $G$, denoted by $M(G)$, is defined to be the largest possible nullity over all real symmetric matrices $A$ whose $a_{ij}\neq 0$ for $i\neq j$, whenever two vertices $u_i$ and $u_j$ of $G$ are adjacent. In this paper, we characterize all cubic graphs with zero forcing number $3$.
Saieed Akbari +2 more
openalex +3 more sources
Zero forcing number, path cover number, and maximum nullity of cacti [PDF]
Involve, a Journal of Mathematics, 2011 The zero forcing number of a graph is the minimum size of a zero forcing set. This parameter is useful in the minimum rank/maximum nullity problem, as it gives an upper bound to the maximum nullity. The path cover number of a graph is the minimum size of a path cover.
Darren D. Row
openalex +3 more sources
Linear Algebra and its Applications, 2004 The nullity of a graph is the multiplicity of the eigenvalue zero in its spectrum. Among all \(n\)-vertex trees, the star tree has greatest nullity (equal to \(n-2\)). In this paper it is shown that among all \(n\)-vertex trees whose vertex degrees do not exceed a fixed value \(D\), the greatest nullity is \(n- 2 \lceil (n-1)/D \rceil\).
Stanley Fiorini +2 more
openalex +3 more sources
Zero forcing number, maximum nullity, and path cover number of subdivided graphs
The Electronic Journal of Linear Algebra, 2012 The zero forcing number, maximum nullity and path cover number of a (simple, undirected) graph are parameters that are important in the study of minimum rank problems. We investigate the effects on these graph parameters when an edge is subdivided to obtain a so-called edge subdivision graph. An open question raised by Barrett et al. is answered in the
Minerva Catral +6 more
openalex +6 more sources
The stable maximum nullity of digraphs and $1$-DAGs [PDF]
Given a digraph $D=(V,A)$ with vertex-set $V=\{1,\ldots,n\}$ and arc-set $A$, we denote by $Q(D)$ the set of all real $n\times n$ matrices $B=[b_{u,w}]$ with $b_{u,u}\not=0$ for all $u\in V$, $b_{u,w} \not= 0$ if $u\not=w$ and there is an arc from $u$ to $w$, and $b_{u,w}=0$ if $u\not=w$ and there is no arc from $u$ to $w$.
Marina Arav, Hein van der Holst
openalex +3 more sources
A note on minimum rank and maximum nullity of sign patterns
The Electronic Journal of Linear Algebra, 2011 The minimum rank of a sign pattern matrix is defined to be the smallest possible rank over all real matrices having the given sign pattern. The maximum nullity of a sign pattern is the largest possible nullity over the same set of matrices, and is equal to the number of columns minus the minimum rank of the sign pattern.
Leslie Hogben
openalex +5 more sources
The Electronic Journal of Linear Algebra, 2012 The maximum positive semidefinite nullity of a multigraph G is the largest possible nullity over all real positive semidefinite matrices whose (i,j)th entry (for i 6 j) is zero if i and j are not adjacent in G, is nonzero if fi,jg is a single edge, and is any real number if fi,jg is a multiple edge.
Jason Ekstrand +4 more
openalex +5 more sources
Minimum rank, maximum nullity, and zero forcing number of simple digraphs
The Electronic Journal of Linear Algebra, 2013 A simple digraph describes the off-diagonal zero-nonzero pattern of a family of (not necessarily symmetric) matrices. 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 is an upper bound for maximum nullity.
Adam H. Berliner +5 more
openalex +4 more sources