Maximum independent edge set conjecture for 3-token graphs of paths

From papers

Let PnP_n be the path graph on nn vertices, and let Γ3(Pn)\Gamma_3(P_n) denote its 33-token graph. Write α(G)\alpha'(G) for the maximum size of an independent edge set in a graph GG. For any n3n\geq 3, the 33-token graph Γ3(Pn)\Gamma_3(P_n) satisfies

Maximum independent edge set conjecture.

α(Γ3(Pn))={k=1n21(i=12k1i)+i=1n21i,if n is even,k=1n121(i=12ki)+i=1n121i,if n is odd,\alpha'(\Gamma_3(P_n)) = \begin{cases} \displaystyle \sum_{k=1}^{\frac{n}{2}-1} \left(\sum_{i=1}^{2k-1} i \right)+ \sum_{i=1}^{\frac{n}{2}-1} i, & \text{if } n \text{ is even},\\[6pt] \displaystyle \sum_{k=1}^{\frac{n-1}{2}-1} \left(\sum_{i=1}^{2k} i \right)+ \sum_{i=1}^{\frac{n-1}{2}-1} i, & \text{if } n \text{ is odd}, \end{cases}

and equivalently

α(Γ3(Pn))={n33n2+2n12,if n is even,n33n2n+312,if n is odd.\alpha'(\Gamma_3(P_n)) = \begin{cases} \displaystyle \frac{n^3-3n^2+2n}{12}, & \text{if } n \text{ is even},\\[6pt] \displaystyle \frac{n^3-3n^2-n+3}{12}, & \text{if } n \text{ is odd}. \end{cases}

The conjecture asserts that the displayed independent edge sets are maximum. The proposed formulas are based on explicit constructions for even and odd nn; determining whether these constructions are largest remains an open problem for the 33-token graphs of path graphs.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Felicia Servina Djuang, Arizka Yuliana, Widi Bagaskara and Yeni Susanti, “Exploring the 3-Token Graph of Particular Graphs”, arXiv:2511.10875 (2025).

Additional references

2 papers in this index state this conjecture (2021–2025). The statement above is taken from the most recent of them; the others are arXiv:2107.00295.

Solutions 0

No solutions have been posted yet.