Bounding the total forcing number of graphs

Shengjin Ji (), Mengya He (), Guang Li (), Yingui Pan () and Wenqian Zhang ()
Additional contact information
Shengjin Ji: Shandong University of Technology
Mengya He: Shandong University of Technology
Guang Li: Shandong University of Technology
Yingui Pan: National University of Defense Technology
Wenqian Zhang: Shandong University of Technology

Journal of Combinatorial Optimization, 2023, vol. 46, issue 4, No 3, 8 pages

Abstract: Abstract In recent years, a dynamic coloring, named as zero forcing, of the vertices in a graph have attracted many researchers. For a given G and a vertex subset S, assigning each vertex of S black and each vertex of $$V\setminus S$$ V \ S no color, if one vertex $$u\in S$$ u ∈ S has a unique neighbor v in $$V\setminus S$$ V \ S , then u forces v to color black. S is called a zero forcing set if S can be expanded to the entire vertex set V by repeating the above forcing process. S is regarded as a total forcing set if the subgraph G[S] satisfies $$\delta (G[S])\ge 1$$ δ ( G [ S ] ) ≥ 1 . The minimum cardinality of a total forcing set in G, denoted by $$F_t(G)$$ F t ( G ) , is named the total forcing number of G. For a graph G, p(G), q(G) and $$\phi (G)$$ ϕ ( G ) denote the number of pendant vertices, the number of vertices with degree at least 3 meanwhile having one pendant path and the cyclomatic number of G, respectively. In the paper, by means of the total forcing set of a spanning tree regarding a graph G, we verify that $$F_t(G)\le p(G)+q(G)+2\phi (G)$$ F t ( G ) ≤ p ( G ) + q ( G ) + 2 ϕ ( G ) . Furthermore, all graphs achieving the equality are determined.

Keywords: Zero forcing set; Total forcing set; Cyclomatic number; Cactus graphs; Spanning tree; 05C69; 05C05; 05C57 (search for similar items in EconPapers)
Date: 2023
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://link.springer.com/10.1007/s10878-023-01089-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:jcomop:v:46:y:2023:i:4:d:10.1007_s10878-023-01089-4

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/10878

DOI: 10.1007/s10878-023-01089-4

Access Statistics for this article

Journal of Combinatorial Optimization is currently edited by Thai, My T.

More articles in Journal of Combinatorial Optimization from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().