The forcing number of graphs with given girth

Graphs and linear algebra (matrices, eigenvalues, etc.) (05C50) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

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 called a forcing set of

G

if, by iteratively applying the forcing process, every vertex in

G

becomes colored. The forcing number, originally known as the emph{zero forcing number}, and denoted

F (G)

, of

G

is the cardinality of a smallest forcing set of

G

. We study lower bounds on the forcing number in terms of its minimum degree and girth, where the girth

g

of a graph is the length of a shortest cycle in the graph. Let

G

be a graph with minimum degree

d e l t a g e 2

and girth~

g g e 3

. Davila and Kenter [Theory and Applications of Graphs, Volume 2, Issue 2, Article 1, 2015] conjecture that

F (G) g e d e l t a + (d e l t a - 2) (g - 3)

. This conjecture has recently been proven for

g l e 6

. The conjecture is also proven when the girth

g g e 7

and the minimum degree is sufficiently large. In particular, it holds when

g = 7

and

d e l t a g e 481

, when

g = 8

and

d e l t a g e 649

, when

g = 9

and

d e l t a g e 30

, and when

g = 10

and

d e l t a g e 34

. In this paper, we prove the conjecture for

g i n 7, 8, 9, 10

and for all values of

d e l t a g e 2

.

Recommendations

Cites work

Cited in

(20)

This page was built for publication: The forcing number of graphs with given girth

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4639236)