UPPER BOUNDS ON THE SEMITOTAL FORCING NUMBER OF GRAPHS

被引：0

作者：

Liang, Yi-Ping ^{[1
]}

Chen, Jie ^{[1
]}

Xu, Shou-Jun ^{[1
]}

机构：

[1] Lanzhou Univ, Gansu Ctr Appl Math, Sch Math & Stat, Lanzhou 730000, Gansu, Peoples R China

来源：

BULLETIN OF THE AUSTRALIAN MATHEMATICAL SOCIETY | 2024年 / 109卷 / 02期

基金：

中国国家自然科学基金;

关键词：

semitotal forcing number; NP-complete; extremal graph; upper bound;

D O I：

10.1017/S000497272300045X

中图分类号：

O1 [数学];

学科分类号：

0701 ; 070101 ;

摘要：

Let G be a graph with no isolated vertex. A semitotal forcing set of G is a (zero) forcing set S such that every vertex in S is within distance 2 of another vertex of S. The semitotal forcing number F-t2(G) is the minimum cardinality of a semitotal forcing set in G. In this paper, we prove that it is NP-complete to determine the semitotal forcing number of a graph. We also prove that if G ? K(n )is a connected graph of order n = 4 with maximum degree ? = 2, then F-t2(G) = (? - 1)n/?, with equality if and only if either G = C(4)or G = P(4)or G = K-?,K-?.

引用

页码：177 / 185

页数：9

共 50 条

[31] Upper Bounds on the (Signless Laplacian) Spectral Radius of Irregular Weighted Graphs [J].

Xie, Shuiqun ;

Chen, Xiaodan ;

Li, Xiuyu ;

Liu, Xiaoqian .

BULLETIN OF THE MALAYSIAN MATHEMATICAL SCIENCES SOCIETY, 2021, 44 (04) :2063-2080

[32] Upper bounds on vertex distinguishing chromatic index of some Halin graphs [J].

Zhu Jun-qiao ;

Bu Yue-hua .

APPLIED MATHEMATICS-A JOURNAL OF CHINESE UNIVERSITIES SERIES B, 2012, 27 (03) :329-334

[33] The performance of an upper bound on the fractional chromatic number of weighted graphs [J].

Ganesan, Ashwin .

APPLIED MATHEMATICS LETTERS, 2010, 23 (05) :597-599

[34] Improved Upper Bounds on the Number of Non-Zero Weights of Cyclic Codes [J].

Chen, Bocong ;

Fu, Yuqing ;

Liu, Hongwei .

IEEE TRANSACTIONS ON INFORMATION THEORY, 2024, 70 (06) :4079-4092

[35] New upper bounds on the number of non-zero weights of constacyclic codes [J].

Chen, Li ;

Fu, Yuqing ;

Liu, Hongwei .

DISCRETE MATHEMATICS, 2024, 347 (12)

[36] Sum coloring and interval graphs: a tight upper bound for the minimum number of colors [J].

Nicoloso, S .

DISCRETE MATHEMATICS, 2004, 280 (1-3) :251-257

[37] New upper bounds on the spectral radius of trees with the given number of vertices and maximum degree [J].

Song, Haizhou ;

Wang, Qiufen ;

Tian, Lulu .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2013, 439 (09) :2527-2541

[38] On the Upper Bounds of Number of Linear Regions and Generalization Error of Deep Convolutional Neural Networks [J].

Chen, Degang ;

Liu, Jiayu ;

Che, Xiaoya .

IEEE TRANSACTIONS ON PATTERN ANALYSIS AND MACHINE INTELLIGENCE, 2025, 47 (06) :5014-5022

[39] Variable neighborhood search for extremal graphs. 22. Extending bounds for independence to upper irredundance [J].

Aouchiche, Mustapha ;

Favaron, Odile ;

Hansen, Pierre .

DISCRETE APPLIED MATHEMATICS, 2009, 157 (17) :3497-3510

[40] Upper bounds for the spread of a matrix [J].

Wu, Junliang ;

Zhang, Pingping ;

Liao, Wenshi .

LINEAR ALGEBRA AND ITS APPLICATIONS, 2012, 437 (11) :2813-2822

← 1 2 3 4 5 →