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.
05C07 Vertex degrees
05C35 Extremal problems in graph theory
Full Text: DOI
[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)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.