The 2‐intersection number of paths and bounded‐degree trees
Michael S. Jacobson, André E. Kézdy, Douglas B. West · Journal of Graph Theory · 1995
Abstract 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 (t2 ‐ 19t + 4)/4 and (t2 ‐ t + 6)/4, making θ2(Pn) 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) > .945n2/3. © 1995 John Wiley & Sons, Inc.