✦ LIBER ✦

Two characterizations of interchange graphs of complete m-partite graphs

✍ Scribed by Curtis R. Cook

Publisher: Elsevier Science
Year: 1974
Tongue: English
Weight: 564 KB
Volume: 8
Category: Article
ISSN: 0012-365X
DOI: 10.1016/0012-365x(74)90150-2

No coin nor oath required. For personal study only.

✦ Synopsis

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 interchange graph I,(G I of G is a graph whose points can be identified with the K,+l'~ of G such that two points are adjacent whenever the corresponding K,+lf have a K, in common. Interchange graphs of complete 2-partite and 3-partite graphs have been characterized, but interchange graphs of complete m-partite graphs for m > 3 do not seem to have been investigated. The main result of this paper is two characterizations of interchange graphs of complete mpartite graphs for m _> 2.

📜 SIMILAR VOLUMES

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

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

Hamiltonian decompositions of complete r

Hamiltonian decompositions of complete regular s-partite graphs

✍ A.J.W. Hilton; C.A. Rodger 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 962 KB

In this paper we give a procedure by which Hamiltonian decompositions of the s-partite graph K~.....,~, where (s-1)n is even, can be constructed. For 2t<~s, l<~al<~...<~a~n, we find conditions which are necessary and sufficient for a decomposition of the edge-set of Kal.a2..... ~ into (s-1)n/2 class

On biclique decompositions of complete t

On biclique decompositions of complete t-partite graphs

✍ Elizabeth D. Boyer; Bryan L. Shader 📂 Article 📅 1995 🏛 Elsevier Science 🌐 English ⚖ 704 KB

On balanced claw designs of complete mul

On balanced claw designs of complete multi-partite graphs

✍ Kazuhiko Ushio 📂 Article 📅 1982 🏛 Elsevier Science 🌐 English ⚖ 201 KB

In this paDer,

Characterizations of outerplanar graphs

✍ Maciej M. Sysło 📂 Article 📅 1979 🏛 Elsevier Science 🌐 English ⚖ 750 KB

The paper presents several characterizations of outerp:anar graphs, some of them are counterparts of the well-known characterizations of planar graphs and the other provide very efficient tools for outerplanarity testing, coding (i.e. isomorphism testing), and counting such graphs. Finally, we attem