The full-degree vertex necessity conjecture for saturation of joins

Less than 1 year old · traced to

Let FF be a non-empty graph and let n≥∣V(F)∣+1n\geq |V(F)|+1. Write K1∨FK_1\vee F for the join of FF with a single vertex, and call a vertex full-degree if its degree is n−1n-1. An extremal graph for saturation is an nn-vertex K1∨FK_1\vee F-saturated graph with sat⁡(n,K1∨F)\operatorname{sat}(n,K_1\vee F) edges.

Full-degree vertex necessity conjecture. If

sat⁡(n,K1∨F)=n−1+sat⁡(n−1,F),\operatorname{sat}(n,K_1\vee F)=n-1+\operatorname{sat}(n-1,F),

then some extremal graph of K1∨FK_1\vee F contains a full-degree vertex.

The conjecture proposes a necessary structural condition for equality in the standard upper bound obtained by adjoining a universal vertex to an extremal FF-saturated graph. The paper's discussion shows that, for the particular join K1∨(Kp−1−∪K1)K_1\vee(K_{p-1}^-\cup K_1), extremal graphs have no full-degree vertex, but it does not establish the conjecture in general.

References

Primary source

Xinying Hua and Yuejian Peng, “Saturation numbers of some joins of graphs”, arXiv:2606.22006 (2026).

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.