✦ LIBER ✦

On the euclidean dimension of a complete multipartite graph

✍ Scribed by Hiroshi Maehara

Publisher: Elsevier Science
Year: 1988
Tongue: English
Weight: 272 KB
Volume: 72
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(88)90217-8

No coin nor oath required. For personal study only.

✦ Synopsis

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 with vertex-classes consisting of s sets of size 1, I sets of size 2, and u sets of size 23. We prove that e(G)=s+t+2u

if t+us2, and e(G)=s+t+2u-1 if t+uc1.

📜 SIMILAR VOLUMES

On path factorizations of complete multi

On path factorizations of complete multipartite graphs

✍ Min-li Yu 📂 Article 📅 1993 🏛 Elsevier Science 🌐 English ⚖ 523 KB

## Necessary conditions for IK(n, r), the complete multipartite graph with r parts of size n in which each edge has multiplicity 1, to have a P,-factorization are nr=O(mod k) and i(r-l)kn=O(mod2(k-1)). We show that when n=O(modk) or r=O(modk), these two conditions are also sufficient. (This impli

The chromatic index of complete multipar

The chromatic index of complete multipartite graphs

✍ D. G. Hoffman; C. A. Rodger 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 266 KB

## Abstract We show that a complete multipartite graph is class one if and only if it is not eoverfull, thus determining its chromatic index.

The diameter of an orientation of a comp

The diameter of an orientation of a complete multipartite graph

✍ K.M. Koh; B.P. Tan 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 390 KB

For a graph G, let e(G) denote the minimum value of the diameters diamD of D, where D runs through all the orientations of G. In this paper, we obtain some results on e(G) for complete multipartite graphs G, which extend some known results due to Boesch and Tindell [1] and Maurer [4].

On minimum sets of 1-factors covering a

On minimum sets of 1-factors covering a complete multipartite graph

✍ David Cariolaro; Hung-Lin Fu 📂 Article 📅 2008 🏛 John Wiley and Sons 🌐 English ⚖ 132 KB 👁 1 views

## Abstract We determine necessary and sufficient conditions for a complete multipartite graph to admit a set of 1‐factors whose union is the whole graph and, when these conditions are satisfied, we determine the minimum size of such a set. © 2008 Wiley Periodicals, Inc. J Graph Theory 58:239‐250,

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 achromatic indices of the regular co

The achromatic indices of the regular complete multipartite graphs

✍ Nam-Po Chiang; Hung-Lin Fu 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 272 KB

In this paper, we study the achromatic indices of the regular complete multipartite graphs and obtain the following results: (1) A good upper bound for the achromatic index of the regular complete multipartite graph which gives the exact values of an infinite family of graphs and solves a problem p