On the total forcing number of a graph

Randy Davila, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

15 Citations (Scopus)

Abstract

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 Δ, then F t (G)≤([Formula presented])n, with equality if and only if G is a complete graph K Δ+1 , or a star K 1,Δ .

Original languageEnglish
Pages (from-to)115-127
Number of pages13
JournalDiscrete Applied Mathematics
Volume257
DOIs
Publication statusPublished - 31 Mar 2019

Keywords

  • Dominating sets
  • Forcing sets
  • Total forcing number
  • Total forcing sets

ASJC Scopus subject areas

  • Discrete Mathematics and Combinatorics
  • Applied Mathematics

Fingerprint

Dive into the research topics of 'On the total forcing number of a graph'. Together they form a unique fingerprint.

Cite this