Composition of graphs and the hop-constrained path problem (Q1758872)

Summary: Given a graph \(G = (V,E)\) and a non negative cost function on edges, the Hop-constrained Path Problem (HPP) consists of finding between two distinguished vertices \(s\) and \(t\) of \(V\) a minimum cost path with no more than \(L\) edges where \(L\) is a fixed integer. Dahl characterised the dominant of the convex hull of the incidence vectors of \textit{st}-paths of length bounded by \(L\), denoted by \(D_L(G)\), for any graph \(G\) when \(L \leq 3\), using \textit{trivial}, \textit{st-cut}, and \(L\)-\textit{path-cut} inequalities. A graph \(G\) is said \(L\)-h-simple if the set of Dahl's inequalities is sufficient to define \(D_L(G)\). In this paper, we study the \(L\)-h-simple property when \(L \geq 4\). We present some results on the facial structure of the dominant \(D_L(G)\). We also examine some basic operations on graphs which preserve the \(L\)-h-simple property.