𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the line graphs of the complete r-partite graphs

✍ Scribed by Peter Zörnig

Publisher
Elsevier Science
Year
1997
Tongue
English
Weight
184 KB
Volume
171
Category
Article
ISSN
0012-365X

No coin nor oath required. For personal study only.

✦ Synopsis

We show that the connectivities of line graphs of multipartite graphs equal the minimum valency.

I. Introduction

In order to solve degeneracy problems in linear optimization the so-called degeneracy graphs, assigned to a degenerate vertex x of the feasible solution set, have proved to be useful 11]. In the special case when the degeneracy degree ofx is 2 (i.e. two basic variables equal zero), degeneracy graphs are the line graphs of complete multipartite graphs.

To date only the line graphs of special complete multipartite graphs have been investigated [2, p. 286; 6, 8]. The present paper deals with the line graphs of general complete r-partite graphs. We derive an exact expression for the connectivities of these graphs which tum out to be equal, while results on the connectivities of graphs are usually confined to stating their lower or upper bounds .

In the following, K(pt ..... p~) denotes the graph with the partition

📜 SIMILAR VOLUMES

Total chromatic number of complete r-par
Total chromatic number of complete r-partite graphs
✍ K. H. Chew; H. P. Yap 📂 Article 📅 1992 🏛 John Wiley and Sons 🌐 English ⚖ 284 KB 👁 1 views

## Abstract Rosenfeld (1971) proved that the Total Colouring Conjecture holds for balanced complete __r__‐partite graphs. Bermond (1974) determined the exact total chromatic number of every balanced complete __r__‐partite graph. Rosenfeld's result had been generalized recently to complete __r__‐par

Two characterizations of interchange gra
Two characterizations of interchange graphs of complete m-partite graphs
✍ Curtis R. Cook 📂 Article 📅 1974 🏛 Elsevier Science 🌐 English ⚖ 564 KB

A graph G is m-partite if its points can be partitioned into m subsets Yl, . . . . Vm such that every line joins a point in Vi with a point in Vi, i + j. A complete m-partite graph contains every line joining Vi with V-. A complete graph Kp has every pair of its p points adjacent. The nth interchang

On the decomposition of Kn into complete
On the decomposition of Kn into complete m-partite graphs
✍ Qingxue Huang 📂 Article 📅 1991 🏛 John Wiley and Sons 🌐 English ⚖ 195 KB 👁 1 views

## Abstract Graham and Pollak [3] proved that __n__ −1 is the minimum number of edge‐disjoint complete bipartite subgraphs into which the edges of __K__~__n__~ can be decomposed. Using a linear algebraic technique, Tverberg [2] gives a different proof of that result. We apply his technique to show