The 2‐intersection number of paths and bounded‐degree trees

We represent a graph by assigning each vertex a finite set such that vertices are adjacent if and only if the corresponding sets have at least two common elements. The 2‐intersection number θ 2 ( G ) of a graph 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 t elements is between ( t 2 ‐ 19 t + 4)/4 and ( t 2 ‐ t + 6)/4, making θ 2 ( P n ) asymptotic to 2√n. We also show the existence of a constant c depending on ϵ such that, for any tree T with maximum degree at most d , θ 2 ( T ) ≤ c (√n) 1+ϵ . When the maximum degree is not bounded, there is an n ‐vertex tree T with θ 2 ( T ) > .945 n 2/3 . © 1995 John Wiley & Sons, Inc.