Article ID Journal Published Year Pages File Type
4647335 Discrete Mathematics 2015 8 Pages PDF
Abstract
Let H be a multigraph, possibly with loops, and consider a set S⊆V(H). A (simple) graph G is (H,S)-semi-linked if, for every injective map f:S→V(G), there exists an injective map g:V(H)∖S→V(G)∖f(S) and a set of |E(H)| internally disjoint paths in G connecting pairs of vertices of  f(S)∪g(V(H)∖S) for every edge between the corresponding vertices of H. This new concept of (H,S)-semi-linkedness is a generalization of H-linkedness. We establish a sharp minimum degree condition for a sufficiently large graph G to be (H,S)-semi-linked.
Keywords
Related Topics
Physical Sciences and Engineering Mathematics Discrete Mathematics and Combinatorics
Authors
, , ,