On Chromatic Degree Partition Number of a Graph

On Chromatic Degree Partition Number of a Graph

N. Malathi (1), M. Bhuvaneshwari (2), Selvam Avadayappan (3)

(1) Department of Mathematics, V.V.Vanniaperumal College for Women, Virudhunagar, India

(2,3) Research Department of Mathematics, VHN Senthikumara Nadar College, (Affiliated to Madurai Kamaraj University)

Virudhunagar, India

Abstrat – Major Corporations rely on partitioning certain group of individuals or components to ensure the systematic functioning of the projects in some situations. The Graph Theoretical approach makes our work easier. We introduce the concept chromatic similar degree partitioning. A partition of the vertex set () is defined to be a chromatic similar degree partition of if each partition class is independent and the absolute difference of the sum of the degrees of all vertices between any two partition classes is at most 1. The maximum cardinality and the minimum cardinality taken over all the chromatic similar degree partition number of the graph are called the Max Chromatic Degree Partition Number and Min Chromatic Degree Partition of and are denoted by () and () respectively. In this paper we attempt to prove some theorems

on these parameters.

AMS Subject Classification Code (2010): 05C (Primary)

Keywords: Degree Partition Number, Partitions in Graphs, Colour Partitioning, Chromatic Partitioning

1. INTRODUCTION

   In this we paper, we consider only undirected simple connected graphs. For the basic definitions and notations of graph theory, we refer the text book by Harary [2]. A finite non- empty set of objects called vertices together with a set of unordered pairs of distinct vertices of

   called edges is called a graph . Throughout this paper, the vertex set and edge set of are denoted by () and () respectively. The number of vertices and the number of edges in a graph are called its order and its size respectively.

   The number of edges incident with a vertex is called the degree of the vertex and it is denoted by deg . The vertex of degree 1 is called full vertex. The sum of the degree of all the vertices in a set () is denoted by ().

   If all the vertices are of same degree say , then the graph is said to be an graph. Suppose that the degree of every vertex of a graph is either or , then is called an (, ) graph. The ( 1) graph is called the Complete Graph denoted by and 0 graph is called totally disconnected which is denoted by . A 2 graph of order is called cycle and the graph obtained by removing one of the edges of is called the path . The minimum and maximum degree among the vertices of G are denoted by () and () respectively.

   The given two graphs and with same order and size are said to be isomorphic if there exists a bijection between () and () preserving the adjacency. In this case we write

   .

   A vertex partition of a graph is a collection of disjoint subsets of () whose union is (). Also, each smaller sets are called the partition classes of (). Each subset in the partition is called a partition class of (). A vertex partition is said to be an isolated partition if each partition class contains exactly one vertex and the class which contains exactly one vertex is called an isolated partition class.

   A subset of () is called an independent set of if no two vertices in are adjacent. A graph is known to be a bipartite graph if the vertex set of can be partitioned into two independent sets say 1 and 2. The complete bipartite graph , is nothing but the bipartite graph with |1| = and |2| = in which every vertex in 1 is adjacent to every vertex in 2. The graph 1, is called the star graph.

   Whenever the vertex of a graph can be partitioned into independent sets, is called a k-partite graph. The Turan graph (, ) is the complete graph on vertices whose partite sets are as nearly equal in cardinality as possible. It is noticeable that (, 1)

   . Always, the number of vertices in each partite set in (, ) is either

   or

   and the

   number of vertices in each partite set in (, ) is same if and only if 0( ).

   The join of two graphs and , denoted by is obtained from , by joining each vertex of to every vertex of by means of an edge. The wheel graph ( 4) is nothing but 11.

   The graph ( 4) on n vertices with degree sequence 1,

   2, ,

   2

   ,

   2

   , , 2,1 is called the irregular most graph [3].

   The partitioning of the vertex set by means of distinct independent sets is called proper colour partition of . The proper colour partition with minimum possible number of

   independent sets is called the minimum proper colour partition and such number is called the chromatic number of , (). Many researchers studied on this concept which can be referred from [1], [6], [7] and [8].

   The similar degree partition of a graph is defined as the partition {1, 2, , } of

   () such that |( ) ()| 1 for every 1 , . The similar degree partition of with the maximum possible number of partition classes is called the max-similar degree partition of . The cardinality of the max-similar degree partition is called the degree partition number of denoted by (). More results on this parameter can be found in [3], [4] and [5].

   A proper colour partition of G is said to be chromatic similar degree partition if the absolute difference between the degree sum of any two colour classes is at most 1. The maximum value and the minimum value among all the chromatic similar degree partition of the graph are called the max-chromatic degree partition number () and the min-

   chromatic degree partition number () respectively, if such partition exists. Otherwise

   () and () are defined to be infinity. The chromatic similar degree partitions with

   () and ()classes are called max-chromatic similar degree partition and min- chromatic similar degree partition respectively. A graph is said to have unique chromatic similar degree partition if () is uniquely partitioned into chromatic similar degree partition classes.

2. Main Results

   In this section, we establish some interesting facts and results on our parameters.

   Observation 1 For any graph , () (), if such partition exists. Observation 2 For any graph , () (), if such partition exists. Observation 3 For any graph , () (), if such partition exists.

   Proof () gives the maximum possible number of similar degree partition classes. So,

   () can be at most () if such number exists.

   Observation 4 () =1 if and only if .

   Proof The result follows as () = 1 if and only if .

   Observation 5 For any connected non-trivial graph , () > 1 and () > 1

   Proof The result is obvious as () > 1 if and only if . Observation 6 The full vertex of any graph of order forms an isolated partition in any chromatic similar degree partition if such partition exists.

   Proof Any subset of () with at least two vertices containing the full vertex cannot be

   independent. So, the full vertex must form an isolated partition class in any chromatic similar degree partition if such partition exists.

   Observation 7 If is a non-trivial graph such that () = 1, then both () and

   () cannot be finite.

   Proof In viewing observations 1, 3 and 5, the result is quite possible.

   Observation 8 If is either or an ( 1, 2) biregular graph with vertices where

   4, () = .

   Proof As possess at least one full vertex, the degree sum of any partition class must range from 2 to . But there cannot be any partition class with degree sum . So, the only

   possible chromatic similar degree partition is the isolated partition.

   Theorem 9 () = 2 if and only if is bipartite.

   Proof As () = 2 if and only if is bipartite, the theorem holds. Theorem 10 () = if and only if is either or (, + 1) . Proof As () = if and only if is either or (, + 1) [3], the result follows easily.

   Observation 11 ((, )) = .

   Proof As (, ) is a ( , + 1) graph, the result follows easily.

   Theorem 12 Let denote the smallest prime number such that |. Then () = .

   Proof As is 2 , () must be the smallest factor of greater than 1. So, () .

   Also, since 0( ), we can partition the vertex set of into independent sets, each

   consisting of vertices as follows.

   1 = {1, +1, , +1},

   2 = {2, +2, , +2}, .,

   = {, 2, , }

   Then = {1, 2, , } constitute our required min-chromatic degree partition of .

   Theorem 13 Let G contain ( ) full vertices. Then

   ()+

   ( ) () if such

   partition exists.

   2

   Proof Let 1, 2, , be the full vertices of . Then in any chromatic similar degree partition (if exists), these vertices should form isolated partition classes.

   Suppose () = . Then classes namely 1, 2, , must be isolated. Also, ( ) =

   1 for 1 . Therefore, for the remaining classes +1, +2, , , () is either or 2 for + 1 .

   As the degree sum of these classes is at least 2,

   =1

   Thus, () = ( ) ( 1) + ( )( 2)

   = ( 2) +

   This forces that ()

   2

   ()

   2

   The other side of the inequality follows in a similar way.

   The analogous of this result for max-chromatic similar partition can be stated as follows:

   Theorem 14 Let G contain ( ) full vertices. Then

   ()+

   ( ) () if such

   partition exists.

   2

   The proof is very similar to Theorem 13.

   5 = 5

   Theorem 15 () = () = { 4 1( 3)}

   Proof Clearly 4 4 and 5 is (4,3) .

   So, (4) = (4) = 4 and (5) = (5) = 5

   Now, we consider 6. Let () = {1, 2, , } where be the full vertex.

   Since ( )

   ()+1

   ()1

   = 4 4,

   =

   2

   = 4 for 6.

   Thus by Theorems 13 and 14, () = () = 4 if such partition exists.

   We already see that, in a similar degree partition of , the full vertex can form an isolated partition only when 1( 3) for 6. [5]

   Thus, the chromatic similar degree partition exists only when 1( 3).

   Hence, () = () = whenever 1( 3) and 6.

   When 1( 3), 1 = {1, 4, , 3}, 2 = {2, 5, , 2}, 3 = {3, 6, , 1}

   and 4 = {} is the required chromatic similar degree partition.

   So, () = () = 4 whenever 1( 3).

   Theorem 16 For 3, ( ) = ( ) .

   2

   = + 1

   Proof The degree sequence of is

   and it has one full

   vertex.

   Now, () = (1)

   2

   ( 1, 2, , , , ,2,1)

   2 2

   + =

   2 2

   +

   2 2

   So, () = {

   2 2

   }

   21

   2

   2+2

   Now

   ()+1

   2

   = { 2+1 }

   2

   +

   = {

   2

   +

   2

   1

   }

   1

   2

   + 1

   = {

   2

   } as 3

   2

   Also,

   ()1

   22

   2(2)

   = {

   2

   23

   }

   2(2)

   22+24+2

   = { 2(2)

   }

   22+24+1

   2(2)

   + 1 + 1

   = {

   2

   2

   + 1 +

   2

   1

   2(2)

   }

   + 1

   = {

   2

   } as 3

   + 1

   2

   2

   + 1

   = {

   +2 }

   2

   + 1

   = {2 }

   +1

   2

   2

   + 1

   = {

   }

   2

   Hence,

   (

   ) =

   ()

   = + 1

   2

   if such partition exists.

   1 1

   We label the vertices of as 1, 2, , such that deg = {

   2

   = }

   1 ,

   It may be noted that for

   is adjacent to

   ,

   , ,

   ,

   is adjacent to

   2

   1

   2

   1, 2, , +1, 1, , 1, and is adjacent to 1, 2, ,

   2+1

   Case i Let be even.

   Consider +1 = {1, 2, , +1} where 1 = {1, 3},

   2 2

   2 = {2, 4}, , 2 = {2, } , 1 = {1, } , = {1} and +1 = {2}

   2 2 2 2 2 2 2

   which is the required chromatic similar degree partition.

   Case ii Let n be odd.

   In this case we take, +1 = {1, 2, , +1} where 1 = {1, 2},

   2 2

   2 = {2, 3}, , 3 = {3, +1} , 1 = {1, } +1 = {1} which is the

   2 2 2 2 2 2

   required chromatic similar degree partition.

   Hence, for any 3,

   (

   ) =

   (

   )

   = + 1

   2

   Theorem 17 Let 1 1 where 4. Then

   3 = 4,5

   () = { 4 > 5 1,2( 3)}

   and () = { 4 1,2( 3)}.

   Proof The degree sequence of is ( 1,33, 22) and has one full vertex. Clearly, () = 1 + 3( 3) + 2(2) = 4 6 and so

   () + 1

   =

   4 5

   = 4

   5 3 = 4,5 = { }

   4 > 5

   and

   ()1

   47 1

   2

   =

   2

   = 4 +

   = 4 as 4.

   2

   So, if chromatic similar degree partition exists,

   () {3 = 4,5} and

   4 > 5

   () 4 for any 4.

   The chromatic similar degree partition, for the case 4 and 5 are illustrated in Figure 1. Now, for 6, () = () = 4 if any chromatic similar degree partition exists.

   3 2 2

   Let () = {1, 2, . . , } such that deg = { 2 = 1, 1 }.

   1 =

   1

   3

   1

   1

   1

   2 4

   2 3

   1

   2 3 2 3

   4 2 3 4

   Min-chromatic Similar Degree Partition Max-chromatic Similar Degree Partition

   Figure 1

   Clearly, {} forms an isolated partition in chromatic similar degree partition. So, we need there more independent classes from {1, 2, . . , 1} which are 1 = {1, 4, }, 2 =

   2, 5, } and 3 = {3, 6, }.

   If 0( 3), then 1 2 and (1) = 1, (2) = 1 and (3) = 3, which is not a similar degree partition.

   So, () = () = if 0( 3)

   Next, if 1( 3), then 1 3 and (1) = 2, (2) = 1 and (3) =

   2.

   Also, if 2( 3), then 1 1 and (1) = 1, (2) = 2 and (3) =

   2.

   Hence, () = () = 4 if 1,2( 3).

   Theorem 18

   ((, )) = { 0( ) = 1,2 = 3,4} for 3

   and 1.

   Proof By Observation 2, () .

   Also, the result is obvious when = 1 2 or = 3 4 5.

   Now, the colour classes in the k-colouring partition 6 consists of

   vertices.

   vertices or

   Without loss of generality, we assume that the colour classes 1, 2, , ( ) contains

   vertices and , , , contains

   +1 +2

   vertices.

   , 1

   deg = { }

   So, () = {

   (

   (

   , + 1

   ) 1

   }

   ) + 1

   By taking = , for any 1 and + 1 ,

   ( ) ( ) 0( )

   () ( ) = {( + 1)( ( + 1)) ( ) }

   }

   = { 0 0( )

   2 1

   But the case 2 1 = 1 is impossible when 3 and 6. Thus ((, )) = whenever 0( ).

   In addition, for any 6, 3 and 0( ), the only possible chromatic similar

   degree partition is isolated partition and hence ((, )) = .

   Corollary 19 Let be a ( 2) graph, 3. Then

   () = .

   2

   Proof As is ( 2) , is even.

   Each vertex in is not adjacent to exactly one vertex. So, is

   (,

   ) 2

   graph.

   Hence by the above theorem,

   () = .

   2

   Theorem 20 Let be a ( 3) graph where 4. Then

   0( 3) (, )

   3 3

   () =

   2

   0( 2)

   { }

   Proof G can be obtained by removing a spanning cycle or a vertex disjoint union of cycles which covers all the vertices of , from .

   Case i Let G be obtained by removing vertex disjoint union of 3s.

   In this case, 0 ( 3) and

   (,

   ). 3

   So,

   () =

   3

   Case ii Let G be obtained by removing at least one cycle of length at least 4.

   Without loss of generality, let 0, 1, 2, , , 0 ( 3) be a cycle removed to obtain . Clearly is non-adjacent to 1 and +1 where 0 and the addition and subtraction are taken over modulo .

   Also, 1 and +1 are adjacent in .

   So, from these vertices 1, 2, , 1, +1, , , a maximum of two vertices can be in a chromatic similar degree partition whose degree sum will be 2( 3).

   In order to attain the required degree sum, all the vertices in should be partitioned into

   2

   classes of non-adjacent vertices.

   So, whenever 0 ( 2), this partition is possible and so

   () = .

   2

   And suppose 0( 2) or is obtained from by removal of a cycle of length at least 4, () = as the only possible chromatic similar degree partition is isolated partition.

3. REFERENCES

1. Alexey Pokrovskiy, (2012). Partitioning edge-coloured complete graphs into monochromatic cycles and paths, Journal of Combinatorial Theory, Series B.

2. Harary. F, Graph Theory, (1972). Addison-Wesly, Reading Mass.

3. Malathi. N, M. Bhuvaneshwari and Selvam Avadayappan, (2021). A Note on Degree Partition Number of a Graph, Journal of Emerging Technologies and Innovative Research, Volume 8, Issue 7, Pages a717-a722.

4. Malathi. N, M. Bhuvaneshwari and Selvam Avadayappan, (2023). More Results on Degree Partition Number, Advances and Applications in Mathematical Sciences, Volume 22, Issue 8, Pages 1905 1914.

5. Malathi. N, M. Bhuvaneshwari and Selvam Avadayappan, (2025). Degree Partition Number of Some Derived Graphs, IAENG International Journal of Applied Mathematics, Volume 55, Issue 6, Pages1865- 1872.

6. Sampathkumar. E, (1976). Partition graphs and coloring numbers of a graph. Discrete Mathematics – DM.

   16. 57-60. 10.1016/0012-365X (76) 90093-5.

7. Shoham Letzter, (2019). Monochromatic cycle partitions of 2-coloured graphs with minimum degree 3n/4, the electronic journal of combinatorics, Volume 26, Issue 1.

8. Yegnanarayanan. V, (2001). Graph colourings and partitions, Theoretical Computer Science, Volume 263, Issues 12, Pages 59-74.