Back to Search
Start Over
Zero Forcing in Claw-Free Cubic Graphs.
- Source :
-
Bulletin of the Malaysian Mathematical Sciences Society . Jan2020, Vol. 43 Issue 1, p673-688. 16p. - Publication Year :
- 2020
-
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) ≤ 1 3 n + 1 . Both bounds are shown to be best possible. [ABSTRACT FROM AUTHOR]
- Subjects :
- *GRAPH coloring
Subjects
Details
- Language :
- English
- ISSN :
- 01266705
- Volume :
- 43
- Issue :
- 1
- Database :
- Academic Search Index
- Journal :
- Bulletin of the Malaysian Mathematical Sciences Society
- Publication Type :
- Academic Journal
- Accession number :
- 140453344
- Full Text :
- https://doi.org/10.1007/s40840-018-00705-5