✦ LIBER ✦

Intersection properties of line graphs

✍ Scribed by Stanisław Bylka; Jan Komar

Book ID: 104113643
Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 515 KB
Volume: 164
Category: Article
ISSN: 0012-365X
DOI: 10.1016/s0012-365x(96)00041-6

No coin nor oath required. For personal study only.

✦ Synopsis

Each graph is an intersection graph (intersection multigraph) of a family of sets. Such a family is called a representation if all sets are different and a pseudorepresentation if some are the same. By intersection number we mean the cardinality of the smallest set on which we can construct a representation. So each graph has four intersection numbers. A graph is uniquely representable if it has only one representation on the minimal set. We take into account only triangle free graphs which are uniquely intersectable in any sense and line graphs. We show that line graphs with pendant/{4 -e and clepsydras are line graphs which are not uniquely multiple pseudointerseetable (u.m.p.i.) in the class of line graphs.

📜 SIMILAR VOLUMES

Intersection properties of graphs

✍ Terry A. McKee 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 550 KB

McKee, T.A., Intersection properties of graphs, Discrete Mathematics 89 (1991) 253-260. For each graph-theoretic property, we define a corresponding 'intersection property', motivated by the natural relationship of paths with interval graphs, and of trees with chordal graphs. We then develop a simp

Properties of spectra of graphs and line

Properties of spectra of graphs and line graphs

✍ Chen Yan 📂 Article 📅 2002 🏛 SP Editorial Committee of Applied Mathematics - A 🌐 English ⚖ 261 KB

Intersection Graphs of Segments

✍ J. Kratochvil; J. Matousek 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 998 KB

Intersection graphs of segments (the class SEG) and of other simple geometric objects in the plane are considered. The results fall into two main areas: how difficult is the membership problem for a given class and how large are the pictures needed to draw the representations. Among others, we prove

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,

Chordal intersection graphs of bands

✍ Bedřich Pondělíček 📂 Article 📅 1999 🏛 Springer 🌐 English ⚖ 354 KB

Characterizing intersection classes of g

Characterizing intersection classes of graphs

✍ Edward R. Scheinerman 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 571 KB

A graph is an intersection graph if it is possible to assign sets to its vertices so that adjacency corresponds exactly to nonempty intersection. If the sets assigned to vertices must belong to a pre-specified family, the resulting class of all possible intersection graphs is called an intersection