Premium
The 2‐intersection number of paths and bounded‐degree trees
Author(s) -
Jacobson Michael S.,
Kézdy André E.,
West Douglas B.
Publication year - 1995
Publication title -
journal of graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 1.164
H-Index - 54
eISSN - 1097-0118
pISSN - 0364-9024
DOI - 10.1002/jgt.3190190403
Subject(s) - combinatorics , mathematics , bounded function , vertex (graph theory) , degree (music) , graph , tree (set theory) , discrete mathematics , intersection (aeronautics) , mathematical analysis , physics , acoustics , engineering , aerospace engineering
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.