2019/06/21 by Runrun Liu, Liu, Runrun, Martin Rolek +3 · 1 citation
Computer Science · #Optimization and Search Problems #Advanced Graph Theory Research #Computational Geometry and Mesh Generation
paper · pdf · doi:10.48550/arxiv.1906.09197
For a multigraph H, a graph G is H-linked if every injective mapping ϕ: V(H)→ V(G) can be extended to an H-subdivision in G. We study the minimum connectivity required for a graph to be H-linked. A k-fat-triangle Fk is a multigraph with three vertices and a total of k edges. We determine a sharp connectivity requirement for a graph to be Fk-linked. In particular, any k-connected graph is Fk-linked when Fk is connected. A kite is the graph obtained from K4 by removing two edges at a vertex. As a nontrivial application of Fk-linkage, we then prove that every 8-connected graph is kite-linked, which shows that the required connectivity for a graph to be kite-linked is 7 or 8.