# The Equitable Chromatic Bounds on Splitting of Block Circulant Graphs

Authors: M Jagannathan; Vernold Vivin.J; Veninstine Vivik.J
Journal: Mathematical Problems in Engineering
 (2022)

---

## Abstract

An equitable vertex coloring for the splitting of block circulant graphs is investigated. The block circulant graphs comprises block circulant matrices, where each block is itself a matrix. These blocks in each row are cyclically shifted one place to the right from those of the previous row. We approached such block circulant graphs in matrix representation and derived their independent sets using the neighbourhoods of each vertex. This classification makes the vertex coloring process to be simpler and equitable in most cases. In this framework, the equitable chromatic numbers are obtained for splitting on block circulant graphs, namely prism, antiprism, crossed and closed sun graphs.


---

## Body

## 1. Introduction

In this paper, we consider on block circulant graph. Circulant graphs remains an active area of research for decades because of their wider applications in computer science, coding theory and discrete mathematics. A circulant graph is a graph having a circulant matrix. It is a matrix in which the elements of each row are taken from those of the previous row moved one place to the right.The few more practical applications of circulant networks are, it forms a basis of the structure in a model of small-world networks, an important class of interconnection networks in parallel and distributed computing, a base structure for discrete cellular neural networks and in coding theory for the construction of perfect error-correcting codes, etc. In 2012 Monakhova [1] studied the structural and communicative properties of circulant networks.Heuberger [2] in 2003 completely characterized the planarity and calculated the chromatic number for circulant graphs. Discepoli et al. [3] in 2004 constructed two different heuristics to choose the best set of eigenvectors through which the correct coloration of the graph is found. Ilic and Basic [4] in 2010 provided upper and lower bounds on the chromatic number of integral circulant graphs with arbitrary number of divisors. Codenotti et al. [5] have shown that the computation of chromatic number for circulant graphs whose adjacency matrices are circulant, is an NP-hard problem. In 2009 Barajas and Serra [6] studied the regular chromatic number of circulant graphs. In 2017 Nicoloso and Pietropaoli [7] discussed an exact vertex colouring algorithm for 3-chromatic circulant graphs.In 2013 Hongbo and Xiaofeng [8] calculated the characteristic polynomials and spectra of several special block circulant graphs. Garcia et al. [9] in 2019 provides a natural bijection between the associated graphs of generalized crowns and a particular family of block circulant graphs. Recently in 2022 Goedgebeur and Van Overberghe [10] presented algorithms to establish the new lower bounds and exact values on Ramsey numbers involving circulant and block-circulant graphs.However, only few research works has been carried out in the chromatic number problem for circulant and block circulant graphs. It still remains an active area of research. This led to the idea of applying splitting on block circulant graphs and explore its equitable vertex coloring.Sampathkumar et al. [11] introduced the concept of splitting graph of a graph G denoted by SG. It is framed by adding to each vertex v, a new vertex v′ such that v′ is adjacent to every vertex that is adjacent to v in G. In this work, the splitting is considered for family of prism graphs and closed sun graph.Besides this circulant and block circulant graphs, the idea of bounds remains open for various other graph such as Y-index of graphs and Zagreb indices of graphs. In 2022, Maji et al. explored the test of having a high correlation with the physiochemical properties passed through the new chemical descriptors Y-index of graphs [12]. The new topological indices, such as the Zagreb index of graphs [13], have a good correlation with various physical attributes, chemical reactives, or biological properties that can be explored by equitable chromatic bounds.


### 1.1. Organization of the paper

This paper is organized as follows: The next section contains some basic definitions and important results of equitable coloring related to this paper. In section 3, the adjacency matrix of block circulant graphs, like closed sun, prism, Antiprism and crossed prism are structured. In section 4, the theorems with proofs is constructed for splitting of block circulant graphs discussed in previous section, and their equitable chromatic number are determined. Finally, the conclusion of this study with some future work related to this field is suggested in section 5.


## 1.1. Organization of the paper

This paper is organized as follows: The next section contains some basic definitions and important results of equitable coloring related to this paper. In section 3, the adjacency matrix of block circulant graphs, like closed sun, prism, Antiprism and crossed prism are structured. In section 4, the theorems with proofs is constructed for splitting of block circulant graphs discussed in previous section, and their equitable chromatic number are determined. Finally, the conclusion of this study with some future work related to this field is suggested in section 5.


## 2. Preliminaries

Graph coloring is one of the interesting concept and has wider applications in assignment, scheduling and balancing problems, etc. For example, consider the scheduling problem like collection of tasks to be done, which are represented as the vertices of the graph and the edges are connected between two conflicting tasks that should not be performed at the same time. When graph coloring is applied to such scheduling problem, the coloring on the vertices of this graph partitions the tasks into subsets that may be done at the same time. The balancing of such tasks to be performed properly in more or less equally within the available time slots is achieved by equitable coloring. Here we present some basic definitions related to this work.An×n circulant matrix [14] is generated from the n-vector c1,c2,…,cn by cyclically permuting its entries, and is of the form.(1)Cn=circc1,c2,…,cn=c1c2…cncnc1…cn−1⋮⋮⋱⋮c2c3…c1.Definition 2.1.
(see [14]). A circulant matrix is defined completely by the generating elements in its first row, which are cyclically shifted to the right by one position per row to form the subsequent rows. The circulant matrix is the set of all such matrices of ordern, which is denoted byCn.Definition 2.2.
(see [14]). A block circulant matrix of dimensionnm×nmis a matrix generated by the matricesC1,C2,…,Cneach of dimensionm×mand is symbolized asC. The block rows ofCare obtained by cyclically shifting theCi’s as follows:(2)C=bcircC1,C2,…,Cn=C1C2…CnCnC1…Cn−1⋮⋮⋱⋮C2C3…C1.
The matrix array defined above is said to be a block circulant of typem,n. The set of all such matrices is denoted byℬCm,n. Any matrixCi,i=1,2,…,nin a block circulant matrixCneed not be necessarily a circulant.Definition 2.3.
(see [11]). For each pointvof a graphG, take a new pointv′. Joinv′to all points ofGadjacent tov. The graphSGthus obtained is called the Splitting graph ofG.Definition 2.4.
[15]Equitable vertex coloring. The set of vertices of a graphGcan be colored withpcolors such that no edge joins the vertices of the same color and the cardinalities of the color setsV1,V2,…,Vpdiffer by maximum value of one, thenGis said to be equitablyp-colorable.
The smallest integerp for which G is equitably p-colorable is known as the equitable chromatic number and is denoted by χ=G.Conjecture 2.5 (see [15]).
Equitable Coloring ConjectureECCFor any connected graphG, other than complete graph or odd cycle, thenχ=G≤Δ.
Bodleander and Fomin [16] proved both the problems of equitable k-coloring and l-bounded k-coloring can be solved to optimality in polynomial time for graphs of bounded tree-width. In 2006, Furmańcyzk [17] studied the equitable coloring of Cartesian and tensor product of graphs. In 2013, Kaliraj et al. [18] investigated the equitable coloring’s on Myscielkian construction of wheels and bi-graphs. In 2021, Veninstine and Xavier [19] applied spectral cluster techniques to achieve equitable coloring for distributed web networks.
This paper focus on the study of block circulant graphs, splitting block circulant graphs and determining their equitable chromatic number. The embodying of splitting of graphSG with block circulant graph BCm,n and obtaining its equitable chromatic number χ=G is a new approach. Throughout this paper, we propose the idea of identifying the neighbours NG of each n-vertex in splitting block circulant graph by considering its adjacency matrix. The n-independent sets of cardinal number 4 are formed by taking the difference between the neighbourhood sets.
An independent set [20] in a graph is a set of pairwise nonadjacent vertices. In this work the independent sets are represented as ℐn. The coloring is applied to these independent sets ℐk,1≤k≤n and verified for equitability. If it is not equitable, further some the independent sets are parted into subsets to make the coloring as equitable. In this work, we obtain the equitable chromatic number for spitting on graphs such as prism, antiprism, crossed prism, and closed sun graph.


## 3. Graphs with block circulant adjacency matrix

In this section, the matrix representation of considered block circulant graphs is constructed with examples. A graph with2n vertices having a central complete graph Kn and an outer ring of n vertices, each of which is joined to both end points in the closest outer edge of the central core is called a sun graph, denoted as Sn.The closed sun graph is obtained from sun graphSn by adding edges to the outer ring of n vertices and is denoted as Sn¯=Sn∪Cn. this graph can be viewed as a block circulant graph by considering its adjacency matrix.For example, consider a closed sun graphS4¯ (Figure 1) and its adjacency matrix as follows.Figure 1
Closed sun graphS4¯ Adjacency matrix of S4¯.The adjacency matrix can be represented in block matrix as(3)AS4−=XYYXwhere(4)X=0111101111011110,Y=1001110001100011.Thus,AS4¯=bcircX,Y is a block circulant of type 2,2. Hence the closed sun graph is a block circulant graph but not a circulant graph.The prism graph [21] is a graph obtained from two disjoint cycles by connecting the vertices vi:1,2,…,n in the inner cycle with the corresponding vertices vj:j=n+i in the outer cycle. It is represented in this work as Yn. Prism graph is also called as a circular ladder graph CLn.For example, consider a prism graphY6 (Figure 2) and its adjacency matrix as follows.Figure 2
Prism graphY6 Adjacency matrix of Y6.For prism graphY6 its adjacency matrix can be given in block matrix as(5)AY6=PQQP.where(6)P=010001101000010100001010000101100010,Q=100000010000001000000100000010000001.HereP=circ0,1,0,0,0,1, and Q=circ1,0,0,0,0,0 are circulant matrices. But the entire prism graph, AY6=bcircP,Qis a block circulant graph of type (2, 2). Hence the prism graph is a block circulant graph and on the whole it is not a circulant graph.The antiprism graph [22] is a graph having 2n vertices on two cycles labelled with vi:i=1,2…,n in the inner cycle, vj:j=n+1 in the outer cycle. Join these two cycles with edges of the form vivj:1≤i≤n, v1v2n and vj−12≤i≤n such that vi+1and vj+1 and vi+1 (mod n) are adjacent. It is symbolized as An.For example, consider a antiprism graphA4 as shown in Figure 3 and its adjacency matrix as follows.Figure 3
Antiprism graphA4 Adjacency matrix of A4.The adjacency matrix can be represented in block matrix asIt is observed thatR=circ0,1,0,1 and S=circ1,0,0,1 are separately circulant matrices. The full prism graph, AY6=bcircR,S is a block circulant graph with block circulant matrix of type 2,2. Hence the prism graph is a block circulant graph and is not a circulant graph.A crossed prism graph [22] for positive even n, is a graph obtained from two cycles Cn and joining these cycles with edges vk,vk+n+1 and vk+1,vk+n for k=1,3,…,n−1. The crossed prism graph is denoted by Rn.For example, consider a crossed prism graphR6 (Figure 4) and its adjacency matrix as follows.Figure 4
Crossed Prism graphR6 Adjacency matrix of R6.The adjacency matrix of crossed prism graphR6 can be written in block matrix as(7)AR6=STTSwhere(8)S=010001101000010100001010000101100010,andT=010000100000000100001000000001000010.Thus,AR6=bcircS,T is a block circulant of type 2,2. Hence the crossed prism graph is a block circulant graph and not a circulant graph.


## 4. Equitable coloring in splitting of block circulant graphs

In this section, the splitting of graph is considered for block circulant graphs such asYn, An, Rn and Sn¯. Their generalized adjacency matrix with blocks are constructed. The partition of independent sets is done through the difference of neighbourhood sets identified from the rows of the adjacency matrix. The equitable vertex coloring is established by applying minimum colors to the vertices of the independent sets. The figures depict the colors assigned to the vertices of each independent set in an equitable manner.Theorem 4.1.
The equitable vertex coloring for splitting of Prism graphYnis(9)χ=SYn=2,ifnis odd andn≡0mod3for any evenn,3,ifnis odd andn≡1mod3orn≡2mod3.Proof.
Consider a splitting Prism graphSY6 (see Figure 5), which generates a graph with 24 vertices and 54 edges.
Generally, the splitting of block circulant Prism graphYn generates a graph with 4n vertices and 9n edges which is not a block circulant. Its generalized adjacency matrix can be structured in blocks as follows.
Consider the first row of the adjacency matrix corresponding to the vertexv1 and 4n columns to obtain the neighbourhood N.(10)v1v1v2…vnvn+1vn+2…v2n01…110…0v2n+1v2n+2…v3nv3n+1v3n+2…v4n01…110…0.
The neighbourhood of the vertexv1 are identified from columns having the entries as 1.(11)Nv1=v2,vn,vn+1,v2n+2,v3n,v3n+1.
The second row of the adjacency matrix corresponds to the neighbourhood of the vertex(12)AR6=STTS,
Therefore,(13)Nv2=v1,v3,vn+2,v2n+1,v2n+3,v3n+2.Similarly the neighbourhood of the remaining vertices are obtained from the corresponding rows of the adjacency matrix of graph SYn.(14)Nv3=v2,v4,vn+3,v2n+2,v2n+4,v3n+3,Nv4=v3,v5,vn+4,v2n+3,v2n+5,v3n+4,……………………Nvn−1=vn−2,vn,v2n−1,v3n−2,v3n,v4n−1,Nvn=v1,vn−1,v2n,v2n+1,v3n−1,v4n.The repetition of vertices in Ni,i=1,2,…,n are refined by finding the difference of the neighbourhood sets which produces the independent sets ℐi,i=1,2,…,n.(15)ℐ1=Nv1−Nv3=vn,vn+1,v3n,v3n+1,ℐ2=Nv2−Nv4=v1,vn+2,v2n+1,v3n+2,ℐ3=Nv3−Nv5=v2,vn+3,v2n+2,v3n+3,…………………………………………ℐn−1=Nvn−1−Nv1=vn−2,v2n−1,v3n−2,v4n−1,ℐn=Nvn−Nv2=vn−1,v2n,v3n−1,v4n.The coloring of the vertices is made through these independent sets.Figure 5
Splitting Prism graphSY6.Case.
(i)Ifn is odd, n≡0mod3
Consider the coloring as a mapping function fromf1:ℐi⟶C1, where C1=1,2.
When1≤i≤n−1(16)f1ℐi=1,i≡1mod2,2,i≡0mod2.To achieve equitable coloring the set ℐn is divided into two subsets ℐn+1=vn−1,v2n and ℐn+2=v3n−1,v4n such that ℐn+1⊂ℐn and ℐn+2⊂ℐn which implies ℐn+1∪ℐn+2=ℐn. The coloring of the elements (vertices) in this two subsets are done as follows.(17)f1ℐn+1=1and,f1ℐn+2=2.
Thus the colors assigned on the vertices of the graph through this method of mapping the functionf1 yields the two independent color classes C1 and C2 having colors 1 and 2 respectively. For instance see Figure 6.(18)C1=v2k,1≤k≤3n−12,3n+12≤k≤4n−12,vn,v3n,C2=v2l−1,1≤l≤n2,n+22≤l≤3n−22,3n+22≤l≤4n−12,v3n−1,v4n.
It is evident thatC1=C2=2n, therefore C1−C2=0≤1 satisfies the equitable condition. In this case χ=SYn=2.Figure 6
Equitable vertex coloring of splittingY9, n≡0mod3.Case (ii).
Ifn is even and n≡0mod3 or n≡1mod3 or n≡2mod3
Consider the coloring as a mapping function fromf2:ℐi⟶C1, where C1=1,2.
When1≤i≤n(19)f2ℐi=1,i≡1mod2,2,i≡0mod2.
It is clear that the difference between two color classesC1 and C2 is less than or equal to one, where C1=ℐ1∪ℐ3∪…∪ℐn−1 and C2=ℐ2∪ℐ4∪…∪ℐn. As a consequence C1=C2=2n. Hence the equitable condition is satisfied by C1|−|C2=0≤1. Thus χ=SYn=2 (see Figure 7).Figure 7
Equitable vertex coloring of splittingY12, n≡0mod3.Case (iii).
Ifn is odd, n≡1mod3
The independent setsℐ1, ℐ2 and ℐn−1 are split up into subsets for making the proper equitable vertex coloring. The set ℐ1 is separated into subsets ℐS1=vn, ℐS2=vn+1 and ℐS3=v3n,v3n+1, where ℐS1⊂ℐ1, ℐS2⊂ℐ1 and ℐS3⊂ℐ1. It implies that ℐS1∪ℐS2∪ℐS3=ℐ1. The set ℐ2 is divided into subsets ℐS4=v1,v2n+1 and ℐS5=vn+2,v3n+2, which implies ℐS4⊂ℐ2, ℐS5⊂ℐ2 and hence ℐS4∪ℐS5=ℐ2. Likewise the set ℐn−1 is partitioned into two subsets ℐS6=vn−2,v4n−1 and ℐS7=v2n−1,v3n−2. After splitting form the union of the sets βk,k=1,2,…5, where(20)β1=IS1∪IS5,β2=IS2∪IS3,β3=IS4,β4=IS6,β5=IS7.
Next the coloring is mapped as a function from(21)f3:ℐi,2≤i≤n−2∪ℐn∪βk,1≤k≤5⟶C2,whereC2=1,2,3is the color set.When 3≤i≤n−2(22)f3ℐi=1,i≡2mod3,2,i≡2mod3,3,i≡2mod3,f3ℐn=1,f3βk=1,k=3,2,k=2,4,3,k=1,5.
After the coloring the color sets are classified as(23)C1=ℐ5∪ℐ8∪…∪ℐn−2∪ℐn∪ℐS4,C2=ℐ3∪ℐ6∪…∪ℐn−4∪ℐS2∪ℐS3∪ℐS6and,C3=ℐ4∪ℐ7∪…∪ℐn−3∪ℐS1∪ℐS5∪ℐS7.
The bounds for this color partitions isC1=4n/3 and C2=C3=4n/3. It is observed that the difference between any two color classes vary by the extent value of one. Therefore it satisfies the equitable condition Ci|−|Cj≤1,for1≤i,j≤3,i≠j. Hence it is equitably 3-colorable (see Figure 8).Figure 8
Equitable vertex coloring of splittingY13, n≡1mod3.Case (iv).
Ifn is odd, n≡2mod3
In this case the independent setℐ1 is divided into ℐS1=vn,vn+1,v3n+1, ℐS2=v3n such that ℐS1⊂ℐ1 and ℐS2⊂ℐ1. Also ℐS1∪ℐS2=ℐ1. Let ℐn+1=ℐS1. The set ℐ2 is partitioned into ℐS3=v1,v2n+1,v3n+2, ℐS4=vn+2 such that ℐS3⊂ℐ2, ℐS4⊂ℐ2 and hence ℐS3∪ℐS4=ℐ2 which is represented as ℐn+2=ℐS3 . Form the union of the sets ℐS2, ℐS4 as ℐn+3=ℐS2∪ℐS4
Consider the coloring as a mapping function fromf4:ℐi,3≤i≤n+3⇒C2, where C2=1,2,3.
For3≤i≤n(24)f4ℐi=1,i≡2mod3,2,i≡1mod3,3,i≡0mod3,f4In+1=1,f4In+2=2,f4In+3=3.
Using this method the color sets are sorted as(25)C1=ℐ5∪ℐ8∪…∪ℐn∪ℐn+1,C2=ℐ4∪ℐ7∪…∪ℐn−1∪ℐSn+2,C3=ℐ3∪ℐ6∪…∪ℐn−2∪ℐn+3.
The absolute value of grouping the color classes isC1=C2=4n/3 and C3=4n/3. Clearly Ci|−|Cj≤1,for1≤i,j≤3,i≠j. It is true that equitable condition holds for this case of graph. Hence χ=SYn=3 (see Figure 9). □Figure 9
Equitable vertex coloring of splittingY11, n≡2mod3.Theorem 4.2.
The equitable vertex coloring for splitting of Antiprism graphAnis(26)χ=SAn=3,ifnis odd or even andn≡0mod3,4,ifnis odd andn≡1mod4orn≡3mod4,ifnis even andn≡1mod3orn≡2mod3,Proof.
Consider a splitting Antiprism graphSA4 (see Figure 10), which generates a graph with 16 vertices and 48 edges.
Generally, the splitting of Antiprism graphAn emerges as a graph with 4n vertices and 12n edges which is not block circulant. Its adjacency matrix can be represented in matrix blocks as follows.
Each row in the adjacency matrix of this graph portray the adjacent vertices of each vertex resulting in their neighbourhoodN. The first row corresponds to the vertex v1 shows the neighbouring elements which are represented with 1 in column-wise. (27)v1v1v2…vnvn+1vn+2…v2n01…110…0v2n+1v2n+2…v3nv3n+1v3n+2…v4n01…110…0,NV1=v2,vn,vn+1,v2n,v2n+2,v3n,v3n+1,v4n.
The second row of the adjacency matrix unfolds the neighbouring elements of the vertexv2 in this graph.(28)v1v1v2…vnvn+1vn+2…v2n10…011…0v2n+1v2n+2…v3nv3n+1v3n+2…v4n10…111…0,NV2=v1,v3,vn+1,vn+2,v2n+1,v2n+3,v3n+1,v3n+2.Similarly the successive rows upto v2nth vertex of the adjacency matrix gives the remaining neighbourhood sets of the splitting on Antiprism graph.(29)NV3=v2,v4,vn+2,vn+3,v2n+2,v2n+4,v3n+2,v3n+3,……………………Nvn−1=vn−2,vn,v2n−2,v2n−1,v3n−2,v3n,v4n−2,v4n−1,Nvn=v1,vn−1,v2n−1,v2n,v2n+1,v3n−1,v4n−1,v4n,Nvn+1=v1,v2,vn+2,v2n,v2n+1,v2n+2,v3n+2,v4n,Nvn+2=v2,v3,vn+1,vn+3,v2n+2,v2n+3,v3n+1,v3n+3,……………………Nv2n=v1,vn,vn+1,v2n−1,v2n+1,v3n,v3n+1,v4n−1.
Further the independent subsetsℐi of the neighbourhood sets Ni,i=1,2,…,n are obtained by considering the difference between the following neighbourhood sets.(30)ℐ1=Nv1−Nvn+1=vn,vn+1,v3n,v3n+1,ℐ2=Nv2−Nvn+2=v1,vn+2,v2n+1,v3n+2,ℐ3=Nv3−Nvn+3=v2,vn+3,v2n+2,v3n+3,……………………ℐn−1=Nvn−1−Nv2n−1=vn−2,v2n−1,v3n−2,v4n−1,ℐn=Nvn−Nv2n=vn−1,v2n,v3n−1,v4n.
The vertices of the independent sets are colored through the mapping functionϕ:ℐi⟶Ck, k=1,2. The color sets are C1=1,2,3 and C2=1,2,3,4.Figure 10
Splitting antiprism graphSA4.Case 5.
Ifn is odd or even, n≡0mod3
Consider the coloring as a mapping function fromϕ:ℐi⟶C1.
When1≤i≤n(31)ϕℐi=1,i≡1mod32,i≡2mod33,i≡0mod3.
Hence the vertices of the independent sets of the whole graph under this case are colored with only 3 colors (see Figure11) and can be grouped into color classes C1,C2 and C3, where C1=ℐ1∪ℐ4∪…∪ℐn−2, C2=ℐ2∪ℐ4∪…∪ℐn−1 and C3=ℐ3∪ℐ6∪…∪ℐn. The cardinal of the color sets are C1=C2=C3=4n/3 which implies the equitable condition holds for 1≤i≤3,1≤j≤3, Ci−Cj=0≤1,i≠j . Hence for the splitting antiprism graphs in this type χ=SAn=3.Figure 11
Equitable vertex coloring of splittingA12,n≡0mod3.Case 6.
(i) Ifn is odd and n≡1mod4
The independent setsℐ1, ℐ3 and ℐn−1 are split into subsets for equitable vertex coloring. The set ℐ1 is separated into subsets ℐS1=vn,v3n and ℐS2=vn+1,v3n+1, where ℐS1⊂ℐ1 and ℐS2⊂ℐ1. It implies that ℐS1∪ℐS2=ℐ1. The set ℐ3 is divided into subsets ℐS3=v2,vn+3,v3n+3 and ℐS4=v2n+2, which implies ℐS3⊂ℐ3, ℐS4⊂ℐ3 and hence ℐS3∪ℐS4=ℐ3. Also the set ℐn−1 is partitioned into two subsets ℐS5=vn−2,v2n−1,v3n−2 and ℐS6=v4n−1 such that ℐS5∪ℐS5=ℐn−1. For the coloring to be equitable form the union of the sets γk,k=1,2,3,4, where(32)γ1=I2∪IS6,γ2=IS1∪IS3,γ3=IS2∪IS5,γ4=In∪IS4.
After these reformation the coloring is allocated as a function from(33)ϕ:ℐi,4≤i≤n−2∪γk,1≤k≤4⟶C2,ϕγk=k,1≤k≤4.When 4≤i≤n−2(34)ϕℐi=3,i≡0mod44,i≡1mod41,i≡2mod42,i≡3mod4.
It requires 4 colors (see Figure12) and the color classesare(35)C1=ℐ2∪ℐ6∪…∪ℐn−3∪ℐS6,C2=ℐ7∪ℐ11∪…∪ℐn−2∪ℐS1∪ℐS3,C3=ℐ4∪ℐ8∪…∪ℐn−1∪ℐS2∪ℐS5,C4=ℐ5∪ℐ9∪…∪ℐn∪ℐS4.
The number of vertices in the color sets areC1=C2=C3=C4=n. Further the difference between any of these two color classes differs by the value of one. It confirms the equitable condition and is equitably 4-colorable.
(ii) Ifn is odd and n≡3mod4.
In this case the independent setsℐ1, ℐ2 and ℐn are divided into subsets. The set ℐ1 is partitioned into subsets ℐS1=vn,vn+1,v3n and ℐS2=v3n+1, where ℐS1∪ℐS2=ℐ1. The set ℐ2 is split into subsets ℐS3=v1,vn+2,v3n+2 and ℐS4=v2n+1, hence ℐS3∪ℐS4=ℐ2. Also the set ℐn is parted into two subsets ℐS5=vn−1,v2n,v3n−1 and ℐS6=v4n such that ℐS5∪ℐS6=ℐn. The coloring process is allocated after the union of the sets ωk,k=0,1,2,3,4, where(36)ω0=IS2∪IS4∪IS6,ω1=IS3∪I6,ω2=IS5∪I3,ω3=ω0∪I4,ω4=IS1∪I5.
The coloring is done as a function of(37)ϕ:ℐi,7≤i≤n−1∪ωk,1≤k≤4⟶C2,ϕωk=k,1≤k≤4.
For7≤i≤n−1(38)ϕℐi=2,i≡3mod43,i≡0mod44,i≡1mod41,i≡2mod4.
In this way the vertices of the independent sets are allotted with 4 colors in an uniform manner to reach the equitable condition (see Figure13). The color sets are(39)C1=ℐ6∪ℐ10∪…∪ℐn−1∪ℐS3,C2=ℐ3∪ℐ7∪ℐ11∪…∪ℐn∪ℐS5∪ℐ3,C3=ℐ4∪ℐ8∪…∪ℐn−3∪ℐS2∪ℐS4∪ℐS6,C4=ℐ5∪ℐ9∪…∪ℐn−2∪ℐS1.
The cardinal number of the color sets areC1=C2=C3=C4=n which proves that Ci−Cj=0≤1,fori≠j is equitable. In this case χ=SAn=4
(iii) Whenn is even and a multiple of 4, also n≡1mod3 or n≡2mod3
The coloring in this case is considered as a functionϕ such that ϕ:ℐi⟶C2.
For1≤i≤n(40)ϕℐi=1,i≡1mod42,i≡2mod43,i≡3mod44,i≡0mod4.
In this method all the vertices of the independent sets of this graph is colored equally by 4 colors (see Figure14) with color classes partitions as(41)C1=ℐ1∪ℐ5∪…∪ℐn−3,C2=ℐ2∪ℐ6∪…∪ℐn−2,C3=ℐ3∪ℐ7∪…∪ℐn−1,C4=ℐ4∪ℐ8∪…∪ℐn,and their cardinal numbers are C1=C2=C3=C4=n. Thereof satisfies the equitable condition Ci−Cj≤1fori≠j. Hence under both these cases n≡1mod3 or n≡2=mod3, χ=SAn=4.
(iv) Whenn is even and not a multiple of 4, along with n≡1mod3 or n≡2mod3
In this case the independent setsℐ1 and ℐn are divided into subsets. The set ℐ1 is parted into subsets ℐS1=vn,vn+1 and ℐS2=v3n,v3n+1, where ℐS1∪ℐS2=ℐ1. Also the set ℐn is partitioned into two subsets ℐS3=vn−1,v2n and ℐS4=v3n−1,v4n such that ℐS4∪ℐS6=ℐn.
The coloring is defined as a functionϕ:ℐSk,1≤k≤4∪ℐi,i=2,3,…n−1⟶C2.(42)ϕℐS1=4,ϕℐS2=3,ϕℐS3=1,ϕℐS4=2.
When2≤i≤n−1(43)ϕℐi=1,i≡2mod42,i≡3mod43,i≡0mod44,i≡1mod4.
It is observed that all the vertices under this case of the graph are colored equally with 4 colors (see Figure15), thus grouping the color classes as(44)C1=ℐ2∪ℐ6∪…∪ℐn−4∪ℐS3,C2=ℐ3∪ℐ7∪…∪ℐn−3,∪ℐS4,C3=ℐ4∪ℐ8∪…∪ℐn−2∪ℐS2,C4=ℐ5∪ℐ9∪…∪ℐn−1∪ℐS1,with cardinal numbers as C1=C2=C3=C4=n. Hence it is suffice to prove the equitable condition Ci−Cj≤1fori≠j. Also in these cases n≡1mod3 or n≡2mod3, χ=SAn=4. □Figure 12
Equitable vertex coloring of splittingA13,n≡1mod4.Figure 13
Equitable vertex coloring of splittingA11,n≡3mod4.Figure 14
Equitable vertex coloring of splittingA16,n≡1mod3.Figure 15
Equitable vertex coloring of splittingA14,n≡2mod3.Theorem 4.3.
The vertex coloring on splitting of crossed prism graphRnis equitably 2- colorable.i.e,χ=SRn=2.Proof.
Consider a splitting crossed prism graphSR6 (see Figure 16), which generates a graph with 24 vertices and 54 edges.
Generally, the crossed prism graph contains2n vertices and 3n edges and the splitting of crossed prism graph Rn promotes a graph with 4n vertices and 9n edges which is not block circulant on the whole matrix. The adjacency matrix of SRn can be generalized in blocks as follows
The neighbouring elementsN of the vertices to this splitting graph corresponds to each row in the adjacency matrix. The first row relate to the vertex v1 shows the neighbouring elements which are represented as 1 in column-wise. (45)v1v1v2…vnvn+1vn+2…v2n01…101…0v2n+1v2n+2…v3nv3n+1v3n+2…v4n1…101…0,NV1=v2,vn,vn+2,v2n+2,v3n,v3n+2.
The second row present the neighbouring elements of the vertexv2 in this graph.(46)v2v1v2v3…vnvn+1vn+2…v2n101…001…0v2n+1v2n+2v2n+3…v3nv3n+1v3n+2…v4n101…001…0,NV2=v1,v3,vn+1,v2n+1,v2n+3,v3n+1.
Consider the consecutive rows in the adjacency matrix of crossed prism graph up tonth vertex.(47)NV3=v2,v4,vn+4,v2n+2,v2n+4,v3n+4,……………………,Nvn=v1,vn−1,v2n−1,v2n+1,v3n−1,v4n−1.
The independent subsetsℐi,i=1,2,…,n of this graph is obtained by taking the difference of the neighbourhood sets Ni,i=1,2,…,n as follows.(48)ℐ1=Nv1−Nv3=vn,vn+2,v3n,v3n+2,ℐ2=Nv2−Nv4=v1,vn+1,v2n+1,v3n+1,ℐ3=Nv3−Nv5=v2,vn+4,v2n+2,v3n+4,……………………,ℐn−1=Nvn−1−Nv1=vn−2,v2n,v3n−2,v4n,ℐn=Nvn−Nv2=vn−1,v2n−1,v3n−1,v4n−1.
The coloring of this graph is accomplished by allocating colors to the vertices of the independent sets. Define a functionϕ such that ϕ:ℐi⟶C, where C=1,2.(49)ϕℐi=1,ifi≡1mod22,ifi≡0mod2.
Through this method it needs only 2 colors for coloring the splitting crossed prism graph and found to be equitably allotted (see Figure17). Let the two color classes be C1=ℐ1∪ℐ3∪…∪ℐn−1 and C2=ℐ2∪ℐ4∪…∪ℐn. Here C1=C2←=2n, thus satisfies the equitable condition C1−C2=0≤1. Hence χ=SRn=2. □Figure 16
Splitting crossed prism graphSR6.Figure 17
Equitable vertex coloring of splittingR10,n≡0mod2.Theorem 4.4.
The vertex coloring on splitting of closed sun graphSn¯n≥4is equitable.i.e,χ=SSn¯=n.Proof.
Consider a splitting closed sun graphSS4¯ (see Figure 18), which generates a graph with 16 vertices and 54 edges.
Generally, the block circulant closed sun graph contains2n vertices and 4n+2 edges and the splitting of closed sun graph Sn¯ has 4n vertices and 3n2+15n/2 edges which is not block circulant on the whole matrix. The adjacency matrix of SSn¯ can be generalized in blocks as follows.
The neighbourhoodN for each vertices of the graph can be identified from the rows of the adjacency matrix of this graph. The first row corresponds to the vertex v1 whose neighbouring elements are represented with 1 in column-wise. (50)v1v2…vnvn+1vn+2…v2nv101…110…1v2n+1v2n+2…v3nv3n+1v3n+2…v4n.01…110…1NV1=v2,v3,…vn,vn+1,v2n,v2n+2,v2n+3,v2n+4,…v3n,v3n+1,v4n.
The neighbouring elements of the vertexv2 are identified from the second row of the adjacency matrix.(51)v1v2…vnvn+1vn+2…v2nv210…111…0v2n+1v2n+2…v3nv3n+1v3n+2…v4n10…111…0,NV2=v1,v3,…vn,vn+1,vn+2,v2n+1,v2n+3,v2n+4,…v3n,v3n+1,v4n−1.The neighbours of the remaining successive rows upto nth are obtained from the adjacency matrix of the splitting on closed sun graph.(52)NV3=v1,v2,v4…vn,vn+2,vn+3,v2n+1,v2n+2,v2n+4,…v3n,v3n+2,v3n+3,……………………,Nvn−1=v1,v2,…vn−2,vn,v2n−2,v2n−1,v2n+1,v2n+2,…v3n−2,v3n,v4n−2,v4n−1,Nvn=v1,v2,…vn−1,v2n−1,v2n,v2n+1,v2n+2,…v3n−1,v4n−1,v4n.
The independent subsets of the neighbourhood setsNi,i=1,2,…,n are obtained from the difference between the neighbourhood sets in the following pattern.(53)ℐ1=Nv1−Nv2=v2,v2n,v2n+2,v4n,ℐ2=Nv2−Nv3=v3,vn+1,v2n+3,v3n+1,ℐ3=Nv3−Nv4=v4,vn+2,v2n+4,v3n+2,……………………,……………………,ℐn−1=Nvn−1−Nvn=vn,v2n−2,v3n,v4n−2,ℐn=Nvn−Nv1=v1,v2n−1,v2n+1,v4n−1.
The coloring is defined as a functionϕ such that ϕ:ℐi⟶C1, where C1=1,2,…n.(54)ϕℐi=i,for1≤i≤n.
By this process of coloring it requires 6 colors for coloring theSS6¯ (see Figure 19). In general, it requires n colors for the entire graph. The allotment of colors induces the color classes as C1=ℐ1,C2=ℐ2,…Cn=ℐn which implies Ci=n,i=1,2,…n is equitable. Therefore the inequality Ci−Cj≤1fori≠j is true. Hence χ=SSn¯=n. □Figure 18
Splitting closed sun graphSS4¯.Figure 19
Equitable vertex coloring of splittingS6¯.


## 5. Conclusion and Future works

The study on block circulant graphs is considered in this paper. Only very few research works has been done so far in the area of block circulant graphs. This area of research is active and can be explored for various graphs of this type. The goal of this paper is to determine equitable chromatic bounds of splitting block circulant graphs. We have proposed a new approach to compute the chromatic number by generalization of adjacency matrix and deriving the independent sets of the splitting block circulant graphs. Hence the coloring becomes easier by assigning colors to the independent sets. The limitations of this work is such that the independent sets obtained from the difference of neighbourhood sets may not have uniform cardinality for various other graphs, which restricts the task of achieving equitable coloring in a rapid way. Future work could include obtaining the bounds of equitable chromatic number for splitting different block circulant graphs, splitting bipolar fuzzy graphs and splitting inverse fuzzy mixed graphs.


## 6. FundingStatement

No funding were used to support this study.



---

*Source: 7603023-2022-11-08.xml*