On the total forcing number of a graph
| Autor: | Michael A. Henning, Randy Davila |
|---|---|
| Rok vydání: | 2019 |
| Předmět: |
Applied Mathematics
0211 other engineering and technologies Complete graph 021107 urban & regional planning 0102 computer and information sciences 02 engineering and technology 01 natural sciences Graph Combinatorics 010201 computation theory & mathematics Zero Forcing Equalizer Discrete Mathematics and Combinatorics Connectivity Mathematics |
| Zdroj: | Discrete Applied Mathematics. 257:115-127 |
| ISSN: | 0166-218X |
| DOI: | 10.1016/j.dam.2018.09.001 |
| Popis: | 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 N P -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 ) ≤ ( Δ Δ + 1 ) n , with equality if and only if G is a complete graph K Δ + 1 , or a star K 1 , Δ . |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|
Full Text from ScienceDirect