Maximising the quantity of valid 2-paths on cographs

Assigning labels to the vertices and/or edges of a given graph G=(V,E), respecting predefined conditions, is a well-known research problem in the field of Graph Theory. The labelling of a graph G, of order n, is defined as a numbering when the set of integers {1,...,n} is used to label V(G) in a distinct way . A path with three vertices (2-path) is termed valid if the label associated with its central vertex is smaller than the labels associated with the endpoints of the path. The Path Validity Problem} involves finding a numbering that optimises the quantity of valid 2-paths in G. 

The focus of this work is on the class of cographs, presenting an polynomial algorithm based on dynamic programming which maximizes the quantity of valid 2-paths in cographs. Also some interesting properties related to the problem are presented.