ON THE GENERALIZED CAYLEY GRAPHS OF POWER SET RINGS AND HAMILTONIAN CYCLES

摘要

Let X be a non-empty set and R be the power set of X. Then (R, Delta, boolean AND) is a commutative ring with an identity element, where Delta is the symmetric difference. For a natural number n, Gamma(n)(R) is a graph with vertex set R-n{0} and two distinct vertices Y and Z are adjacent if and only if there exists a lower triangular matrix A = [A(i)(j)](n x n) over R such that, for each i with 1 = i = n, A(ii) not equal 0(R) and also AY(T) = Z(T) or AZ(T) = Y-T, where, for a matrix B, B-T is the matrix transpose of B. In this paper we show that if vertical bar X vertical bar = 2, for each natural number n, the graph Gamma(n)(R) has a Hamiltonian cycle except the case that vertical bar X vertical bar = 2 and n = 1. Also we investigate the clique number of Gamma(n)(R). Moreover we obtain a suitable bound for the independence number of Gamma(n)(R).