Commuting graphs and their generalized complements.

In this paper we consider a graph G, a partition P = [V1, V2, ..., Vk} of V (G) and the generalized complements GkP and Gk(i)P with respect to the partition P. We derive conditions to be satisfied by P so that G commutes with its generalized complements. Apart from the general characterization, we also obtain conditions on P = [V1, V2, ...,Vk} so that G commutes with its generalized complements for certain classes of graphs namely complete graphs, cycles and generalized wheels. In the process we obtain a commuting decomposition of regular complete k-partite graph ... in terms of a Hamiltonian cycle and its k-complement. We also get a commuting decomposition of a complete k-partite graph ... in terms of a generalized wheel and its k-complement, where n1, n2, ..., nk satisfy some conditions. [ABSTRACT FROM AUTHOR]