Linkage for the diamond and the path with four vertices
Mark N. Ellingham, Michael D. Plummer, Gexin Yu · Journal of Graph Theory · 2011
Abstract Given graphs G and H , we say G is H ‐ linked if for every injective mapping ℓ: V ( H )→ V ( G ), we can find a subgraph H ′ of G that is a subdivision of H with ℓ( v ) being the vertex of H ′ corresponding to each vertex v of H . In this article, we prove two results on H ‐linkage for 4‐vertex graphs H . Goddard showed that 4‐connected planar triangulations are 4‐ordered, or in other words C 4 ‐linked. We strengthen this by showing that 4‐connected planar triangulations are ( K 4 − e )‐linked. X. Yu characterized certain graphs related to P 4 ‐linkage. We use his characterization to show that every 7‐connected graph is P 4 ‐linked, and to construct 6‐connected graphs that are not P 4 ‐linked. © 2011 Wiley Periodicals, Inc. J Graph Theory