Smarandachely Adjacent-Vertex-Distinguishing Proper Edge Chromatic Number of C_{m}∨K_{n}
Shunqin Liu
School of Information & Technology, Xiamen University Tan Kah Kee College, Zhangzhou, China
Email address:
To cite this article:
Shunqin Liu. Smarandachely Adjacent-Vertex-Distinguishing Proper Total Coloring Number of C_{m}∨K_{n}. 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 C_{m}∨K_{n}.
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