The zero forcing conjecture for Johnson graphs

Let Gn=K(n,2)G_n=K(n,2) be the Johnson graph whose vertices are the 22-subsets of an nn-element set, with two vertices adjacent when the corresponding subsets intersect in one element. For an integer q0q\geq 0, let Zq(Gn)Z_q(G_n) denote the qq-zero forcing number of GnG_n. The zero forcing conjecture for GnG_n. For any n8n\geq 8,

Z0(Gn)=(n12).Z_0(G_n)=\binom{n-1}{2}.

Moreover,

Z0(Gn)=(n2)6for n{5,6,7},Z_0(G_n)=\binom{n}{2}-6\quad\text{for }n\in\{5,6,7\},

and

Z0(Gn)=Z1(Gn)for any n7,Z_0(G_n)=Z_1(G_n)\quad\text{for any }n\geq 7,

while

Z1(Gn)=Z0(Gn)+1for n{5,6}.Z_1(G_n)=Z_0(G_n)+1\quad\text{for }n\in\{5,6\}.

These claims refine the preceding exact values and bounds for the zero forcing numbers of the Johnson graphs K(n,2)K(n,2); the source does not report a resolution.

Sources & referencesView supporting material

Primary source

Shaun Fallat, Neha Joshi, Roghayeh Maleki, Karen Meagher, Seyed Ahmad Mojallal, Shahla Nasserasr, Mahsa N. Shirazi, Andriaherimanana Sarobidy Razafimahatratra and Brett Stevens, “The q-Analogue of Zero Forcing for Certain Families of Graphs”, arXiv:2306.01138 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.