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<degG(vi)<n10<\operatorname{deg}_G(v_i)<n-1, let degG(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<degG(vi)<n1degG(vi)+E(G)>n(n1)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<degG(vi)<n1degG(vi)+E(G)=n(n1)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.

Sources & referencesView supporting material

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.