THE 2-INTERSECTION NUMBER OF PATHS AND BOUNDED-DEGREE TREES

We represent a graph by assigning each vertex a finite set such that v ertices are adjacent if and only if the corresponding sets have at lea st two common elements. The 2-intersection number theta(2)(G) of a gra ph G is the minimum size of the union of sets in such a representation . We prove that the maximum order of a path that can be represented in this way using telements is between (t(2) - 19t + 4)/4 and (t(2) - t + 6)/4, making theta(2)(P-n) asymptotic to 2 root n. We also show the existence of a constant c depending on epsilon such that, for any tree T with maximum degree at most d, theta(2)(T) less than or equal to c( root(n))(1+epsilon). When the maximum degree is not bounded, there is an n-vertex tree T with theta(2)(T) > .945n(2/3). (C) 1995 John Wiley & Sons, Inc.