✦ LIBER ✦

The circular dimension of a graph

✍ Scribed by Robert B. Feinberg

Publisher: Elsevier Science
Year: 1979
Tongue: English
Weight: 484 KB
Volume: 25
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(79)90149-3

No coin nor oath required. For personal study only.

✦ Synopsis

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(fi!x)nfi(y)Zpl).

The circular dimension of a graph IG is defined as the smallest integer m such that G has an m-arc intersection model. In this paper we establish that the maximum circular dimension of any complete partite graph having n vertices is the largest integer p such that 2p + p s n + 1.

📜 SIMILAR VOLUMES

The rotational dimension of a graph

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

The frame dimension and the complete ove

The frame dimension and the complete overlap dimension of a graph

✍ Jeffrey E. Steif 📂 Article 📅 1985 🏛 John Wiley and Sons 🌐 English ⚖ 715 KB

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 gr

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 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

A note on circular dimension

✍ J.B. Shearer 📂 Article 📅 1980 🏛 Elsevier Science 🌐 English ⚖ 92 KB

In [l] Feinberg conjectures that the maximum circular dimension of all graphs having n vertices is attained by a complete partite graph. In this note we show that this is not so. In [l], Feinberg defined the circular dimension of a graph as follows: Given a graph G = (V, E), a collection of functio

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