Malaysian Journal of Mathematical Sciences, January 2018, Vol. 12, No. 1
Commuting graphs and their generalized complements
Bhat, K. A and Sudhakara, G.
Corresponding Email: sudhakaraadiga@yahoo.co.in
Received date: 4 April 2017
Accepted date: 15 January 2018
Abstract:
In this paper we consider a graph \(G\), a partition \(P = \left \{V_1,V_2,...,V_k\right \}\) of \(V(G)\) and the generalized complements \(G_{k}^{P}\) and (G_{k(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 = \left \{V_1,V_2,...,V_k\right \}\) 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 \(K_{n_1,n_2,...,n_k}\) in terms of a Hamiltonian cycle and its complement. We also get a commuting decomposition of a complete \(k\)-partite graph \(K_{n_1,n_2,...,n_k}\) in terms of a generalized wheel and its \(k\)-complement, where \(n_1,n_2,...,n_k\) satisfy some conditions.
Keywords: Adjacency matrix, Graphical, Matrix product, k- complement, k(i)-complement, Commutativity, Graph decomposition
Indexing
