On the total forcing number of a graph

被引：18

作者：

Davila, Randy ^{[1
,2
]}

Henning, Michael A. ^{[1
]}

机构：

[1] Univ Johannesburg, Dept Pure & Appl Math, ZA-2006 Auckland Pk, South Africa

[2] Univ Houston Downtown, Dept Math & Stat, Houston, TX 77002 USA

来源：

DISCRETE APPLIED MATHEMATICS | 2019年 / 257卷

基金：

新加坡国家研究基金会;

关键词：

Forcing sets; Total forcing sets; Dominating sets; Total forcing number; ZERO; DOMINATION; BOUNDS;

D O I：

10.1016/j.dam.2018.09.001

中图分类号：

O29 [应用数学];

学科分类号：

070104 ;

摘要：

A total forcing set in a graph G is a forcing set (zero forcing set) in G which induces a subgraph without isolated vertices. Total forcing sets were introduced and first studied by Davila (2015). The total forcing number of G, denoted F-t (G) is the minimum cardinality of a total forcing set in G. We study basic properties of F-t (G), relate F-t (G) to various domination parameters, and establish NP-completeness of the associated decision problem for F-t (G). Our main contribution is to prove that if G is a connected graph of order n >= 3 with maximum degree Delta,then F-t (G) <= (Delta/Delta+1)n, with equality if and only if G is a complete graph K-Delta(+1), or a star K-1,K- Delta. (C) 2018 Elsevier B.V. All rights reserved.

引用

页码：115 / 127

页数：13

共 50 条

[11] THE FORCING NONSPLIT DOMINATION NUMBER OF A GRAPH
John, J.
Raj, Malchijah
KOREAN JOURNAL OF MATHEMATICS, 2021, 29 (01): : 1 - 12
[12] Forcing Independent Domination Number of a Graph
Armada, Cris L.
Canoy, Sergio, Jr.
EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS, 2019, 12 (04): : 1371 - 1381
[13] The upper forcing geodetic number of a graph
Zhang, P
ARS COMBINATORIA, 2002, 62 : 3 - 15
[14] Bounds on the Connected Forcing Number of a Graph
Davila, Randy
Henning, Michael A.
Magnant, Colton
Pepper, Ryan
GRAPHS AND COMBINATORICS, 2018, 34 (06) : 1159 - 1174
[15] FORCING SUPER DOMINATION NUMBER OF A GRAPH
Liguarda, Remilou F.
Canoy, Sergio R., Jr.
ADVANCES AND APPLICATIONS IN DISCRETE MATHEMATICS, 2018, 19 (04): : 339 - 357
[16] ON THE CHROMATIC FORCING NUMBER OF A RANDOM GRAPH
MCDIARMID, C
DISCRETE APPLIED MATHEMATICS, 1983, 5 (01) : 123 - 132
[17] Bounds on the Connected Forcing Number of a Graph
Randy Davila
Michael A. Henning
Colton Magnant
Ryan Pepper
Graphs and Combinatorics, 2018, 34 : 1159 - 1174
[18] FORCING DETOUR MONOPHONIC NUMBER OF A GRAPH
Titus, P.
Ganesamoorthy, K.
FACTA UNIVERSITATIS-SERIES MATHEMATICS AND INFORMATICS, 2013, 28 (02): : 211 - 220
[19] The forcing near geodetic number of a graph
Lenin, R.
DISCRETE MATHEMATICS ALGORITHMS AND APPLICATIONS, 2020, 12 (02)
[20] THE FORCING HOP DOMINATION NUMBER OF A GRAPH
Anusha, D.
Robin, S. Joseph
ADVANCES AND APPLICATIONS IN DISCRETE MATHEMATICS, 2020, 25 (01): : 55 - 70

← 1 2 3 4 5 →