Premium
Linkage for the diamond and the path with four vertices
Author(s) -
Ellingham M. N.,
Plummer Michael D.,
Yu Gexin
Publication year - 2012
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.20612
Subject(s) - combinatorics , injective function , mathematics , vertex (graph theory) , planar graph , subdivision , graph , discrete mathematics , archaeology , history
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