On Extremal Graphs for Zero Forcing Number

被引:0
作者
Yi-Ping Liang
Jianxi Li
Shou-Jun Xu
机构
[1] Lanzhou University,School of Mathematics and Statistics, Gansu Center for Applied Mathematics
[2] Minnan Normal University,School of Mathematics and Statistics
来源
Graphs and Combinatorics | 2022年 / 38卷
关键词
Zero forcing number; Connected forcing number; Girth; Triangle-free; Subcubic; 05C69; 05C75;
D O I
暂无
中图分类号
学科分类号
摘要
A subset S of vertex set V(G) of a graph G is a zero forcing set of G if iteratively adding vertices to S from V(G)\S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V(G){\setminus }S$$\end{document} that are the unique neighbor in V(G)\S\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$V(G){\setminus } S$$\end{document} of some vertex in S, results in the entire V(G) of G. Additionally, if the subgraph induced by S is connected, then S is a connected forcing set of G. The zero (resp., connected) forcing number, denoted by F(G) (resp., Fc(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_c(G)$$\end{document}), of G is the minimum cardinality of a zero (resp., connected) forcing set of G. Davila and Kenter [Theory Appl. Graphs, 2(2) (2015) Article 1] proved that F(G)≤n-g+2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(G)\le n-g+2$$\end{document} for graphs G of finite girth g and order n(≥g)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n (\ge g)$$\end{document}. In this paper, first, we restrict G to be connected and improve the upper bound according to the value of g: F(G)≤n-g+2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(G)\le n-g+2$$\end{document} when g=3,4\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$g=3, 4$$\end{document} or n; F(G)≤n-g+1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(G)\le n-g+1$$\end{document} when g=5,6\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$g=5, 6$$\end{document} or n-1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$n-1$$\end{document}(n≥6)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$(n \ge 6)$$\end{document} and F(G)≤n-g\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(G)\le n-g$$\end{document} when 7≤g≤n-2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$7\le g\le n-2$$\end{document}. Further, the extremal graphs are characterized, respectively. Davila et al. [Graphs Combin. 34 (2018) 1159-1174] proved a similar upper bound on Fc(G)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_c(G)$$\end{document} for 2-connected graphs G with n vertices and finite girth g: Fc(G)≤n-g+2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_c(G)\le n-g+2$$\end{document}. Secondly, we prove that Fc(G)=n-g+2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F_c(G)=n-g+2$$\end{document} if and only if G is Cn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$C_{n}$$\end{document}, or Kn\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{n}$$\end{document}, or Ka,b\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$K_{a,b}$$\end{document} for integers a,b≥2\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a, b \ge 2$$\end{document}, a+b=n\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$a+b=n$$\end{document}. Finally, we also characterize all connected triangle-free or subcubic graphs G of order n with F(G)=n-3\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$F(G)=n-3$$\end{document}.
引用
收藏
相关论文
共 74 条
  • [1] Alishahi M(2020)Maximum nullity and zero forcing number on graphs with maximum degree at most three Discrete Appl. Math. 284 179-194
  • [2] Rezaei-Sani E(2015)Upper bounds on the Discrete Appl. Math. 181 1-10
  • [3] Sharifi E(2004)-forcing number of a graph Linear Algebra Appl. 392 289-303
  • [4] Amos D(2008)Computation of minimal rank and path cover number for graphs Linear Algebra Appl. 429 1629-1638
  • [5] Caro Y(2004)An upper bound for the minimum rank of a graph Electron. J. Linear Algebra. 11 258-280
  • [6] Davila R(2017)Graphs whose minimal rank is two Discrete Appl. Math. 229 31-45
  • [7] Pepper R(2007)Complexity and computation of connected zero forcing Phys. Rev. Lett. 99 100-501
  • [8] Barioli F(2015)Full control by locally induced relaxation Nat. Comput. 14 485-490
  • [9] Fallat S(2007)Logic circuits from zero forcing Electron. J. Linear Algebra. 16 60-67
  • [10] Hogben L(2019)On the nullity of graphs Discrete Appl. Math. 257 115-127