𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Simultaneous intersection representation of pairs of graphs

✍ Scribed by Tanenbaum, Paul J.

Publisher
John Wiley and Sons
Year
1999
Tongue
English
Weight
436 KB
Volume
32
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

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 consider several special cases and explore bounds on the size of the universal set.

πŸ“œ SIMILAR VOLUMES

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 πŸ‘ 2 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

Niche graphs and mixed pair graphs of to
Niche graphs and mixed pair graphs of tournaments
✍ Bowser, Steve; Cable, Charles; Lundgren, Richard πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 339 KB πŸ‘ 2 views

In our efforts to study the niche graph of a tournament T , we have found it easier to study the complement, which we call the ''mixed pair'' graph of T and denote MP (T ). We show that an undirected graph G is MP (T ), for some tournament T , if and only if G is one of the following: a cycle of odd

Intersection representation of digraphs
Intersection representation of digraphs in trees with few leaves
✍ Lin, In-Jen; Sen, Malay K.; West, Douglas B. πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 285 KB πŸ‘ 1 views

The leafage of a digraph is the minimum number of leaves in a host tree in which it has a subtree intersection representation. We discuss bounds on the leafage in terms of other parameters (including Ferrers dimension), obtaining a string of sharp inequalities.

Hamilton cycles in block-intersection gr
Hamilton cycles in block-intersection graphs of triple systems
✍ Peter HorΓ‘k; David A. Pike; Michael E Raines πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 336 KB πŸ‘ 2 views

Given a BIBD S = (V, B), its 1-block-intersection graph GS has as vertices the elements of B; two vertices B1, B2 ∈ B are adjacent in GS if |B1 ∩ B2| = 1. If S is a triple system of arbitrary index λ, it is shown that GS is hamiltonian.