错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Failed zero forcing numbers of Kneser graphs, Johnson graphs, and hypercubes

  • Fatemeh Afzali,
  • Amir Hossein Ghodrati,
  • Hamid Reza Maimani

摘要

For a graph \(G=(V,E)\) G = ( V , E ) and an assignment of black and white colors to its vertices, the zero forcing color-change rule operates as follows: if a vertex u and all of its neighbors except v are black, then v is forced to change its color to black. A proper subset S of V is called a zero forcing set if by initially assigning the black vertices to be the elements of S and repeatedly applying this rule to G, all vertices are eventually forced to change their colors to black. Otherwise, S is called a failed zero forcing set. The maximum size of a failed zero forcing set of G is called the failed zero forcing number of G and is denoted by F(G). In this paper, we study the failed zero forcing numbers of three graph families: Kneser graphs K(nr), Johnson graphs J(nr), and hypercube graphs \(Q_n\) Q n  . Specifically, we prove that \(F(K(n, r))=\left( {\begin{array}{c}n\\ r\end{array}}\right) -(r+2)\) F ( K ( n , r ) ) = n r - ( r + 2 ) , for \(2\le r \le \frac{n-1}{2}\) 2 r n - 1 2 , \(F(J(n, r))=\left( {\begin{array}{c}n\\ r\end{array}}\right) -(r+1)\) F ( J ( n , r ) ) = n r - ( r + 1 ) , for \(1\le r \le \frac{n}{2}\) 1 r n 2 , and \(F(Q_n)=2^n - n\) F ( Q n ) = 2 n - n , for \(n \ge 2\) n 2  .