On large semi-linked graphs |
| |
Authors: | Alexander Halperin Colton Magnant Hua Wang |
| |
Institution: | 1. Department of Mathematics and Computer Science, Salisbury University, 1101 Camden Ave., Salisbury, MD 21804, United States;2. Department of Mathematical Sciences, Georgia Southern University, 65 Georgia Ave., Room 3008, P.O. Box 8093, Statesboro, GA 30460, United States |
| |
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: | Graph linkedness Minimum degree |
本文献已被 ScienceDirect 等数据库收录! |
|