Premium
On set intersection representations of graphs
Author(s) -
Jukna Stasys
Publication year - 2009
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.20367
Subject(s) - combinatorics , mathematics , bipartite graph , discrete mathematics , intersection graph , strongly regular graph , graph , line graph , graph power
The intersection dimension of a bipartite graph with respect to a type L is the smallest number t for which it is possible to assign sets A x ⊆{1, …, t } of labels to vertices x so that any two vertices x and y from different parts are adjacent if and only if | A x ∩ A y |∈ L . The weight of such a representation is the sum Σ x | A x | over all vertices x . We exhibit explicit bipartite n × n graphs whose intersection dimension is (i) at least n 1 /| L | with respect to any type L , (ii) at least $\sqrt{n}$ with respect to any type of the form L ={ k, k + 1, …}, and (iii) at least n 1 /| R | with respect to any type of the form L ={ k | k modp ∈ R }, where p is a prime number. We also show that any intersection representation of a Hadamard graph must have weight about n lnn / ln lnn , independent on the used type L . Finally, we formulate several problems about intersection dimensions of graphs related to some basic open problems in the complexity of boolean functions. © 2009 Wiley Periodicals, Inc. J Graph Theory 61: 55‐75, 2009