The {\it zero forcing number} of a graph $G$, $Z(G)$, is a well-studied parameter which arises from a color changing process and has strong connections to {\it minimum rank}, {\it critical ideals} and related invariants. In this work, we consider the complementary parameter $\mz(G) = |V(G)| - Z(G)$. This parameter is monotone under taking induced subgraphs. This leads us to the study of graphs for which $\mz(G)$ is bounded, via forbidden induced subgraphs. We prove that the number of minimal forbidden graphs for graphs with $\mz(G)\leq k$ is finite for any $k\geq 1$. We determine the complete set of minimal forbidden graphs for the case $k = 3$, and we provide partial characterizations of graphs with $\mz(G) \leq 3$, based on girth. Our results suggest new directions for the structural understanding of zero forcing-type parameters.
In this paper we introduce and explore the following new graph invariant: For a graph $G$ on $k$ vertices, $G \neq K_k$, let $st(n,G)$ denote the maximum number of edges in a graph of order $n$ which does not contain any subgraph on $k$ vertices strictly containing $G$. A basic relation to classical Tur\'an numbers is...
For a finite graph $G$, the maximum average degree $\operatorname{mad}(G)$ is the largest average degree of a nonempty subgraph of $G$. Hendrey, Norin and Wood asked whether this parameter is partitionable, that is, whether for all positive reals $a,b$ every graph $G$ with $\operatorname{mad}(G)<a+b$ admits a vertex pa...
Andrzej Grzesik, Lenka Kopfová, Gaurav Kucheriya et al.· 0 citations
The toughness of a connected noncomplete graph $G$ is$$\tau(G)=\min\left\{\frac{|S|}{c(G-S)}:S\subseteq V(G),\ c(G-S)\geq2\right\},$$where $c(G)$ is the number of components of $G$; as usual, $\tau(K_n)=\infty$. In 1973, Bondy proposed the metaconjecture that almost every nontrivial condition implying Hamiltonicity sho...
Cai-Li Jia, Xiang-Ge Liu, Lu Yong et al.· Electronic Journal of Combin...· 0 citations
The $k$-th power of a simple graph $G$, denoted $G^k$, is the graph with vertex set $V(G)$ where two vertices are adjacent if they are within distance $k$ in $G$. We investigate the zero forcing number of graph powers. Powers of graphs are much denser and generally not encompassed by existing results on zero forcing of...
A. Abiad, Mary Flagg, Sina Ghasemi Nezhad et al.· 0 citations
Let $G$ be a finite simple graph on the vertex set $[n]$, and let $\Gamma(G)$ be the Cayley graph of the symmetric group $S_n$ generated by the transpositions corresponding to the edges of $G$. We study the inverse spectral problem for the assignment $G\mapsto \Gamma(G)$ through the group-algebra operator $A_G=\sum_{\{...
The lettericity of a graph $G$ is the smallest size of a set $\Sigma$ such that there exist $w_1, \ldots, w_{|V(G)|} \in \Sigma$ and a so-called decoder $D \subseteq \Sigma^2$ for which $G$ is isomorphic to the letter graph $(\{1, \ldots, |V(G)|\}, \{ij : 1 \le i<j \le |V(G)|, w_iw_j \in D\})$. It took around two decad...
Henning Fernau, S. German, Kevin Mann et al.· 1 citation
We use cookies to run the site and, with your consent, for analytics and to show ads.
See our Cookie Policy.
