Skip to main content
Article
On Large Semi-Linked Graphs
Discrete Mathematics
  • Alexander Halperin, Salisbury University
  • Colton Magnant, Georgia Southern University
  • Hua Wang, Georgia Southern University
Document Type
Article
Publication Date
1-1-2015
DOI
10.1016/j.disc.2014.08.022
Disciplines
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 inG 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.

Citation Information
Alexander Halperin, Colton Magnant and Hua Wang. "On Large Semi-Linked Graphs" Discrete Mathematics Vol. 338 Iss. 1 (2015) p. 122 - 129 ISSN: 0012-365X
Available at: http://works.bepress.com/hua_wang/92/