𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Onp-intersection representations

✍ Scribed by Eaton, Nancy; Gould, Ronald J.; R�dl, Vojtech

Publisher
John Wiley and Sons
Year
1996
Tongue
English
Weight
695 KB
Volume
21
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

For a graph G = (V, E) and integer p, a p-intersection representation is a family = {Sx: x E V} of subsets of a set S with the property that IS, n S, , l 2 p -{u, u } E E.

It is conjectured in 111 that 8,(G) I B(K,,/2,,,/2)(1 + o(1)) holds for any graph with n vertices. This is known to be true for p = 1 by [41. In [I], O(K,,/2,,,/2) 1 (n2 + (2pl)n)/4p is proved for any n and p. Here, w e show that this is asymptotically best possible.

Further, w e provide a bound on 8,(G) for all graphs with bounded degree. In particular, w e prove O,(G) 5 O(nl/P) for any graph G with the maximum degree bounded by a constant.

Finally, w e also investigate the value of 8 , for trees. Improving on an earlier result of M. Jacobson, A. Kezdy, and D. West, (The 2-intersection number of paths and bounded-degree trees, preprint), w e show that 62(T) 5 O ( d f i ) for any tree T with maximum degree dand @ ( r ) 5 O(n3'4) for any tree on n vertices. We conjecture that our result can be further improved and that & ( T ) I O(&$ as long as A(r) 5 , h . If this conjecture is true, our method gives &(T) I O(n2l3) for any tree Twhich would be the best possible.

📜 SIMILAR VOLUMES

On set intersection representations of g
On set intersection representations of graphs
✍ Stasys Jukna 📂 Article 📅 2009 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB 👁 1 views

## Abstract 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

Set intersection representations for alm
Set intersection representations for almost all graphs
✍ Eaton, Nancy; Grable, David A. 📂 Article 📅 1996 🏛 John Wiley and Sons 🌐 English ⚖ 581 KB

Two variations of set intersection representation are investigated and upper and lower bounds on the minimum number of labels with which a graph may be represented are found that hold for almost all graphs. Specifically, if &(G) is defined to be the minimum number of labels with which G may be repre

On intersection representations of co-pl
On intersection representations of co-planar graphs
✍ Jan Kratochvíl; Aleš Kuběna 📂 Article 📅 1998 🏛 Elsevier Science 🌐 English ⚖ 221 KB

We show that complements of planar graphs have intersection representations by convex sets in the plane, i.e., for every planar graph, one can assign convex sets in the plane to its vertices in such a way that two of the sets are disjoint if and only if the correspondning vertices are adjacent. This

Simultaneous intersection representation
Simultaneous intersection representation of pairs of graphs
✍ Tanenbaum, Paul J. 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 436 KB 👁 2 views

We characterize the pairs (G 1 , G 2 ) of graphs on a shared vertex set that are intersection polysemic: those for which the vertices may be assigned subsets of a universal set such that G 1 is the intersection graph of the subsets and G 2 is the intersection graph of their complements. We also cons

Intersection Representation of Complete
Intersection Representation of Complete Unbalanced Bipartite Graphs
✍ Nancy Eaton 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 282 KB

A p-intersection representation of a graph G is a map, f, that assigns each vertex a subset of [1, 2, ..., t] The symbol % p (G) denotes this minimum t such that a p-intersection representation of G exists. In 1966 Erdo s, Goodman, and Po sa showed that for all graphs G on 2n vertices, % 1 (G) % 1