Originators: Ping Hu (presented by Ping Hu - REGS 2010)
Definitions: Given a graph H with vertices w1,...,wm, a graph G with at least m vertices is H-linked if for every choice of vertices v1,...,vm in G, there is a subdivision of H in G such that for all i, vi is the branch vertex representing wi.
Background: Liu, West, and Yu [LWY] showed that if a graph H is obtained from a graph H' by deleting an edge xy and introducing a new vertex u adjacent only to y, then every H-linked graph is also H'-linked. In other words, if H' is obtained from H by merging a vertex u of degree 1 into another vertex x, then every H-linked graph is also H'-linked.
Question 1: Suppose that u has degree 2 in H and v has distance at least 3 from u. Obtain H' from H by merging u into v. Does H-linked imply H'-linked?
Question 2: The same as Question 1 but with u and v both required to have degree 2.
Results: Hehui Wu gave a conterexample to Question 2, thereby showing that the answer is "no" to both questions. Construct H by adding vertices u and v to Kn, each having two neighbors in Kn but no common neighbors. The graph H' consists of Kn plus one vertex of degree 4. Let G be the join of Km with the complement of Kn+1, where m=n(n-1)/2+3.
The graph G is H-linked but not H'-linked. To see that G is not H'-linked, map all n+1 vertices of H' to the low-degree vertices in G. All edges must map to paths having an internal vertex in Km. However the number of edges in H' is n(n-1)/2+4, which equals m+1. On the other hand, H has n+2 vertices, so one of its vertices must be mapped to a vertex of Km. Its incident edges map into paths of length 1, and there remain enough other vertices in Km to lay out the other edges.
References:
[LWY] Qi Liu, Douglas B. West, and Gexin Yu, Implications among linkage
properties in graphs, J. Graph Theory (2009) vol. 60 (4) pp. 327-337