Saturation-number formula for joins of cliques and paths

About 17 years old · traced to

Let PkP_k be the path on kk vertices, let KsK_s be the complete graph on ss vertices, and let sat(n,H)sat(n,H) denote the minimum number of edges in an HH-saturated graph on nn vertices. Let aka_k be defined as in equation (1.1)(1.1), with k,s≥3k,s\geq 3 and n≥ak+sn\geq a_k+s. Saturation-number conjecture.

sat(n,Ks∨Pk)=(s2)+s(n−s)+sat(n−s,Pk).sat(n,K_s\vee P_k)=\binom{s}{2}+s(n-s)+sat(n-s,P_k).

This conjecture extends the known saturation-number results for k∈{1,2}k\in\{1,2\}, s=1s=1, and s=2s=2, and is motivated by Proposition 5.4, which establishes the displayed quantity as an upper bound. The equality remains open in the stated range.

References

Primary source

Xiaoxue Zhang, Lihua You and Xinghui Zhao, “Saturation numbers of K_2P_k”, arXiv:2511.20213 (2025).

Additional references

3 papers in this index state this conjecture (2009–2025). The statement above is taken from the most recent of them; the others are arXiv:2311.16899, arXiv:0909.1970.

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.