Caterpillar tolerance representations of graphs.

摘要

A caterpillar, H, is a tree containing a path, P, such that every vertex of H is either in P or adjacent to P. Given a graph G, a caterpillar tolerance representation of tolerance t on a caterpillar H, is a mapping of each vertex v ∈ V(G) to a subtree Hv ⊆ H, such that uv ∈ E( G) if and only if Hu and H v share at least t vertices.; Denote by cat[h,t] the set of all graphs for which there exists a tolerance t representation of G in a caterpillar of maximum degree h. Given any positive integers, h and t, it is determined for all values of n whether or not a caterpillar tolerance representations exists for a cycle of length n using a representing caterpillar of maximum degree h and tolerance t.; We show equivalence among various classes including cat[3,1] = cat[h,1] = cat[3,2] for h ≥ 3 and cat[4,2] = cat[3,3]. Also, for h ≥ 5 we show that cat[h,2] ⊊︀ cat[h - 1,3].; A vertex, v, in a graph, G, is called simplicial if the set of neighbors of v induces a clique in G. We say that a graph G has an asimplicial asteroidal triple if there exists in G three distinct vertices v1, v2,v3, none of which are simplicial, and such that for all permutations i, j, k of the indices 1,2,3 there exits a vivj path which is distance at least two from vk. We provide the characterization of cat[3,1] as the set of all chordal graphs that do not contain an asimplicial asteroidal triple. And since cat[3,1] = cat[h,1] = cat[3,2] for h ≥ 3, we get characterizations for them as well.