The zero forcing conjecture for Johnson graphs

About 3 years old · traced to

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 q≥0q\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 n≥8n\geq 8,

Z0(Gn)=(n−12).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 n≥7,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.

References

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.