2019/12/05 by Chris Stephens, Stephens, Chris, Dong Ye +1
Computer Science · #Combinatorics (math.CO) #Distributed systems and fault tolerance #FOS: Mathematics #Opportunistic and Delay-Tolerant Networks #Optimization and Search Problems
paper · pdf · doi:10.48550/arxiv.1912.02873
openalex publication_date 2019/12/05 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
For a given graph H, a graph G is H-linked if, for every injection φ: V(H) → V(G), the graph G contains a subdivision of H with φ(v) corresponding to v, for each v∈ V(H). Let f(H) be the minimum integer k such that every k-connected graph is H-linked. Among graphs H with at least four vertices, the exact value f(H) is only know when H is a path with four vertices or a cycle with four vertices. A kite is graph obtained from K4 by deleting two adjacent edges, i.e., a triangle together with a pendant edge. Recently, Liu, Rolek and Yu proved that every 8-connected graph is kite-linked. 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.