Disconnected selfcomplementary factors of almost complete tripartite graphs

Research output: Contribution to journalArticlepeer-review

1 Scopus citations

Abstract

A complete tripartite graph without one edge, K̃m1 ,m2 ,m3 , is called an almost complete tripartite graph. A graph K̃m1 ,m2 ,m3 that can be decomposed into two isomorphic factors is called halvable. It is proved that an almost complete tripartite graph is halvable into disconnected factors without isolated vertices if an only if it is a graph K̃1, 2m+1 ,2p and the "missing" (i.e., deleted) edge has the endvertices in the odd parts. It is also shown that the factors have always two components: one component is isomorphic to a star K1 ,p and the other to a graph K1 ,2m ,p - K1 ,m. For factors with isolated vertices it is proved that they have just one non-trivial component and all isolated vertices belong to the same part.

Original languageEnglish (US)
Pages (from-to)107-116
Number of pages10
JournalUtilitas Mathematica
Volume56
StatePublished - Nov 1 1999

Fingerprint

Dive into the research topics of 'Disconnected selfcomplementary factors of almost complete tripartite graphs'. Together they form a unique fingerprint.

Cite this