Zero Forcing in Claw-Free Cubic Graphs

Randy Davila, Michael A. Henning

Research output: Contribution to journalArticlepeer-review

5 Citations (Scopus)

Abstract

In this paper, we study a dynamic coloring of the vertices of a graph G that starts with an initial subset S of colored vertices, with all remaining vertices being uncolored. At each discrete time interval, a colored vertex with exactly one uncolored neighbor forces this uncolored neighbor to be colored. The initial set S is a zero forcing set of G if, by iteratively applying the forcing process, every vertex in G becomes colored. The zero forcing number Z(G) of G is the minimum cardinality of a zero forcing set of G. In this paper, we prove that if G is a connected, cubic, claw-free graph of order n≥ 6 , then Z(G) ≤ α(G) + 1 where α(G) denotes the independence number of G. Further we prove that if n≥ 10 , then Z(G)≤13n+1. Both bounds are shown to be best possible.

Original languageEnglish
Pages (from-to)673-688
Number of pages16
JournalBulletin of the Malaysian Mathematical Sciences Society
Volume43
Issue number1
DOIs
Publication statusPublished - 1 Jan 2020

Keywords

  • Claw-free
  • Independence number
  • Zero forcing number
  • Zero forcing set

ASJC Scopus subject areas

  • General Mathematics

Fingerprint

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

Cite this