Marcello's completion conjecture for connected graphs with at most one pendant vertex

Let GG be a non-complete, connected graph of order nn with at most one pendant vertex. For each vertex viv_i whose degree satisfies 0<deg⁡G(vi)<n−10<\operatorname{deg}_G(v_i)<n-1, let deg⁡G(vi)\operatorname{deg}_G(v_i) denote its degree, let E(G)E(G) be the edge set of GG, and let ϖ(G)\varpi(G) be the number of global iterations in Marcello's completion. Then the following assertions are made:

Marcello's completion conjecture.

(a) If

∑0<deg⁡G(vi)<n−1deg⁡G(vi)+∣E(G)∣>n(n−1)2,\sum_{0<\operatorname{deg}_G(v_i)<n-1}\operatorname{deg}_G(v_i)+|E(G)|>\frac{n(n-1)}{2},

then ϖ(G)=1\varpi(G)=1.

(b) If

∑0<deg⁡G(vi)<n−1deg⁡G(vi)+∣E(G)∣=n(n−1)2,\sum_{0<\operatorname{deg}_G(v_i)<n-1}\operatorname{deg}_G(v_i)+|E(G)|=\frac{n(n-1)}{2},

then ϖ(G)=1\varpi(G)=1 or 22.

The paper presents these assertions in the context of determining Marcello numbers and understanding how many Marcello edges can be found during a global iteration. The conclusion describes the general problem of guaranteeing the maximum number of Marcello edges as open, and no resolution of these assertions is supplied.

References

Primary source

Johan Kok, “Marcello's completion of graphs”, arXiv:2507.02015 (2025).

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.