Applied and Computational Mathematics
Volume 5, Issue 5, October 2016, Pages: 202-206

Smarandachely Adjacent-Vertex-Distinguishing Proper Edge Chromatic Number of CmKn

Shunqin Liu

School of Information & Technology, Xiamen University Tan Kah Kee College, Zhangzhou, China

Shunqin Liu. Smarandachely Adjacent-Vertex-Distinguishing Proper Total Coloring Number of CmKn. Applied and Computational Mathematics. Vol. 5, No. 5, 2016, pp. 202-206. doi: 10.11648/j.acm.20160505.13

Received: September 23, 2016; Accepted: October 13, 2016; Published: October 17, 2016

Abstract: According to different conditions, researchers have defined a great deal of coloring problems and the corresponding chromatic numbers. Such as, adjacent-vertex-distinguishing total chromatic number, adjacent-vertex-distinguishing proper edge chromatic number, smarandachely-adjacent-vertex-distinguishing proper edge chromatic number, smarandachely-adjacent-vertex-distinguishing proper total chromatic number. And we focus on the smarandachely adjacent-vertex-distinguishing proper edge chromatic number in this paper, study the smarandachely adjacent-vertex-distinguishing proper edge chromatic number of joint graph CmKn.

Keywords: Graph Theory, Joint Graph, Smarandachely Adjacent-Vertex-Distinguishing Proper Edge Chromatic Number

1. Introduction

Coloring problem in graph theory, is one of the most famous NP-complete problems. Four color conjecture which is one of the world’s three major mathematical conjecture says that each map can be used only four colors to dye, and no two adjacent areas dyed the same color. In the spring of 1976, with the help of the computer, the four color conjecture was proved. The conjecture finally became a theorem. The significance of graph coloring theory is much more than that. Known to all, coloring problems can solve many problems such as scheduling problem, time tabling, transportation, arrangement, circuit design and storage problems.

In recent years, more and more coloring problems was put forward by experts of graph theory, such as proper-adjacent- vertex-distinguishing edge coloring, proper -adjacent- vertex-distinguishing total coloring, smarandachely adjacent- vertex-distinguishing proper edge coloring.

2. Smarandachely Adjacent-Vertex-Distinguishing Proper Edge Coloring

Definition 1[1] A k-proper edge coloring of a graph  is a mapping from tothat satisfies the condition described as below:

For,, if  have a common end vertex, then .

The number has a k-proper edge coloring of graph } is called the proper edge chromatic number of , denoted by . If , then we call the number to be the color of edge .

Definition 2[1] A k-proper edge coloring  is called a k-proper-adjacent-vertex-distinguishing proper edge coloring, short for k-AVDPEC when satisfies condition described as below:

Denote for every vertex , if for, we have .

The number has a k-proper-adjacent- vertex-distinguishing proper edge coloring} is called the adjacent –vertex-distinguishing proper edge chromatic number and denoted by . Set is called the color set of the vertex.

Definition 3[1] A k-proper edge coloring is called a smarandachely adjacent- vertex-distinguishing proper edge coloring, short for k-SA when  satisfies conditions described as below:

Denote for every vertex , if , we have and  mean well.

The number  is called the smarandachely adjacent-vertex-distinguishing proper edge chromatic number of , denoted by .

It’s obviously of below conclusion: when have a vertex who’s degree equal to 1, then have no k-SA for all nature number k.

The paper use to denote the graph of circle with vertices and to denote the complete graph with vertices, use  to denote the joint graph of and . We denote the vertex sets and the edge set of the graphs such that:

, , .

is the degree of the vertex ,is the maximum degree of the graph discussed, S is the universal set of the color used, that , is the complement of .

Lemma 1 [1] If denote the graph have no one degree vertex, then

1) , if  is a regular graph then.

2) .

Lemma 2 [1] If is the complete graph with vertices ,, then

.

Lemma 3[2] If is the complete graph with vertices ,and is even, then .

3. Smarandachely Adjacent-Vertex-Distinguishing Proper Edge Coloring of Cm∨Kn

Theorem 1 If ,,are both even, then have no .

Proof Suppose that  have a , then . Be aware of the facts that:

Then

(1)

,is adjacent to ,so , so

(2)

Inferred from (1) and (2), then each vertex has one different color from each other.

Then we may as well suppose that , for.

Then it must have the result such as ,  (otherwise, if there exists a color and exists a vertex  satisfies, then we can deduce the result such as , but the vertexis adjacent to the vertex , this result is in contradiction with the definition of ). Now we consider all vertices of the whole graph  who satisfy , according to previous discussion, except vertex, all the remaining  vertices of the graph  satisfied the condition , that is to say, except the vertex, the remaining  vertices form a matching, this result is in contradiction with the fact such as that is odd.

So, have no .

Theorem 2 If, is even, then

.

Proof Be aware of the fact that the maximum degree of graph is , by the 2) of Lemma 1, we get the result such as, also because of the fact that is even, then by theorem 1, the graphhave no , so we get the result such as .

For the subgraph, by lemma 3, there is a -proper edge coloring on, that is to say, there is a mapping from to  satisfied that,, if have a common end vertex, then .

Now we define a mapping from to described as below:

If , then , then  , for ,

,

,

,

,

,

,

,

,

,

,

,.

By the definition of , we get the andof every vertex of the graph such as below:

,,

,,

,

,

,

,,

.

We can see that

,

,

,

,

.

So the givenis a  for .

That is to say

.

Example 1 For , then .

In fact, for the subgraph  of , we defined a 5-proper edge coloring  such that:

,

,

,

,

.

Obviously, every adjacent edge have different colors, sois a 5-proper edge coloring of.

Then, for graph, we define the mapping from to  described as below:

For edge ,,

,

,

,

,

,

,

,.

We can see that the  and of every vertex for graph  are described as below:

,

,

,,

,,,

,,

,.

We can see that the color set of the adjacent vertices meet the requirements of definition[3], sois a  for , then.

Theorem 3 If, is even, then

.

Proof Because of the fact that the maximum degree of the graphis , by the 2) of Lemma 1, we get the result such as .

For the subgraph  of the graph , by lemma 3, there is a -proper edge coloring on, that is to say, there is a mapping from to that is satisfied the conditions such as:

,, if have a common end vertex, then .

Now we define a mapping from to as below:

If , then , then  ,,

,

,

,

,

,

,

.

By the definition of , we get that the and of every vertex as below:

,

,,

,

,

,

,

,

,

.

We can see that

,

,

,

, ,

.

That is to say, all the vertices have color sets that are not contained in other color set of the adjacent vertices. So the givenis a  for .

So .

Example 2 For , then .

In fact, we defined the mapping from to as below:

,

,

,

,

,

,

.

We can see that

,,

,,

,,.

Obviously,  is a  for .

So .

4. Conclusion

Coloring problem is a classical difficult problem of graph theory. Smarandachely adjacent- vertex-distinguishing proper edge coloring was first put forward by Zhang Zhong-fu in 2008. A lot of problems need to be solved urgently, such as finding out the smarandachely adjacent-vertex-distinguishing proper edge chromatic number, such as how smarandachely adjacent-vertex-distinguishing proper edge chromatic number changes when the vertices n grows.

In the paper, we deduce the smarandachely adjacent-vertex -distinguishing proper edge chromatic number of the joint graph  by the methods of combination analysis and reduction to absurdity, also the method of apagoge.

References

1. Liu Shun-qin, Chen Xiang-en. "Smarandachely Adjacent-Vertex-distinguishing proper edge coloring of ". vol.41, pp. 155-158. August. 2015.
2. Bondy. J .A. MURTY U S R. Graph Theory. London. Springer.2008.
3. Zhang Zhong-fu, Chen Xiang-en, Li Jing-wen. "On adjacent –vertex-distinguishing total coloring of graphs." Sci. China. Ser. vol. 48. pp. 289-299. June. 1997.
4. Chen Xiang-en, Zhan-fu, "Adjacent-Vertex-Distinguishing Total Chromatic Number of Pm×Kn,"Journal of Mathematical Research and Exposition, Dalian.vol. A26, pp.489-494. August. 2015.
5. Liu Shun-qin, Chen Xiang-en. "Smarandachely Adjacent-Vertex-distinguishing proper edge coloring of ". vol.37,pp.139-145.April.2011.
6. Tian Jing-jing. "The Smarandachely Adjacent –Vertex –Eege Coloring of Some Mycielski’s Graph". J. of. Math (PRC). vol. 32. pp. 723-728. April 2012.
7. Qiang Hui-ying, Li mu-chun. "A Bound on Vertex Distinguishing Total Coloring of Graphs with Distance Constrant for Recurrent Event Data".Acta Mathematicae Applicatae Sinica. vol. 34. pp. 554-559. May. 2011.
8. Tian Jing-jing, Deng Fang-an. "Adjacent Vertex-Distinguishing VE-Total Chromatic Number of the Crown Graph Cm.Fnand Cm.Cn".Mathematics in Practice and Theory. vol. 41. pp. 189-192. August. 2011.
9. Tian Jing-jing. "The Smarandachely Adjacent –Vertex –Eege Coloring of Some Mycielski’s Graph". J. of. Math(PRC). vol. 32. pp. 723-728. April 2012.
10. Lin Sun, Xiaohan Cheng, Jianliang Wu. "The Adjacent Vertex Distinguishing Total Coloring of Planar Graphs without Adjacent 4-cycles" J. Comb. Optim. DOI 10.1007/S10878-016-0004-1.11March.2016.
11. Xiaohan Cheng,Guanghui Wang,Jianliang Wu."The AdjacentVertex Distinguishing Total Chromatic Numbers of Planar Graphs with=10" J. Comb. Optim. DOI. 1007/S10878-016-9995-x.04February.2016.
12. Huijuan Wang,Bin Liu, Yan Gu, Xin Zhang."Total Coloring ofPlanar Graphs without Adjacent short cycles" J. Comb. Optim. DOI.1007/S10878-015-9954-y.16. September. 2015.
13. Liu Hua, Feng Jianhua,Ma Shaoxian."Adjacent Vertex-Distinguishing Edges coloring ofSm . Sn"Journal of East China Jiao-tong University.vol.24.pp.157-158.October.2007.
14. Zhang Donghan, Zhang Zhongfu. "The Upper Bound of Adjacent Vertex Strongly Distinguishing Total Chromatic Number of the Graph".Advances of Mathematics.vol.40.No.2.pp.168-172.April.2011.
15. Zhang Z F, Liu L Z, Wang J F. "Adjacent strong edge coloring of graphs". Appl Math Lett. vol. 15. pp. 623-626. April. 2002.
16. Shunqin Liu. "Several Kinds of Chromatic Numbers of Multi-fan Graphs". Applied and Computational Mathematics. vol. 5. No. 3. pp. 133-137. June. 2016.
17. Wang YQ, Sun Q, Tao X, Shen L."Plane graphs with maximum degree 7 and without 5-cycles with chords are 8-totally-colorable. Sci. China A. vol. 41. pp. 95-104. February. 2011.
18. Wang B, Wu JL, Wang HJ. "Total coloring of planar graphs without chordal short cycles". Graphs Comb. Optim. vol. 60: 777-791. 2014.

 Contents 1. 2. 3. 4.
Article Tools