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

About 5 years old · traced to

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 n≥3n\geq 3, the 33-token graph Γ3(Pn)\Gamma_3(P_n) satisfies

Maximum independent edge set conjecture.

α′(Γ3(Pn))={∑k=1n2−1(∑i=12k−1i)+∑i=1n2−1i,if n is even,∑k=1n−12−1(∑i=12ki)+∑i=1n−12−1i,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))={n3−3n2+2n12,if n is even,n3−3n2−n+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.

References

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.

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.