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

Authors: Shamik Ghosh; Raibatak Sen Gupta; M. K. Sen
Journal: ISRN Combinatorics
 (2013)

---

## Abstract

We introduce a representation of simple undirected graphs in terms of polynomials and obtain a unique code for a simple undirected graph.


---

## Body

## 1. Introduction

LetM be the set of all positive integers greater than 1. Let n∈M and V(n) be the set of all divisors of n, greater than 1. Define a simple undirected graph G(n)=(V,E) with the vertex set V=V(n) and any two distinct vertices a,b∈V are adjacent if and only if gcd(a,b)>1. From an observation in [1], it follows that any simple undirected graph is isomorphic to an induced subgraph of G(n) for some n∈M. 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.
LetG be a graph. Then G is isomorphic to an induced subgraph of G(n) for some n∈M.Proof.
LetG=(V,E) be a graph. Let {C1,C2,…,Ck} be the set of all maximal cliques of G. For i=1,2,…,k, let pi be the ith prime. For each v∈V, define s1(v)=∏‍{pj|v∈Cj}. Now in order to make the values of s1(v) distinct for distinct vertices, we modify s1(v) by using different powers of primes pj, if required. For each v∈V, let s(v) be the modified value of s1(v). Let n be the least common multiple of {s(v)|v∈V}. Now it is clear that for any u,v∈V,
(1)uisadjacenttovinG⟺u,v∈Ciddddddddddforsomei∈{1,2,…,k}⟺piisafactorofboths(u)ands(v)ddddddddddforsomei∈{1,2,…,k}⟺gcd(s(u),s(v))>1⟺s(u)isadjacenttos(v)inG(n).
Thus, G is isomorphic to the subgraph of G(n) induced by the set {s(v)|v∈V} of vertices of G(n).Example 2.
Consider the graphG=(V,E) in Figure 1. The maximal cliques of G are C1={v1,v2,v3,v4}, C2={v2,v3,v4,v5,v6}, C3={v7,v8,v10}, C4={v9,v10}, and C5={v10,v11}. We assign the ith prime to the clique Ci for i=1,2,…,5. Then for each v∈V, we compute s1(v) and s(v) as in the proof of Theorem 1 (Table 1).
SoG is isomorphic to the subgraph of G(n) induced by the set {2,3,5,6,7,9,11,12,18,25,385} of vertices of G(n), where n=22·32·52·7·11=69300.Table 1
v
v
1
v
2
v
3
v
4
v
5
v
6
v
7
v
8
v
9
v
10
v
11
s
1
(
v
)
2
2
·
3
2
·
3
2
·
3
3
3
5
5
7
5
·
7
·
11
11
s
1
(
v
)
2
6
6
6
3
3
5
5
7
385
11
s
(
v
)
2
2
·
3
2
2
·
3
2
·
3
2
3
3
2
5
5
2
7
385
11
s
(
v
)
2
6
12
18
3
9
5
25
7
385
11Figure 1
The graphG in Example 2.


## 2. Main Results

It is important to note that instead of taking all maximal cliques ofG in Theorem 1, it is sufficient to consider a set of cliques of G which covers both vertices and edges of G.Definition 3.
LetG=(V,E) be a graph. A set S of cliques of G is called a total clique covering of G if S covers both V and E. The minimum size of a total clique covering of G is called the total clique covering number of G. We denote it by θt(G).On the other hand, given a finite sequence of positive integers, one can construct a simple undirected graph as follows.Definition 4.
Letσ=(a1,a2,…,am) be a finite sequence of positive integers. Then corresponding to this sequence, define a graph G[σ]=(V,E), where V={v1,v2,…,vm}, vi corresponds to ai (ai is called the label of vi) for i=1,2,…,m, and vivj∈E if and only if i≠j and gcd(ai,aj)>1. The graph G[σ] is said to be realized by the sequence σ.Now by Theorem1, every graph can be realized by some sequence of positive integers. Also in Definition 4, it is sufficient to take the entries ai of σ square-free if ai>1. Thus, for convenience, we specify the sequence in the following manner.Definition 5.
LetG=(V,E) be a graph. Let |V|>1, and let the graph G1 be obtained from G by deleting isolated vertices of G, if there are any. Let σ1 be a finite nondecreasing sequence of square-free positive integers greater than 1 such that G1≅G[σ1]. If G has s isolated vertices, then we prefix s number of 1’s in σ1 to obtain the sequence σ. For s=0, σ=σ1. If G is a graph with a single vertex, then σ=(1). Then G≅G[σ] and the sequence σ is called a coding sequence of G. The entries of σ, which are greater than 1, are called nontrivial. Let λ(σ) be the least common multiple of all nontrivial entries of σ.Lemma 6.
Letσ=(λ1,λ2,…,λm) be a coding sequence of a graph G=(V,E). Let V={v1,v2,…,vm}, where vi corresponds to λi for all i=1,2,…,m (one writes λi=μ(vi)). Let {p1,p2,…,pk} be the set of all distinct prime factors of λ(σ). Suppose G has s⩾0 isolated vertices. Define Sj={vj} for j=1,2,…,s and for each j=1,2,…,k, define Ss+j={vi∈V|pjdividesμ(vi)=λi}. Then S={Sj|j=1,2,…,s+k} is a total clique covering of G such that v∈Si1∩Si2∩⋯∩Sir(it>s, t=1,2,…,r) and v∉Sj for all j∈{s+1,s+2,…,s+k}∖{i1,i2,…,ir} if and only if μ(v)=pi1pi2⋯pir and for each j=1,2,…,s, v∈Sj if and only if μ(v)=1.Proof.
We first note thatSj is a clique containing only the vertex vj for j=1,2,…,s. Now for each j∈{1,2,…,k}, pj divides λi for some i∈{s+1,s+2,…,m} as pj divides λ(σ). Thus, vi∈Ss+j. So Sj≠∅, for all j=1,2,…s+k. Also for any two vertices vr,vt∈Ss+j, pj divides both λr and λt. So vr and vt are adjacent in G. Thus, each Sj is a clique of G. Again since {p1,p2,…,pk} is the set of all prime factors of λ(σ), each vertex v∈V belongs to Sj for some j∈{1,2,…,s+k}. So S covers V. Moreover, two vertices vi and vj are adjacent if and only if gcd(λi,λj)>1. So λi and λj must have at least one common prime factor, say, pr and hence vi and vj both lie in Ss+r. So S also covers E and hence S is a total clique covering of G. Now v∈Si1∩Si2∩⋯∩Sir (it>s, t=1,2,…,r) and v∉Sj for all j∈{s+1,s+2,…,s+k}∖{i1,i2,…,ir} if and only if pi1pi2⋯pir divides μ(v) but pj does not divide μ(v) for all j∈{s+1,s+2,…,s+k}∖{i1,i2,…,ir}. Now since nontrivial entries of σ are square-free integers, μ(v) is a product of distinct primes and hence μ(v)=pi1pi2⋯pir. By Definition 5, for each j=1,2,…,s, v∈Sj if and only if μ(v)=1.Definition 7.
Letσ=(λ1,λ2,…,λm) be a coding sequence of a graph G. Then the total clique covering S of G as defined in Lemma 6 is called the total clique covering ofGcorresponding to the sequence σ and is denoted by Sσ.Lemma 8.
LetG=(V,E) be a graph, and let S be a total clique covering of G. Then there exists a coding sequence σ of G such that S=Sσ.Proof.
LetS={C1,C2,…,Cs+k}, where |Ci|=1 for i=1,2,…,s, s⩾0. Let pi denote the ith prime. We define a map f:V→ℕ by f(v)=1 if v∈C1∪C2∪⋯∪Cs and f(v)=pi1pi2⋯pir if v∈Cs+i1∩Cs+i2∩⋯∩Cs+ir(where 1≤r≤k) and v∉Cj for all j∈{s+1,s+2,…,s+k}∖{s+i1,s+i2,…,s+ir}. Now S being a total clique covering, every vertex is assigned a label in this way. Also note that two vertices u, v are adjacent in G if and only if they lie in some Cs+j∈S and consequently, if and only if f(u) and f(v) have a common prime factor pj. Let us arrange the vertices of G according to the nondecreasing order of {f(v)|v∈V} and define the sequence σ by σ=(f(v1),f(v2),…,f(vm)), where f(v1)≤f(v2)≤⋯≤f(vm). Then clearly σ is a coding sequence of G and S=Sσ.Theorem 9.
LetG be a graph with s⩾0 isolated vertices, and let k be the minimum number of prime factors of λ(σ) among all coding sequences σ of G. Then θt(G)=k+s.Proof.
Letσ be a coding sequence of G such that the number of prime factors of λ(σ) is k. Then by Lemma 6, k+s=|Sσ|⩾θt(G). Again let S be a total clique covering of G such that |S|=θt(G). Then by Lemma 8, there is a coding sequence σ of G such that S=Sσ and it follows from the proof of Lemma 8 that there are |S|-s prime factors of λ(σ). Thus, k⩽|S|-s=θt(G)-s. Therefore, θt(G)=k+s.Definition 10.
LetG=(V,E) be a graph with |V|=m and s⩾0 isolated vertices. Let k=θt(G)-s. Let S={C1,C2,…,Ck+s} be a total clique covering of G such that |S|=θt(G) and |Ci|=1 for i=1,2,…,s. Now as in the proof of Lemma 8, there are k! ways of assigning the first k primes to the cliques Cs+1,Cs+2,…,Cs+k to obtain at most k! different coding sequences. Let σ[S] be the least among them in the lexicographic ordering in ℝm. Then σ[S] is called the coding sequence of Gwith respect toS. Let {S1,S2,…,Sr} be the set of all total clique coverings of G such that |Si|=θt(G) for all i=1,2,…,r. Let σ(G) be the least element of {σ[Si]|i=1,2,…,r} in the lexicographic ordering in ℝm. Then σ(G) is called the code of the graph G.For example,(2,3,3,5,5,6,6,6,7,11,385) and (2,3,3,5,5,7,10,10,10,11,231) are two coding sequences of the graph G in Example 2 with respect to the total clique covering S={C1,C2,…,C5}. It is easy to see that θt(G)=5 and S is the only total clique covering with 5 cliques. The code of G is (2,2,3,3,5,7,10,10,10,11,231). Note that for any graph G, we have G≅G[σ(G)].Theorem 11.
LetG1 and G2 be two graphs. Then G1≅G2 if and only if σ(G1)=σ(G2).Proof.
The proof follows from Definition10.Definition 12.
LetG=(V,E) be a graph with s⩾0 isolated vertices. Let S={C1,C2,…,Cs+k} be a total clique covering of G, where |Ci|=1 for i=1,2,…,s. If v∉C1∪C2∪⋯∪Cs, let m(v)=∏‍{xj|v∈Cs+j} be a monomial in the polynomial semiring ℤ0+[x1,x2,…,xk] of k indeterminates over the semiring of nonnegative integers with usual addition and multiplication. For any v∈Ci, i=1,2,…,s, define m(v)=1. Now we define
(2)f(G,S)=f(x1,x2,…,xk)=∑v∈V‍m(v).
Then f(G,S) is said to be a polynomial representation of G with respect to S.Consider the graphG in Example 2. Then f(G,S)=x1+2x2+2x3+x4+x5+3x1x2+x3x4x5 is a polynomial representation of G with respect to S={C1,C2,C3,C4,C5}. Now let G=(V,E) be a graph, and let σ=(λ1,λ2,…,λm) be a coding sequence of G. From the construction of Sσ (cf. Lemma 6, Definition 7) and by Definition 12, it follows that f(G,Sσ) can also be obtained from σ by replacing primes pi by xi (i<j⇔pi<pj) and commas by the addition symbol. It is important to note that the constant term of f(G,S) in Definition 12 is the number of isolated vertices of G.Definition 13.
LetG be a graph and σ(G) the code of G. Then the polynomial representation of G corresponding to σ(G), that is, f(G,Sσ(G)), is called the normal polynomial representation or the canonical polynomial representation of G and is denoted by F(G).The normal polynomial representation of the graphG in Example 2 is given by
(3)F(G)=2x1+2x2+x3+x4+x5+3x1x3+x2x4x5.
The following interesting observations are immediate from Definition 13.Observation 1.
A graphG is disconnected if and only if F(G)=f1+f2, where f1 and f2 are polynomials with no common variables between them. The same is true for f(G,S) for any total clique covering S of G.Observation 2.
A graphG is bipartite if and only if F(G)=f1+f2, where monomials belonging to the same fi have no common variables, for i=1,2. The same is true for f(G,S) for any total clique covering S of G.We now proceed to obtain a formula forF(G(n)).Theorem 14.
Letn=p1r1p2r2⋯pkrk∈M, where the pi’s are distinct primes. Then θt(G(n))=k and there is only one total clique covering of G(n) with precisely k cliques.Proof.
Ifn is prime, then the result is obvious. Suppose n is not a prime number. Now the vertices of G(n) correspond to all the divisors of n, greater than 1. So there are k vertices labeled pi, i=1,2,…,k. Clearly, no two of them can lie in the same clique as gcd(pi,pj)=1 for all i≠j. So in any total clique covering of G(n), these k vertices will be in k different cliques. In other words, any total clique covering has at least k cliques. Now let Ci={v∈V(G(n))|pidividesv}. Then S={Ci|i=1,2,…,k} is easily seen to be a total clique covering of G(n). So we have a total clique covering consisting of precisely k cliques. Hence, θt(G(n))=k.
Now we show that there is only one total clique covering ofG(n) containing precisely k cliques. Suppose there is another total clique covering D={D1,D2,…,Dk} of G with exactly k cliques. Here also, the vertices labeled pi, i=1,2,…,k, are in distinct cliques. Without loss of generality, let pi∈Di for i=1,2,…,k. Now for any i, pi is not adjacent to those vertices which are not in Ci. So Di⊆Ci for all i=1,2,…,k. Now suppose that for some j, there is a vertex v in Cj which is not in Dj. Now D being a total clique covering, v has to lie in at least one Dl, where l≠j. Since a total clique covering covers all the edges, the edge between v and pj will be covered. v∉Dj implies that v and pj both lie in some Dl, where l≠j. However, this contradicts the fact that pj is not adjacent to pl. So Di=Ci for all i=1,2,…,k and hence D=S.Letα(G) denote the maximum size of an independent set in a graph G. In general, θt(G)⩾α(G) for any graph G. The proof of the following proposition is similar to that of Theorem 14 and so it is omitted.Proposition 15.
LetG be a graph with α(G)=k. If {v1,v2,…,vk} is an independent set and S={S1,S2,…,Sk} is a total clique covering of G such that each vi lies only in Si among cliques in S for each i=1,2,…,k, then θt(G)=α(G)=k, and S is the only total clique covering containing exactly k cliques.Now we provide a formula forF(G(n)).Theorem 16.
Letn=p1r1p2r2⋯pkrk∈M, where the pi’s are distinct primes and r1⩾r2⩾⋯⩾rk⩾1, k⩾1. Then F(G(n)) contains all the monomials xi1xi2⋯xis, where {i1,i2,…,is}⊆{1,2,…,k}, s⩾1 with the coefficient ri1ri2⋯ris, that is,
(4)F(G(n))=∑i1<i2<⋯<is∅≠{i1,i2,…,is}⊆{1,2,…,k}‍ri1ri2⋯risxi1xi2⋯xis,
unless n is prime. If n is prime, then F(G(n))=1.Proof.
Ifn is prime, then G(n)≅K1 and so F(G(n))=1. Suppose n is not prime. Now by Theorem 14, θt(G(n))=k and there is only one total clique covering, say, S of G(n) with precisely k cliques. Let S={C1,C2,…,Ck}, where Ci={v∈V(G(n))|pidividesv} for i=1,2,…,k. So σ(G(n)) is σ[S]. First, let k>1. Now σ[S] is the least (in the lexicographic ordering) among the coding sequences of G obtained from S. By Definition 10, any such coding sequence involves the primes {t1,t2,…,tk}, where ti is the ith prime. Now for any pi, there are ri elements (namely, pi,pi2,…,piri) which belong to only the clique Ci. So considering the labellings and the fact that r1⩾r2⩾⋯⩾rk⩾1, it is easy to see that the coding sequence will be the least in the lexicographic ordering if we assign ti to the clique Ci. So the vertex corresponding to a number pi1qi1pi2qi2⋯pisqis (1⩽qij⩽rij for j=1,2,…,s where 1⩽s⩽k) is assigned the label ti1ti2⋯tis. In other words, to find out σ(G(n)), we first consider the set of all divisors {m1,m2,…,mr} (say) of n, greater than 1, where r=(r1+1)(r2+1)⋯(rk+1)-1. Then in each mj, we first replace pi by ti, then make the resultant entries square-free and arrange them in nondecreasing order. This gives us σ(G(n))=(λ1,λ2,…,λr), where each λi is a product of primes of the form ti1ti2⋯tis, (1⩽s⩽k) and this particular number repeats, say, ν times in the sequence σ(G(n)), where ν is the number of divisors of n (greater than 1) which are of the form pi1qi1pi2qi2⋯pisqis, 1⩽qij⩽rij for j=1,2,…,s; that is, ν=∏j=1srij.
Thus, by Definition13 we have F(G(n))=∑i1<i2<⋯<is,∅≠{i1,i2,…,is}⊆{1,2,…,k}ri1ri2⋯risxi1xi2⋯xis.
Finally, ifk=1,r1>1, then G(n)≅Kr1. So F(G(n))=r1x1, which satisfies the aforementioned formula. This completes the proof.For example,F(G(p2qr))=F(G(60))=2x1+x2+x3+2x1x2+2x1x3+x2x3+2x1x2x3, where p, q, and r are distinct primes. Further, one may easily verify codes and normal polynomial representations for the following special classes of graphs:(i)
σ(K1)=(1), F(K1)=1, σ(Kn)=(2,2,…,2) (n times), F(Kn)=nx1 for n⩾2,(ii)
σ(Pn)=(p1,p2,p1p3,p2p4,…,pn-3pn-1,pn-2pn-1), F(Pn)=x1+x2+∑i=1n-3xixi+2+xn-2xn-1 for n⩾3,(iii)
σ(Cn)=(p1p2,p1p3,p2p4,…,pn-2pn,pn-1pn), F(Cn)=x1x2+x1x3+∑i=1n-2xixi+2+xn-1xn for n⩾4, where pi is the ith prime for i=1,2,…,n and Kn, Pn, and Cn are, respectively, the complete graph, the path, and the cycle with n vertices.


## 3. Conclusion

There are some representations of simple undirected graphs in terms of adjacency matrices, adjacency lists, and unordered pairs which are not unique for isomorphic graphs. There are some other instances for unique representations [2, 3]. In the nauty algorithm, McKay [2] defined a canonical isomorph [4] which is a graph rather than a sequence of integers as the code of a graph introduced here. The importance of the code σ(G) is its uniqueness and its simple form. It is the same for any set of isomorphic graphs. The determination of σ(G) is not always easy, but once it is obtained for a graph, it becomes the characteristic of the graph. The authors believe that further study of the code and the normal polynomial representation of a simple undirected graph will be helpful in further research on graph theory. The purpose of this paper is to communicate these interesting observations to all graph theorists.



---

*Source: 703989-2013-08-27.xml*