✦ LIBER ✦

The dimension of sums of graphs

✍ Scribed by Peter Alles

Publisher: Elsevier Science
Year: 1985
Tongue: English
Weight: 235 KB
Volume: 54
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(85)90083-4

No coin nor oath required. For personal study only.

✦ Synopsis

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 and R6dl for sums of complete graphs which then leads to an estimate for sums of arbitrary graphs. The basic idea is the application of matrices with the so-called covering property. This is equivalent to the notion of orthogonal arrays with permutation property which was introduced by Poljak and R6dl.

📜 SIMILAR VOLUMES

Graphs omitting sums of complete graphs

✍ Cherlin, Gregory; Shi, Niandong 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 119 KB 👁 2 views

For every finite m and n there is a finite set {G 1 , . . . , G l } of countable (m • K n )-free graphs such that every countable (m • K n )-free graph occurs as an induced subgraph of one of the graphs G i .

Split dimension of graphs

✍ Arkady A. Chernyak; Zhanna A. Chernyak 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 380 KB

## Chernyak, A.A. and Z.A. Chernyak, Split dimension of graphs, Discrete Mathematics 89 (1991) l-6.

Sum Multicoloring of Graphs

✍ Amotz Bar-Noy; Magnús M. Halldórsson; Guy Kortsarz; Ravit Salman; Hadas Shachnai 📂 Article 📅 2000 🏛 Elsevier Science 🌐 English ⚖ 176 KB

Scheduling dependent jobs on multiple machines is modeled by the graph multicoloring problem. In this paper we consider the problem of minimizing the average completion time of all jobs. This is formalized as the sum multicoloring problem: Given a graph and the number of colors required by each vert

Selberg-Jack Character Sums of Dimension

Selberg-Jack Character Sums of Dimension 2

✍ R.J. Evans 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 295 KB

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