Composition of graphs and the Hop-constrained Path Problem
Fatiha Bendali, Jean Mailfert, Xiaohu Tang · International Journal of Mathematics in Operational Research · 2012
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 st-paths of length bounded by L , denoted by DL( G) , for any graph G when L ≤ 3 , using trivial, st-cut, and L-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 ≥ 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.