✦ LIBER ✦

The frame dimension and the complete overlap dimension of a graph

✍ Scribed by Jeffrey E. Steif

Publisher: John Wiley and Sons
Year: 1985
Tongue: English
Weight: 715 KB
Volume: 9
Category: Article
ISSN: 0364-9024
DOI: 10.1002/jgt.3190090210

No coin nor oath required. For personal study only.

✦ Synopsis

Roberts (F. S. Roberts, On the boxicity and cubicity of a graph. In Recent Progress in Cornbinarorics, W. T. Tutte, ed. Academic, New York (1 969)), studied the intersection graphs of closed boxes (products of closed intervals) in Euclidean n-space, and introduced the concept of the boxicity of a graph G, the smallest n such that G is the intersection graph of boxes in n-space. In this paper, w e study the intersection graphs of the frames or boundaries of such boxes. We study the frame dimension of a graph G-the smallest n such that G is the intersection graph of frames in nspace. We also study the complete overlap dimension of a graph, a notion that is almost equivalent. The complete overlap dimension of a graph G is the smallest dimension in which G can be represented by boxes that intersect but are not completely contained in one another. We will prove that these dimensions are in almost all cases the same and that they both can become arbitrarily large. We shall also obtain a bound for these dimensions in terms of boxicity.

📜 SIMILAR VOLUMES

On the euclidean dimension of a complete

On the euclidean dimension of a complete multipartite graph

✍ Hiroshi Maehara 📂 Article 📅 1988 🏛 Elsevier Science 🌐 English ⚖ 272 KB

The euclidean dimension of a graph G, e(G), is the minimum n such that the vertices of G can be placed in euclidean n-space, R", in such a way that adjacent vertices have distance 1 and nonadjacent vertices have distances other than 1. Let G = K(n,, . , ns+,+J be a complete (s + t + u)-partite graph

The rotational dimension of a graph

✍ Frank Göring; Christoph Helmberg; Markus Wappler 📂 Article 📅 2010 🏛 John Wiley and Sons 🌐 English ⚖ 195 KB

The circular dimension of a graph

✍ Robert B. Feinberg 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 484 KB

A graph is a pair (V, I), V being the vertices and I being the relation of adjacency on V. Given a grqh G, then a collection of functions (fi}~ ,, each fi mapping each vertex of V into an arc on a fixed circle, is said to define an m-arc intersection model for G if for all x, y E V, xly e=, (Vi~ml(f

The divider dimension of the graph of a

The divider dimension of the graph of a function

✍ Steven R Dunbar; Rod W Douglass; W.J Camp 📂 Article 📅 1992 🏛 Elsevier Science 🌐 English ⚖ 483 KB

The vapnik-chervonenkis dimension of a r

The vapnik-chervonenkis dimension of a random graph

✍ Martin Anthony; Graham Brightwell; Colin Cooper 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 652 KB

In this paper we investigate a parameter defined for any graph, known as the Vapnik Chervonenkis dimension (VC dimension). For any vertex x of a graph G, the closed neighborhood N(x) of x is the set of all vertices of G adjacent to x, together with x. We say that a set D of vertices of G is shattere

The dimension of sums of graphs

✍ Peter Alles 📂 Article 📅 1985 🏛 Elsevier Science 🌐 English ⚖ 235 KB

For a graph G, dim G is defined to be the least natural number n such that G is an induced subgraph of a categorial (or direct) product of n complete graphs. The dimension of sums of graphs has been studied in [3] and [8]. The aim if this article is to improve the upper estimates achieved by Poljak