On a problem of C. E. Shannon in graph theory

Abstract

2. Definitions and notations. By an independent set of vertices in a graph G we mean a subset of vertices such that no two different vertices in the subset are joined by an edge in G. The maximal number of independent vertices in a graph G will be denoted by ,i(G). A clique in a graph G is a complete subgraph of G (i.e. a set of vertices each pair of which are connected by an edge) which is not contained in any other complete subgraph of G. Ver(G) will denote the set of vertices of G. A function a: G--G will be called preserving if g-+->g' =>a(g)-+i>a(g') (where g-+->g' means that g is not joined by an edge to the vertex g'). The cartesian product of two graphs is a graph denoted by G XH defined as follows: