𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Cross-intersecting couples of graphs

✍ Scribed by Emanuela Fachini; János Körner

Publisher
John Wiley and Sons
Year
2007
Tongue
English
Weight
134 KB
Volume
56
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Two graphs on the same vertex set form a cross‐intersecting couple if they have a pair of clique coverings with the property that every pair of cliques from the respective coverings intersect. In particular, a graph is called normal if it forms a cross‐intersecting couple with its complement. We determine the largest size of families of graphs every pair of which forms a cross‐intersecting couple under various additional restrictions. © 2007 Wiley Periodicals, Inc. J Graph Theory 56: 105–112, 2007

📜 SIMILAR VOLUMES

Intersections of graphs
Intersections of graphs
✍ Béla Bollobás; Alex Scott 📂 Article 📅 2011 🏛 John Wiley and Sons 🌐 English ⚖ 193 KB

Let G and H be two graphs of order n. If we place copies of G and H on a common vertex set, how much or little can they be made to overlap? The aim of this article is to provide some answers to this question, and to pose a number of related problems. Along the way, we solve a conjecture of Erd" os,

Extremal Graphs for Intersecting Triangl
Extremal Graphs for Intersecting Triangles
✍ P. Erdos; Z. Furedi; R.J. Gould; D.S. Gunderson 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 400 KB

It is known that for a graph on \(n\) vertices \(\left\lfloor n^{2} / 4\right\rfloor+1\) edges is sufficient for the existence of many triangles. In this paper, we determine the minimum number of edges sufficient for the existence of \(k\) triangles intersecting in exactly one common vertex. C 1995

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

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

Intersections of longest cycles in grid
Intersections of longest cycles in grid graphs
✍ Menke, B.; Zamfirescu, T.; Zamfirescu, C. 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 292 KB 👁 3 views

It is well-known that the largest cycles of a graph may have empty intersection. This is the case, for example, for any hypohamiltonian graph. In the literature, several important classes of graphs have been shown to contain examples with the above property. This paper investigates a (nontrivial) cl

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