# 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:
  Chartrand, G.; Harary, F., Graphs with prescribed connectivities, (Theory of Graphs (Proc. Colloq., Tihany, 1966), (1968), Academic Press New York), 61-63  Chartrand, Gary; Lesniak, Linda; Zhang, Ping, Graphs & digraphs, (2011), CRC Press Boca Raton, FL · Zbl 1211.05001  Diestel, R., (Graph Theory, Graduate Texts in Mathematics, vol. 173, (2000), Springer-Verlag New York) · Zbl 0945.05002  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  Ferrara, Michael; Gould, Ronald; Tansey, Gerard; Whalen, Thor, On $$H$$-linked graphs, Graphs Combin., 22, 2, 217-224, (2006) · Zbl 1100.05055  Ferrara, M.; Magnant, C.; Powell, J., Pan-$$H$$-linked graphs, Graphs Combin., 26, 2, 225-242, (2010) · Zbl 1230.05185  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  Gould, R.; Whalen, T., Subdivision extendibility, Graphs Combin., 23, 2, 165-182, (2007) · Zbl 1115.05063  Jung, H. A., Eine verallgemeinerung des $$n$$-fachen zusammenhangs für graphen, Math. Ann., 187, 2, 95-103, (1970) · Zbl 0184.27601  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  Kostochka, Alexandr; Yu, Gexin, An extremal problem for $$H$$-linked graphs, J. Graph Theory, 50, 4, 321-339, (2005) · Zbl 1078.05042  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  Thomas, R.; Wollan, P., An improved linear edge bound for graph linkages, European J. Combin., 26, 3-4, 309-324, (2005) · Zbl 1056.05091  Douglas West, Glossary of terms in combinatorics, 2014.  Whalen, T., Degree conditions and relations to distance, extendability, and levels of connectivity in graphs, (2003), Emory University, August, (Ph.D. Thesis)