- Series
- Combinatorics Seminar
- Time
- Friday, November 20, 2009 - 3:05pm for 1.5 hours (actually 80 minutes)
- Location
- Skiles 255
- Speaker
- Mark Ellingham – Vanderbilt University
- Organizer
- Xingxing Yu
Linkage involves finding a set of internally disjoint paths in a graph with specified endpoints. Given graphs G and H, we say G is H-linked if for every injective mapping f:V(H) -> V(G) we can find a subgraph H' of G which is a subdivision of H, with f(v) being the vertex of H' corresponding to each vertex v of H. We describe two results on H-linkage for small graphs H.
(1) 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.
(2) Xingxing 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.
This is joint work with Michael D. Plummer and Gexin Yu.