The full-degree vertex necessity conjecture for saturation of joins

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

Full-degree vertex necessity conjecture. If

sat(n,K1F)=n1+sat(n1,F),\operatorname{sat}(n,K_1\vee F)=n-1+\operatorname{sat}(n-1,F),

then some extremal graph of K1FK_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(Kp1K1)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.

Sources & referencesView supporting material

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.