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 条

[21] The characterization of the upper bounds on the largest Laplacian eigenvalue of weighted graphs [J].

Li, Ping .

ARS COMBINATORIA, 2020, 153 :99-107

[22] Upper signed k-domination number in graphs [J].

Zhou, Ligang ;

Shan, Erfang ;

Zhao, Yancai .

ARS COMBINATORIA, 2015, 122 :307-318

[23] The Sharp Upper Bounds on the Aα-Spectral Radius of C4-Free Graphs and Halin Graphs [J].

Guo, Shu-Guang ;

Zhang, Rong .

GRAPHS AND COMBINATORICS, 2022, 38 (01)

[24] The Lower and Upper Bounds of Turán Number for Odd Wheels [J].

Byeong Moon Kim ;

Byung Chul Song ;

Woonjae Hwang .

Graphs and Combinatorics, 2021, 37 :919-932

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

ZHU Jun-qiao 1 BU Yue-hua 2 .

Applied Mathematics:A Journal of Chinese Universities, 2012, (03) :329-334

[26] Sharp upper bounds for the adjacency and the signless Laplacian spectral radius of graphs [J].

WU Xianzhang ;

LIU Jianping .

AppliedMathematics:AJournalofChineseUniversities, 2019, 34 (01) :100-112

[27] Sharp upper bounds for the adjacency and the signless Laplacian spectral radius of graphs [J].

Wu Xian-zhang ;

Liu Jian-ping .

APPLIED MATHEMATICS-A JOURNAL OF CHINESE UNIVERSITIES SERIES B, 2019, 34 (01) :100-112

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

Shuiqun Xie ;

Xiaodan Chen ;

Xiuyu Li ;

Xiaoqian Liu .

Bulletin of the Malaysian Mathematical Sciences Society, 2021, 44 :2063-2080

[29] Sharp upper bounds for the adjacency and the signless Laplacian spectral radius of graphs [J].

Xian-zhang Wu ;

Jian-ping Liu .

Applied Mathematics-A Journal of Chinese Universities, 2019, 34 :100-112

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

Jun-qiao Zhu ;

Yue-hua Bu .

Applied Mathematics-A Journal of Chinese Universities, 2012, 27 :329-334

← 1 2 3 4 5 →