Back to Search
Start Over
UPPER BOUNDS ON THE SEMITOTAL FORCING NUMBER OF GRAPHS.
- Source :
-
Bulletin of the Australian Mathematical Society . Apr2024, Vol. 109 Issue 2, p177-185. 9p. - Publication Year :
- 2024
-
Abstract
- Let G be a graph with no isolated vertex. A semitotal forcing set of G is a (zero) forcing set S such that every vertex in S is within distance 2 of another vertex of S. The semitotal forcing number $F_{t2}(G)$ is the minimum cardinality of a semitotal forcing set in G. In this paper, we prove that it is NP-complete to determine the semitotal forcing number of a graph. We also prove that if $G\neq K_n$ is a connected graph of order $n\geq 4$ with maximum degree $\Delta \geq 2$ , then $F_{t2}(G)\leq (\Delta-1)n/\Delta$ , with equality if and only if either $G=C_{4}$ or $G=P_{4}$ or $G=K_{\Delta ,\Delta }$. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH connectivity
*DOMINATING set
Subjects
Details
- Language :
- English
- ISSN :
- 00049727
- Volume :
- 109
- Issue :
- 2
- Database :
- Academic Search Index
- Journal :
- Bulletin of the Australian Mathematical Society
- Publication Type :
- Academic Journal
- Accession number :
- 175959489
- Full Text :
- https://doi.org/10.1017/S000497272300045X