A Polynomial Representation and a Unique Code of a Simple Undirected Graph

We introduce a representation of simple undirected graphs in terms of polynomials and obtain a unique code for a simple undirected graph. 1. Introduction Let be the set of all positive integers greater than 1. Let and be the set of all divisors of , greater than 1. Define a simple undirected graph with the vertex set and any two distinct vertices are adjacent if and only if . From an observation in [1], it follows that any simple undirected graph is isomorphic to an induced subgraph of for some . For the sake of completeness and further use of the construction we provide a sketch of the proof below. Throughout the paper by a graph, we mean a simple undirected graph. Theorem 1. Let be a graph. Then is isomorphic to an induced subgraph of for some . Proof. Let be a graph. Let be the set of all maximal cliques of . For , let be the th prime. For each , define . Now in order to make the values of distinct for distinct vertices, we modify by using different powers of primes , if required. For each , let be the modified value of . Let be the least common multiple of . Now it is clear that for any , ？Thus, is isomorphic to the subgraph of induced by the set of vertices of . Example 2. Consider the graph in Figure 1. The maximal cliques of are , , , , and . We assign the th prime to the clique for . Then for each , we compute and as in the proof of Theorem 1 (Table 1). So is isomorphic to the subgraph of induced by the set of vertices of , where . Table 1 Figure 1: The graph in Example 2. 2. Main Results It is important to note that instead of taking all maximal cliques of in Theorem 1, it is sufficient to consider a set of cliques of which covers both vertices and edges of . Definition 3. Let be a graph. A set of cliques of is called a total clique covering of if covers both and . The minimum size of a total clique covering of is called the total clique covering number of . We denote it by . On the other hand, given a finite sequence of positive integers, one can construct a simple undirected graph as follows. Definition 4. Let be a finite sequence of positive integers. Then corresponding to this sequence, define a graph , where , corresponds to ( is called the label of ) for , and if and only if and . The graph is said to be realized by the sequence . Now by Theorem 1, every graph can be realized by some sequence of positive integers. Also in Definition 4, it is sufficient to take the entries of square-free if . Thus, for convenience, we specify the sequence in the following manner. Definition 5. Let be a graph. Let , and let the graph be obtained from by