✦ LIBER ✦

The diameter of an orientation of a complete multipartite graph

✍ Scribed by K.M. Koh; B.P. Tan

Publisher: Elsevier Science
Year: 1996
Tongue: English
Weight: 390 KB
Volume: 149
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(94)00315-a

No coin nor oath required. For personal study only.

✦ Synopsis

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

📜 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 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 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 the complete regu

The star-arboricity of the complete regular multipartite graphs

✍ Yasukazu Aoki 📂 Article 📅 1990 🏛 Elsevier Science 🌐 English ⚖ 331 KB

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

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,

Complexity of approximating the oriented

Complexity of approximating the oriented diameter of chordal graphs

✍ Fedor V. Fomin; Martín Matamala; Ivan Rapaport 📂 Article 📅 2004 🏛 John Wiley and Sons 🌐 English ⚖ 135 KB

## Abstract The oriented diameter of a bridgeless connected undirected (__bcu__) graph __G__ is the smallest diameter among all the diameters of strongly connected orientations of __G__. We study algorithmic aspects of determining the oriented diameter of a chordal graph. We (a) construct a linear‐