The odd-order exact formula for replication numbers of paths

Let PnP_n be the path on nn vertices, and let ρR(Pn)\rho_R(P_n) denote its replication number. For odd n1n\geq 1, write the upper-bound formula according to the residue class of nn modulo 44. The odd-order exact formula. The upper bound is tight, namely

ρR(Pn)={n2/4+n2/16+3n/8+5/16,n1(mod4),n2/4+n2/16+3n/8+1/16,n3(mod4).\rho_R(P_n)=\begin{cases} n^2/4+n^2/16+3n/8+5/16,& n\equiv 1\pmod 4,\\ n^2/4+n^2/16+3n/8+1/16,& n\equiv 3\pmod 4. \end{cases}

Computer searches determine the exact values for n16n\leq 16, and this conjecture proposes the displayed formula for all odd nn.

Sources & referencesView supporting material

Primary source

Marek Szykuła and Andrzej Kisielewicz, “Rainbow Induced Subgraphs in Replication Graphs”, arXiv:1201.5340 (2012).

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.