pith. sign in

arxiv: 1206.1427 · v1 · pith:J4ABJXMVnew · submitted 2012-06-07 · 🧮 math.CO

Combined degree and connectivity conditions for H-linked graphs

classification 🧮 math.CO
keywords h-linkeddegreedeltaeveryminimumboundsconnectivityfind
0
0 comments X
read the original abstract

For a given multigraph H, a graph G is H-linked, if |G| \geq |H| and for every injective map {\tau}: V (H) \rightarrow V (G), we can find internally disjoint paths in G, such that every edge from uv in H corresponds to a {\tau} (u) - {\tau} (v) path. To guarantee that a G is H-linked, you need a minimum degree larger than |G|/2. This situation changes, if you know that G has a certain connectivity k. Depending on k, even a minimum degree independent of |G| may suffice. Let {\delta}(k, H, N) be the minimum number, such that every k-connected graph G with |G| = N and {\delta}(G) \geq {\delta}(k, H, N) is H-linked. We study bounds for this quantity. In particular, we find bounds for all multigraphs H with at most three edges, which are optimal up to small additive or multiplicative constants.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.