Total Forcing and Zero Forcing in Claw-Free Cubic Graphs

Randy Davila, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

7 Citations (Scopus)

Abstract

A dynamic coloring of the vertices of a graph G starts with an initial subset S of colored vertices, with all remaining vertices being non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set S is called a forcing set (zero forcing set) of G if, by iteratively applying the forcing process, every vertex in G becomes colored. If the initial set S has the added property that it induces a subgraph of G without isolated vertices, then S is called a total forcing set in G. The total forcing number of G, denoted Ft(G) , is the minimum cardinality of a total forcing set in G. We prove that if G is a connected, claw-free, cubic graph of order n≥ 6 , then Ft(G)≤12n, where a claw-free graph is a graph that does not contain K1 , 3 as an induced subgraph. The graphs achieving equality in these bounds are characterized.

Original languageEnglish
Pages (from-to)1371-1384
Number of pages14
JournalGraphs and Combinatorics
Volume34
Issue number6
DOIs
Publication statusPublished - 1 Nov 2018

Keywords

  • Claw-free
  • Cubic
  • Cycle cover
  • Total forcing sets
  • Zero forcing sets

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics

Fingerprint

Dive into the research topics of 'Total Forcing and Zero Forcing in Claw-Free Cubic Graphs'. Together they form a unique fingerprint.

Cite this