Abstract | ||
---|---|---|
For a given graph H, a graph G is H-linked if, for every injection phi : V (H) -> V (G), the graph G contains a subdivision of H with phi(v) corresponding to v for each v \in V (H). Let f(H) be the minimum integer k such that every k-connected graph is H-linked. Among connected simple graphs H with at least four vertices, the exact value f(H) is only known when H is a star, or a path with four vertices, or a cycle with four vertices. A kite is the graph obtained from K-4 by deleting two adjacent edges, i.e., a triangle together with a pendant edge. The exact value of f(H) when H is the kite remains open. In this paper, we settle this problem by showing that every 7-connected graph is kite-linked. |
Year | DOI | Venue |
---|---|---|
2021 | 10.1137/19M130282X | SIAM JOURNAL ON DISCRETE MATHEMATICS |
Keywords | DocType | Volume |
k-linkage, H-linkage, connectivity | Journal | 35 |
Issue | ISSN | Citations |
1 | 0895-4801 | 0 |
PageRank | References | Authors |
0.34 | 0 | 5 |
Name | Order | Citations | PageRank |
---|---|---|---|
Runrun Liu | 1 | 8 | 5.29 |
Martin Rolek | 2 | 0 | 1.01 |
D. Christopher Stephens | 3 | 19 | 3.93 |
Dong Ye | 4 | 20 | 8.36 |
Gexin Yu | 5 | 340 | 40.11 |