Binary Cyclic Codes in Extending Circular Cliques

Binary Cyclic Codes in Extending Circular Cliques

K.Ranga Devi Research Scholar,

Department of Mathematics, S.V.University, Tirupati- 517502, A.P, India.

ABSTRACT: Let G be a coloring graph with circular chromatic number ()= {/d: ,d, gcd(k,d)=1 and d||d}, ,d are prime circular cliques. If the two circular cliques ,d at distance such that some (,d

)-precolouring of the two cliques is non-extendible. In

this section, we examine extending circular colourings of

,d , is the path of length 1 with vertex set

{1,2,,}. In view of the homomorphism G admits a (k,d)-colouring if and only if, there is a homomorphism f:,d. there exist a uniquely extendible homomorphisms between circular cliques.

KEY WORDS: Edge coloring, Vertex coloring, Circular chromatic number, Homomorphism, Binary cyclic codes.

1. INTRODUCTION:

   Graph coloring theory has a central position in discrete mathematics for its own interest as well as for the large variety of applications, dating back to the famous four-color problem stated by Guthrie in 1852 Zhu[9].

   Define a(k,d)-colouring of a graph G is an assignment :(){0,1,2,,1} such that for

   (), d|()()|d, d is any positive integer. The circular complete graph or circular clique ,d has vertices {0,1,,1} and edges

   {:d||d}. Thus ,1 is simply the (classical) complete graph on -vertices. Graph

   coloring is the procedure of assignment of colors to

   each vertex of a graph G such that no adjacent vertices get same color.

   The minimum for which admits a -coloring is called the chromatic number of and denoted by ().

   There are now many papers on colouring extensions. The introduction of [3] provides a nice overview on coloring. We focus on the situation where the precoloured vertices

   Dr.D.Bharathi Professor, Department of Mathematics,

   S.V.University, Tirupati- 517502, A.P, India.

   induce a collection of cliques. Let be a graph with circular chromatic number ()=/d [8]is isomorphic to the circular clique ,d. Suppose the vertices of have been precoloured with a (,d)-colouring. In [2] Albertson and Moore study the problem of extending a (+1)-colouring of a -colourable graph where the precoloured components are -cliques. They also study the problem when the precoloured components are general subgraphs. In the latter case the penalty for having general subgraphs is a larger number of colours may be required for the extension. In this spirit we now turn attention to extending a (,d)-colouring of a (,d)-colourable graph where the precoloured components are circular cliques.

   We now consider extending (classical) -colourings where the precoloured components are ,d. The general problem of extending colourings where the precoloured components are not cliques is considered in [2]. In our work the assumption that the precoloured components are circular cliques

2. PRELIMINARIES:

   DEFINITION 2.1: An undirected graph is a type of graph where the edges have no specified direction assigned to the them..

   DEFINITION 2.2: A binary code is cyclic code if it is a linear [n, k] code and if for every codeword (c1, c2, . . . , cn) C we also have that (cn, c1, . . . , cn1) is again a codeword in C.

   • Vertex coloring is a concept in graph theory that refers to assigning colors to the vertices of a graph in such a way that no two adjacent vertices have the same color..

   • In graph theory, Edge coloring of a graph is an assignment of colors to the edges of the graph so that no two adjacent edges have the same color

   G

   such that no adjacent vertices get same color.

   DEFINITION 2.3: Graph coloring is the procedure of assignment of colors to each vertex of a graph

   DEFINITION 2.4: The chromatic number of a graph is the minimal number of colours needed to colour the vertices in such a way that no two adjacent vertices have the same colour.

3. RESULT AND DISCUSSION:

We find Vertex chromatic number, edges chromatic number, Degree and Dimensions of the generator matrix.

A(k,d)-colouring of a graph G is an assignment :(){0,1,2,,1} such that

for (), d|()()|d, d is any positive integer. The circular complete graph or circular clique ,d has vertices {0,1,,1} and edges {:d||d}. Thus ,1 is simply the (classical) complete graph on -vertices. The circular complete graphs play the role in circular colourings as do the complete graphs in classical colourings. Adopting the homomorphism point of view, see [4], [5], admits a (,d)-colouring if and only if, there is a homomorphism :,d. Recall, a homomorphism : is a

mapping :()() such

that () implies ()()(). We

write to indicate the existence of a

homomorphism. It turns out that ,d,d if and only if /d/d. Thus, given a graph , if ,d, then ,d for any /d/d is surjective. Suppose (k2d), d is positive integer and k is prime number with gcd(k,d)=1, the circular chromatic numbers includes all chromatic numbers ()=() as well as odd holes see the below figures.

The circular chromatic number of a graph is defined as ()=Inf{/d : ,d and gcd(k,d)=1}.

In [4], Bondy and Hell show the infimum may be replaced by a minimum. The proof depends on the fact that optimum colourings must be surjective. The surjective mappings play a key role in our constructions of non-extendible families.

Example 3.1.1: The circular chromatic number of a graph is defined as ()=inf{5/1 : 5,1 and gcd(5,1)=1}.

The adjacency matrix of X is

1	0	0	0	1
1	1	0	0	0
0	1	1	0	0
0	0	1	1	0
[0	0	0	1	1]

Vertex coloring graph Edge coloring graph (Fig 1.1)

The polynomial represented by X is k(x)=1+x4

In above Figure 1.1, the vertex chromatic number ()= 3 and Edge chromatic number is 3.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 4, dimension of the code is 5 and has no error correcting codes. (5/1)=3

Example 3.1.2: The circular chromatic number of a graph is defined as ()=inf{5/2 : 5,2 and gcd(5,2)=1}.

The adjacency matrix of X is

0	0	1	1	0
0	0	0	1	1
1	0	0	0	1
1	1	0	0	0
[0	1	1	0	0]

Vertex coloring graph Edge coloring graph (Fig 1.2)

The polynomial represented by X is k(x)=x2+x3

In above Figure 1.2, the vertex chromatic number ()=5 and Edge chromatic number is 5.

Hence X corresponds to the cyclic code C =<x> . Since te degree of the generator polynomial k(x) is 3, dimension of the code is 5 and has no error correcting codes. (5/2)=5

Example 3.1.3: The circular chromatic number of a graph is defined as ()=inf{5/3 : 5,3 and gcd(5,3)=1 }.

The adjacency matrix of X is

0	0	1	1	0
0	0	0	1	1
1	0	0	0	1
1	1	0	0	0
[0	1	1	0	0]

Vertex coloring graph Edge coloring graph (Fig 1.3)

The polynomial represented by X is k(x)= x2+x3

In above Figure 1.3, the vertex chromatic number ()= 5 and Edge chromatic number is 5.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 3, dimension of the code is 5 and has no error correcting codes. (5/3)=5

()=inf{ 5/1, 5/2 and 5/3} is 5/1=3

Example 3.2.1: The circular chromatic number of a graph is defined as ()=inf{7/1: 7,1 and gcd(7,1)=1 }.

0	1	0	0	0	0	1
1	0	1	0	0	0	0
0	1	0	1	0	0	0
0	0	1	0	1	0	0
0	0	0	1	0	1	0
	0	0	0	1	0	1
1	0	0	0	0	1	0]

The adjacency matrix of X is

0

[

.

Vertex coloring graph Edge coloring graph

(Fig 1.4)

The polynomialrepresented by X is k(x)= x+x6

In above Figure 1.4, the vertex chromatic number ()=3 and Edge chromatic number is 3.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 6, dimension of the code is 7 and has no error correcting codes. (7/1)=3

Example 3.2.2: The circular chromatic number of a graph is defined as ()=inf{7/2: 7,2 and gcd(7,2)=1 }.

The adjacency matrix of X is

0	0	1	0	0	1	0
0	0	0	1	0	0	1
1	0	0	0	1	0	0
0	1	0	0	0	1	0
0	0	1	0	0	0	1
1	0	0	1	0	0	0
[0	1	0	0	1	0	0]

Vertex coloring graph Edge coloring graph (Fig 1.5)

The polynomial represented by X is k(x)= x2+x5 In above Figure 1.3, the vertex chromatic number ()= 4 and Edge chromatic number is 7.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 5, dimension of the code is 7 and has no error correcting codes. (7/2)=4

Example 3.2.3: The circular chromatic number of a graph is defined as ()=inf{7/3: 7,3 and gcd(7,3)=1 }.

The adjacency matrix of X is

0	0	0	1	1	0	0
0	0	0	0	1	1	0
0	0	0	0	0	1	1
1	0	0	0	0	0	1
1	1	0	0	0	0	0
0	1	1	0	0	0	0
[0	0	1	1	0	0	0]

Vertex coloring graph Edge coloring graph

(Fig 1.6)

The polynomial represented by X is k(x)= x3+x4

In above Figure 1.3, the vertex chromatic number ()= 4 and Edge chromatic number is 7.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 4, dimension of the code is 7 and has no error correcting codes. (7/3)=4

()=inf{ 7/1, 7/2 and 7/3} is 7/1=3

Example 3.3.1:The circular chromatic number of a graph is defined as ()=inf{11/1: 11,1 and gcd(11,1)=1 }.

0	1	0	0	0	0	0	0	0	0	1
1	0	1	0	0	0	0	0	0	0	0
0	1	0	1	0	0	0	0	0	0	0
0	0	1	0	1	0	0	0	0	0	0
0	0	0	1	0	1	0	0	0	0	0
0	0	0	0	1	0	1	0	0	0	0
0	0	0	0	0	1	0	1	0	0	0
0	0	0	0	0	0	1	0	1	0	0
0	0	0	0	0	0	0	1	0	1	0
	0	0	0	0	0	0	0	1	0	1
1	0	0	0	0	0	0	0	0	1	0]

The adjacency matrix of X is

0

[

The polynomial represented by X is k(x)=x+x10

In above Figure 1.7, the vertex chrmatic number ()= 3 and Edge chromatic number is 3.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 10, dimension of the code is 11 and has no error correcting codes. (11/1)=3

Example 3.3.2:The circular chromatic number of a graph is defined as ()=inf{11/2 : 11,2 and gcd(11,2)=1 }.

The adjacency matrix of X is

0	0	1	0	0	0	0	0	0	1	0
0	0	0	1	0	0	0	0	0	0	1
1	0	0	0	1	0	0	0	0	0	0
0	1	0	0	0	1	0	0	0	0	0
0	0	1	0	0	0	1	0	0	0	0
0	0	0	1	0	0	0	1	0	0	0
0	0	0	0	1	0	0	0	1	0	0
0	0	0	0	0	1	0	0	0	1	0
0	0	0	0	0	0	1	0	0	0	1
1	0	0	0	0	0	0	1	0	0	0
[0	1	0	0	0	0	0	0	1	0	0]

.

Vertex coloring graph Edge coloringraph

(Fig 1.8)

The polynomial represented by X is k(x)=x2 +x9

In above Figure 1.8, the vertex chromatic number ()= 4 and Edge chromatic number is 6.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 9, dimension of the code is 11 and has no error correcting codes. (11/2)=4

Example 3.3.3:The circular chromatic number of a graph is defined as ()=inf{11/3 : 11,3 and gcd(11,3)=1 }.

The adjacency matrix of X is

Vertex coloring graph Edge coloring graph

(Fig 1.7)

0	0	0	1	0	0	0	1	0	0	0
0	0	0	0	1	0	0	0	1	0	0
0	0	0	0	0	1	0	0	0	1	0
0	0	0	0	0	0	1	0	0	0	1
0	0	0	0	0	0	0	1	0	0	0
0	0	0	0	0	0	0	0	1	0	0
0	0	0	0	0	0	0	0	0	1	0
0	0	0	0	0	0	0	0	0	0	1
1	0	0	0	0	0	0	0	0	0	0
0	1	0	0	0	0	0	0	0	0	0
[0	0	1	0	0	0	0	0	0	0	0]

The polynomial represented by X is k(x)= x4 +x7 In above Figure 1.10, the vertex chromatic number ()= 4 and Edge chromatic number is 6.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 7, dimension of the code is 11 and has no error correcting codes. (11/4)=4

Example 3.3.5:The circular chromatic number of a graph defined as ()=inf{11/5 : 11,5 and gcd(11,5)=1}

The adjacency matrix of X is

Vertex coloring graph Edge coloring graph

(Fig 1.9)

The polynomial represented by X is k(x)= x3 +x7

In above Figure 1.9, the vertex chromatic number ()= 4, edge chromatic number is 6.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 7, dimension of the code is 11 and has no error correcting codes. (11/3)=4

Example3.3.4:The circular chromatic number of a graph is defined as ()=inf{11/4 : 11,4 and gcd(11,4)=1}

The adjacency matrix of X is

0	0	0	0	1	0	0	1	0	0	0
0	0	0	0	0	1	0	0	1	0	0
0	0	0	0	0	0	1	0	0	1	0
0	0	0	0	0	0	0	1	0	0	1
1	0	0	0	0	0	0	0	1	0	0
0	1	0	0	0	0	0	0	0	1	0
0	0	1	0	0	0	0	0	0	0	1
1	0	0	1	0	0	0	0	0	0	0
0	1	0	0	1	0	p>0	0	0	0	0
0	0	1	0	0	1	0	0	0	0	0
[0	0	0	1	0	0	1	0	0	0	0]

0	0	0	0	0	1	1	0	0	0	0
0	0	0	0	0	0	1	1	0	0	0
0	0	0	0	0	0	0	1	1	0	0
0	0	0	0	0	0	0	0	1	1	0
0	0	0	0	0	0	0	0	0	1	1
1	0	0	0	0	0	0	0	0	0	1
1	1	0	0	0	0	0	0	0	0	0
0	1	1	0	0	0	0	0	0	0	0
0	0	1	1	0	0	0	0	0	0	0
0	0	0	1	1	0	0	0	0	0	0
[0	0	0	0	1	1	0	0	0 .	0	0]

Vertex coloring graph Edge coloring graph (Fig 1.11)

The polynomial represented by X is k(x)= x5 +x6

In above Figure 1.11, the vertex chromatic number ()= 4 and Edge

chromatic number is 6.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 6, dimension of the code is 11 and has no error correcting codes. (11/5)=4

c()= inf{11/1, 11/2, 11/3, 11/4 and 11/5} is 11/1=3

Vertex coloring graph Edge coloring graph (Fig 1.10)

.

We observe that the above graphs , the two circular cliques ,d at distance such that some (,d)- precolouring of the two cliques (Vertex chromatic number and Edge chromatic

number d ) are non-extendible. And the dimensions of generator matrix are same. Also the circular chromatic numbers are

• ()= inf{ 5/1, 5/2 and 5/3} is 5/1=3

• ()=inf{ 7/1, 7/2 and 7/3} is 7/1=3

• ()= inf{11/1, 11/2, 11/3, 11/4 and 11/5} is 11/1=3.

HOMOMORPHISM OF A CIRCULAR GRAPHS:

A k-coloring, for some integer k, is an assignment of one of k colors to each vertex of a graph G such that the endpoints of each edge get different colors. The k-colorings of G correspond exactly to homomorphisms from G to the complete graph Kk.[3] Indeed, the vertices of Kk correspond to the k colors, and two colors are adjacent as vertices of Kk if and only if they are different. Hence a function defines a homomorphism to Kk if and only if it maps adjacent vertices of G to different colors (i.e., it is a k-coloring). In particular, G is k-colorable if and only if it is Kk-colorable.[3]

If there are two

homomorphisms G H and H Kk, then their composition G Kk is also a homomorphism.[1] In other words, if a graph H can be colored with k colors, and there is a homomorphism from G to H, then G can also be k-colored. Therefore, G H implies (G) (H), where denotes the chromatic number of a graph (the least k for which it is k-colorable).[4]

DIRECT PRODUCT GRAPHS: The direct product

G × H of graphs G and H is the graph with the vertex set V (G) × V (H), two vertices (x, y) and (v, w) being adjacent in G × H if and only if xv E(G) and yw E(H).

PREPOSITION3.3: Let : be a homomorphism and let V(). The homomorphism is uniquely extendible at if whenever : is a homomorphism with g()=() for all , then ()=(). If is uniquely extendible at for all V(), we simply say is uniquely extendible[1].

PREPOSITION 3.4: Let and be graphs. The extension product X has as its vertex set

()×() with (1,p)(2,p) an edge if 12() and either pp() or p=p. The direct product of with a reflexive copy (a loop on each vertex) of .

Proof: The direct product of G and H is the graph, denoted as G×H, whose vertex is V (G)×V (H), and for which vertices (g, h) and(g, h) are adjacent precisely if ggE(G) and hhE(H).

Thus, V (G×H) = {(g, h) : gV (G) and hV (H)},

E(G×H) = {(g, h)(g, h) : ggE(G) and

hhE(H)}.

Other names for the direct product that have appeared in the literature are tensor product, Kronecker product, cardinal product, relational product, cross product, conjunction, weak direct product, or categorical product.

A product G×H has a loop at (g, h)if and only if both G and H have loops at g and h, respectively.

Moreover, if G has no loop at g, then the Hlayer H(g,h) is disconnected; whereas if G has a loop at g, then H(g,h) is isomorphic to H.

Suppose (g, h) and (g, h) are vertices of a direct product G×H and n is an integer for which G has a g, g- walk of length n and H has an h, h- walk of length

n. Then G×H has a walk of length n from (g, h) to (g, h). The smallest such n (if it exists) equals d((g, h), (g, h)). If no such n exists, then d((g, h), (g, h)) =

.

Example 3.4.1:Let and be graphs.The extension product :2,2 P2×P2 has as its vertex set

(2)×(2) with (1,p)(2,p) an edge

if 12() and either pp() or p=p.

Vertex and Edge coloring graphs of G2 and G3

Let :2,2 P2×P2 the generatoer of a matrix is [1 1]

1 1

P2×P2 Vertex and Edge graphs

(Fig 1.12)

The polynomial represented by X is k(x)=1+x

In above Figure 1.12, the vertex chromatic number

()= :2,2 P2×P2 is 4, edge chromatic number is 2.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 1, dimension of the code is 2 and has no error correcting codes.

Example 3.4.2:Let and be graphs.The extension product P2×P3 has as its vertex set (2)×(3) with (1,p)(2,p) an edge if 12() and

either pp() or p=p.

Let :2,3 P2×P3 , the generator of a matrix is [1 1 1]

1 1 1

P2×P3 Vertex and Edge graphs (Fig 1.13)

The polynomial represented by X is k(x)=1 + x+x2

In above Figure 1.13, the vertex chromatic number ()= :2,3 P2×P3 is 4, edge chromatic number is 4.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 2, dimension of the code is 2 and has no error correcting codes.

Example 3.4.3 :Let and be graphs.The extension product :2,5 P2×P5 has as its vetex set

(2)×(5) with (1,p)(2,p) an edge if 12() and either pp() or p=p.

Let :2,5 P2×P5, the generator of a matrix is [1 1 1 1 1]

1 1 1 1 1

P2×P5 Vertex and Edge graphs

(Fig 1.14)

The polynomial represented by X is k(x)= 1 + x + x2+x3+x4

In above Figure 1.14, the vertex chromatic number ()= :2,5 P2×P5 is 4, edge chromatic number is 6.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 4, dimension of the code is 2 and has no error correcting codes.

Example 3.4.4:Let and be graphs.The extension product :2,7 P2×P7 has as its vertex set

(2)×(7) with (1,p)(2,p) an edge if 12() and either pp() or p=p.

Let :2,7 P2×P7, the generator of a matrix is [1 1 1 1 1 1 1]

1 1 1 1 1 1 1

P2×P7 Vertex and Edge graphs (Fig 1.15)

The polynomial represented by X is k(x)= 1 + x + x2+x3+x4+x5+x6

In above Figure 1.15, the vertex chromatic number ()= :2,7 P2×P7 is 4, edge chromatic number is 6.

Hence X corresponds to the cyclic code C =<x> . Since the degree of the generator polynomial k(x) is 6, dimension of the code is 2 and has no error correcting codes.

We observe that from the graphs , the product of two circular cliques ,d at distance such that some (,d)-precolouring of the two cliques( Vertex chromatic number and Edge chromatic number d ) are non-extendible. And the dimensions of generator matrix are same.

• ()= :2,2 P2×P2 is 4

• ()= :2,3 P2×P3 is 4

• ()= :2,5 P2×P5 is 4

• ()= :2,7 P2×P7 is 4

IV.CONCLUSION:

We finish the paper with an extension result for (,d)-colourings of ,d cliques in -colourable graphs.

1. In above figures, the two circular cliques ,d at distance such that some (,d)-precolouring of the two cliques( Vertex chromatic number and Edge chromatic number) are non-extendible. And the dimensions of generator matrix are same. The circular chromatic numbers are always same.

   • ()= inf{ 5/1, 5/2 and 5/3} is 5/1=3

   • ()=inf{ 7/1, 7/2 and 7/3} is 7/1=3

   • ()= inf{11/1, 11/2, 11/3, 11/4 and 11/5} is 11/1=3, etc.

2. :k,dPn , if is uniquely extendible at for all

   (), we simply say is uniquely extendible. The product of two circular cliques ,d at distance such that some (,d)-precolouring of the two

   cliques( Vertex chromatic number and Edge chromatic number d 2) are non-extendible. Andthe dimensions of generator matrix are same, but degree of the polynomials is increasing.

   • ()= :2,2 P2×P2 is 4

   • ()= :2,3 P2×P3 is 4

   • ()= :2,5 P2×P5 is 4

   • c()= :2,7 P2×P7 is 4

3. REFERENCES:

[1].P. Hell, J. Neeti Graphs and Homomorphisms, Oxford Lecture Series in Mathematics and its Applications, vol. 28, Oxford University Press, Oxford (2004)Google Scholar

[2]. M.O. Albertson, E.H. Moore, Extending graph colorings, J. Combin. Theory Ser. B, 77 (1999),

pp. 83-95 View PDF View article in Scopus Google Scholar

[3]. M.O. Albertson, D.B. West, Extending precolorings to circular colorings, J. Combin. Theory Ser. B, 96 (2006) P.p 472-481View PDF article in Scopus Google Scholar

[4]. J.A. Bondy, P. Hell, A note on the star chromatic number, J. Graph Theory, 14 (1990), pp. 479-482

View at publisher Cross Ref in Scopus Google Scholar

[5]. M.O. Albertson, You cant paint yourself into a corner, J. Combin. Theory Ser. B, 73 (1998), pp. 189-194 View PDF View article in Scopus Google Scholar

[6]. C. Thomassen Color-critical graphs on a fixed surface, J. Combin. Theory Ser. B, 70 (1997), pp. 67-100 View PDF View article in Scopus Google Scholar

[7]. D.B. West, Introduction to Graph Theory(2nd edition), Prentice Hall Inc., Upper Saddle River, NJ (2001)

Googel Scholar

[8]. Dr.D.Bharathi, K.Ranga Devi, Introduced Binary cyclic codes in circular cliques, IJRASET, Volume 12, ISSN NO: 2321-9653, issueVI

June 2024

[9] X. Zhu. Circular chromatic number: a survey. Discrete Mathematics, 229:371410, 2001.

IJERTV13IS090082

(This work is licensed under a Creative Commons Attribution 4.0 International License.)