# zbMATH — the first resource for mathematics

On large semi-linked graphs. (English) Zbl 1302.05036
Summary: Let $$H$$ be a multigraph, possibly with loops, and consider a set $$S \subseteq V(H)$$. A (simple) graph $$G$$ is $$(H, S)$$-semi-linked if, for every injective map $$f : S \to V(G)$$, there exists an injective map $$g : V(H) \setminus S \to V(G) \setminus f(S)$$ and a set of $$| E(H) |$$ internally disjoint paths in $$G$$ connecting pairs of vertices of $$f(S) \cup g(V(H) \setminus 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.
##### MSC:
 05C07 Vertex degrees 05C35 Extremal problems in graph theory
##### Keywords:
 [1] Chartrand, G.; Harary, F., Graphs with prescribed connectivities, (Theory of Graphs (Proc. Colloq., Tihany, 1966), (1968), Academic Press New York), 61-63 [2] Chartrand, Gary; Lesniak, Linda; Zhang, Ping, Graphs & digraphs, (2011), CRC Press Boca Raton, FL · Zbl 1211.05001 [3] Diestel, R., (Graph Theory, Graduate Texts in Mathematics, vol. 173, (2000), Springer-Verlag New York) · Zbl 0945.05002 [4] Ferrara, M.; Gould, R.; Jacobson, M.; Pfender, F.; Powell, J.; Whalen, T., New ore-type conditions for $$H$$-linked graphs, J. Graph Theory, 71, 69-77, (2012) · Zbl 1248.05107 [5] Ferrara, Michael; Gould, Ronald; Tansey, Gerard; Whalen, Thor, On $$H$$-linked graphs, Graphs Combin., 22, 2, 217-224, (2006) · Zbl 1100.05055 [6] Ferrara, M.; Magnant, C.; Powell, J., Pan-$$H$$-linked graphs, Graphs Combin., 26, 2, 225-242, (2010) · Zbl 1230.05185 [7] Gould, R.; Kostochka, A.; Yu, G., On minimum degree implying that a graph is $$H$$-linked, SIAM J. Discrete Math., 20, 4, 829-840, (2006) · Zbl 1127.05059 [8] Gould, R.; Whalen, T., Subdivision extendibility, Graphs Combin., 23, 2, 165-182, (2007) · Zbl 1115.05063 [9] Jung, H. A., Eine verallgemeinerung des $$n$$-fachen zusammenhangs für graphen, Math. Ann., 187, 2, 95-103, (1970) · Zbl 0184.27601 [10] Kawarabayashi, Ken-ichi; Kostochka, Alexandr; Yu, Gexin, On sufficient degree conditions for a graph to be $$k$$-linked, Combin. Probab. Comput., 15, 5, 685-694, (2006) · Zbl 1109.05061 [11] Kostochka, Alexandr; Yu, Gexin, An extremal problem for $$H$$-linked graphs, J. Graph Theory, 50, 4, 321-339, (2005) · Zbl 1078.05042 [12] Kostochka, Alexandr; Yu, Gexin, Minimum degree conditions for $$H$$-linked graphs, General Theory of Information Transfer and Combinatorics, Discrete Appl. Math., 156, 9, 1542-1548, (2008) · Zbl 1144.05039 [13] Thomas, R.; Wollan, P., An improved linear edge bound for graph linkages, European J. Combin., 26, 3-4, 309-324, (2005) · Zbl 1056.05091 [14] Douglas West, Glossary of terms in combinatorics, 2014. [15] Whalen, T., Degree conditions and relations to distance, extendability, and levels of connectivity in graphs, (2003), Emory University, August, (Ph.D. Thesis)