Mengerian graphs: characterization and recognition
share
A temporal graph G is a graph that changes with time. More specifically, it is a pair (G, λ) where G is a graph and λ is a function on the edges of G that describes when each edge e∈ E(G) is active. Given vertices s,t∈ V(G), a temporal s,t-path is a path in G that traverses edges in non-decreasing time; and if s,t are non-adjacent, then a temporal s,t-cut is a subset S⊆ V(G)∖{s,t} whose removal destroys all temporal s,t-paths. It is known that Menger's Theorem does not hold on this context, i.e., that the maximum number of internally vertex disjoint temporal s,t-paths is not necessarily equal to the minimum size of a temporal s,t-cut. In a seminal paper, Kempe, Kleinberg and Kumar (STOC'2000) defined a graph G to be Mengerian if equality holds on (G,λ) for every function λ. They then proved that, if each edge is allowed to be active only once in (G,λ), then G is Mengerian if and only if G has no gem as topological minor. In this paper, we generalize their result by allowing edges to be active more than once, giving a characterization also in terms of forbidden structures. We additionally provide a polynomial time recognition algorithm.
READ FULL TEXT