Back to Search
Start Over
Zero forcing versus domination in cubic graphs
- Source :
- Journal of Combinatorial Optimization. 41:553-577
- Publication Year :
- 2021
- Publisher :
- Springer Science and Business Media LLC, 2021.
-
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 non-colored. At each discrete time interval, a colored vertex with exactly one non-colored neighbor forces this non-colored neighbor to be colored. The initial set S is a zero forcing set of G if, by iteratively5 applying the forcing process, every vertex in G becomes colored. The zero forcing number of G is the minimum cardinality of a zero forcing set of G. In this paper, we prove that if $$G \ne K_4$$ is a connected cubic graph, then the zero forcing number of G is bounded above by twice its domination number, where the domination number of G is the minimum cardinality of a set of vertices of G such that every vertex not in S is adjacent to some vertex in S.
- Subjects :
- 021103 operations research
Control and Optimization
Forcing (recursion theory)
Domination analysis
Applied Mathematics
0211 other engineering and technologies
0102 computer and information sciences
02 engineering and technology
01 natural sciences
Computer Science Applications
Vertex (geometry)
Combinatorics
Cardinality
Computational Theory and Mathematics
Colored
010201 computation theory & mathematics
Discrete Mathematics and Combinatorics
Interval (graph theory)
Graph (abstract data type)
Cubic graph
Mathematics
Subjects
Details
- ISSN :
- 15732886 and 13826905
- Volume :
- 41
- Database :
- OpenAIRE
- Journal :
- Journal of Combinatorial Optimization
- Accession number :
- edsair.doi...........b0bf0714c25b0443f6f0620e1c7496a6