Valid Paths, a short synthesis

• Gustavo M. Leal UFG
• Hebert C. Silva UFG
• Humberto J. Longo UFG
• Les R. Foulds UFG

DOI: https://doi.org/10.5753/etc.2024.2539

Abstract

A labeling of a graph is an assignment of labels to its vertices and/or edges. The Path Validity Problem seeks to optimise the quantity of 2-paths with the integer label associated with the middle vertex being smaller than those associated with the path endpoints. Recent research has investigated the behaviour of optimal labeling in several classes of graphs. This work provides a summary overview of recent advances in the study of this challenging problem and presents that the decision problem of its maximising variant is NP-Complete, while its minimising variant remains an open problem.

References

Dias, E. S., Castonguay, D., Longo, H. J., and Jradi, W. A. R. (2013). Efficient enumeration of all chordless cycles in graphs. CoRR, abs/1309.1051.

Foulds, L. and Longo, H. J. (2023). Valid path-based graph vertex numbering. arXiv eprint 2306.02200.

Gallian, J. A. (2023). A dynamic survey of graph labeling. The Electronic Journal of Combinatorics. Twenty-sixth edition, edition, #DS6.

Krishnamoorthy, M. S. and Deo, N. (1979). Node-deletion np-complete problems. SIAM Journal on Computing, 8(4):619–625.

Leal, G. (2024). Valid path numberings in some graph classes. Master’s thesis, Universidade Federal de Goiás. Master’s thesis currently in development.

Leal, G., Longo, H. J., Coelho, H., and Foulds, L. (2023). Valid path numberings in circulant graphs. Anais do Simpósio Brasileiro de Pesquisa Operacional.

Rosa, A. (1967). On certain valuations of the vertices of a graph. In Theory of Graphs (Internat. Symposium, Rome, 1966), pages 349–355. Gordon and Breach, N. Y. and Dunod Paris.