✦ LIBER ✦

The star-arboricity of the complete regular multipartite graphs

✍ Scribed by Yasukazu Aoki

Publisher: Elsevier Science
Year: 1990
Tongue: English
Weight: 331 KB
Volume: 81
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(90)90142-5

No coin nor oath required. For personal study only.

✦ Synopsis

A subgraph H of a graph G is called a star-subgraph if each component of H is a star. The star-arboricify of G, denoted by sa(G), is the minimum number of star-subgraphs that partition the edges of G. In this paper we show that sa(G) is [r/21 + 1 or [r/2] + 2 for the complete r-regular multipartite graph G. And if r is even or if r is sufficiently larger than the number of partite sets, then sa(G) is [r/2] + 2.

📜 SIMILAR VOLUMES

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

The star arboricity of graphs

✍ I. Algor; N. Alon 📂 Article 📅 1989 🏛 Elsevier Science 🌐 English ⚖ 714 KB

The linear arboricity of some regular gr

The linear arboricity of some regular graphs

✍ Hikoe Enomoto; Bernard Péroche 📂 Article 📅 1984 🏛 John Wiley and Sons 🌐 English ⚖ 582 KB

W e prove that the linear arboricity of every 5-regular graph is 3. That is, the edges of any 5-regular graph are covered by three linear forests. W e also determine the linear arboricity of 6-regular graphs and 8-regular graphs. These results improve the known upper bounds for the linear arboricity

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.

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