✦ LIBER ✦

Set intersection representations for almost all graphs

✍ Scribed by Eaton, Nancy; Grable, David A.

Publisher: John Wiley and Sons
Year: 1996
Tongue: English
Weight: 581 KB
Volume: 23
Category: Article
ISSN: 0364-9024
DOI: 10.1002/(sici)1097-0118(199611)23:3<309::aid-jgt11>3.0.co;2-9

No coin nor oath required. For personal study only.

✦ Synopsis

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 represented using the rule that two vertices are adjacent if and only if they share a t least k labels, there exist positive constants Ck and ck such that almost every graph G on n vertices satisfies

Changing the representation only slightly by defining Oodd(G) to be the minimum number of labels with which G can be represented using the rule that two vertices are adjacent if and only if they share an odd number of labels results in quite different behavior. Namely, almost every graph G satisfies

📜 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

Almost All 3-Connected Graphs Contain a

Almost All 3-Connected Graphs Contain a Contractible Set of k Vertices

✍ Matthias Kriesell 📂 Article 📅 2001 🏛 Elsevier Science 🌐 English ⚖ 223 KB

McCuaig and Ota conjectured that every sufficiently large 3-connected graph G contains a connected subgraph H on k vertices such that G&V(H) is 2-connected. We prove the weaker statement that every sufficiently large 3-connected graph G contains a not necessarily connected subgraph H on k vertices s