Advanced
A NEW VERTEX-COLORING EDGE-WEIGHTING OF COMPLETE GRAPHS
A NEW VERTEX-COLORING EDGE-WEIGHTING OF COMPLETE GRAPHS
Journal of Applied Mathematics & Informatics. 2014. Jan, 32(1_2): 1-6
Copyright © 2014, Korean Society of Computational and Applied Mathematics
  • Received : March 17, 2013
  • Accepted : July 03, 2013
  • Published : January 28, 2014
Download
PDF
e-PUB
PubReader
PPT
Export by style
Share
Article
Author
Metrics
Cited by
TagCloud
About the Authors
MOHAMMAD REZA FARAHANI

Abstract
Let G = ( V ; E ) be a simple undirected graph without loops and multiple edges, the vertex and edge sets of it are represented by V = V ( G ) and E = E ( G ), respectively. A weighting w of the edges of a graph G induces a coloring of the vertices of G where the color of vertex v , denoted Sv :=Σ ev w ( e ). A k-edge-weighting of a graph G is an assignment of an integer weight, w ( e ) ∈ {1,2,..., k } to each edge e , such that two vertex-color Sv , Su be distinct for every edge uv . In this paper we determine an exact 3-edge-weighting of complete graphs k 3q+1 q ∈ ℕ. Several open questions are also included. AMS Mathematics Subject Classification : 05C15, 05C78.
Keywords
1. Introduction
Let G = ( V ; E ) be a simple undirected graph without loops and multiple edges, the vertex and edge sets of it are represented by V = V ( G ) and E = E ( G ), respectively. A weighting w of the edges of a graph G induces a coloring of the vertices of G .
A k-edge-weighting of a graph G is an assignment of an integer weight, w ( e ) ∈ {1,2,..., k } to each edge e . The edge-weighting is proper if for every edge e = uv incident a proper vertex-coloring and the colors of two vertices u , v are distinct, where the color of a vertex v is defined as the sum of the weights on the edges incident to that vertex. Clearly a graph cannot have a k-edge-weighting and vertex-coloring if it has a component which is isomorphic to K2 i.e., an edge component. Throughout this paper, we denoted the color of a vertex v by Sv :=Σ uV(G) w ( uv ), such that if vw is not in V ( G ) w ( vw ) = 0.
In particular a 3-edge-weighting of G called 1-2-3-edge weighting and vertex coloring of G .
In 2002 [9] , Karonski , Luczak and Thomason conjectured that every graph without an edge component permits a 1-2-3-edge weighting and vertex coloring and proved their conjecture for the case of 3-colorable graphs [9] . For k = 2 is not sufficient as seen for instance in complete graphs and cycles of length not divisible by 4.
In 2004, they proved a graph without an edge component permits an 213-edge-weighting and vertex coloring. In continue a constant bound of k = 30 was proved by Addario-Berry , et.al in 2007 [1] . In next year, Addario-Berry’s group improved this bound to k = 16 [2] and also in 2008, T . Wang and Q . Yu improved k to 13 [10] . Recently, its new bounds are k = 5 and k = 6 by Kalkowski, et.al [7 , 8] . In addition, for further study and more historical details, readers can see the recent papers [3 - 5] .
In this paper, we show that there is a proper 1-2-3-edge weighting and vertex coloring for the complete graphs K 3q+1 q ∈ ℕ. and obtain an exact weighting w of all edges e E ( K 3q+1 ) and alternatively a proper color of all vertices v V ( K 3q+1 ). We present these main results in the following theorem:
Theorem 1.1. For the complete graph K 3q+1 for every integer number q with the vertex set V ( K 3q+1 ) = { v 1 , v 2 ,..., v 3q+1 }, there are a 3-edge weighting w : E ( K 3q+1 ) → {1, 2, 3} and a vertex-coloring s : V ( K 3q+1 ) → {9 q , 9 q −1,..., 7 q +1, 7 q , 7 q − 2, 7 q − 5, 7 q − 9,..., 3 q + 11, 3 q + 7, 3 q + 4}.
2. Main Results and Algorithm
For a graph complete graph Kn = ( V ( Kn ); E ( Kn )), a 3-edge weighting is a function w : E ( Kn ) → {1, 2, 3} such that
PPT Slide
Lager Image
is a color for any every vertex v V ( Kn ). The edge weighting w implies that E ( Kn ) = E ( Kn ) 1 E ( Kn ) 2 E ( Kn ) 3 . Throughout this paper, we denoted the size of edge sets E ( Kn ), E ( Kn ) 2 and E ( Kn ) 3 by γn , βn and αn , respectively. Obviously
PPT Slide
Lager Image
Before proving Theorem 1.1, for a general representation of complete graph K 3q+1 q ∈ ℕ, we present a proper 3-edge weighting for all edges incident to a vertex v in 3 q + 1 following steps and obtain all summations Sv .
2.1.Algorithm for 1-2-3-edge weighting and vertex coloring of K 3q+1 ( q ≥ 5): At first, we denote all vertices of K 3q+1 by v 1 , v 2 ,..., v 3q+1 , respectively. Obviously E ( K 3q+1 ) = { vivj | i j , i , j = 1, 2,..., 3 q + 1} and this implies that
PPT Slide
Lager Image
Suppose ∀ i = 1, 2,..., 3 q + 1; w ( vivi ) = 0. So, we have
Step(1)- For the vertex v 1 label all its edges with 3 (∀ vj V ( K 3q+1 ) w ( v 1 vj ) = 3 and
PPT Slide
Lager Image
Step(2)- For v 2 label all v 2 ’s edges with 3, except an edge v 2 v 3q+1 , then ∀ j = 1, 3, 4,..., 3 q , w ( v 2 vj ) = 3 and w ( v 2 v 3q+1 ) = 2. Thus S 2 = S 1 −1 = 9 q −1.
Step(3)- For v 3 label all edges v 3 vj ( j = 1, 2, 4,..., 3 q − 1) with 3 and v 3 v 3q , v 3 v 3q+1 with 2. Thus S 3 = S 2 − 1 = 9 q − 2.
Step(4)- For v 4 label all edges v 4 vj ( j = 1, 2, 3, 5,..., 3 q − 1) with 3, v 4 v 3q with 2 and v 4 v 3q+1 with 1. Thus S 4 = S 3 − 1 = 9 q − 3.
Step(s)- ∀ s = 5, 7,..., 2 q − 1 label all edges
PPT Slide
Lager Image
with 3, label
PPT Slide
Lager Image
with 2 and all edge
PPT Slide
Lager Image
with 1. Thus
PPT Slide
Lager Image
Step(r)- ∀ r = 6, 8,..., 2 q label all edges
PPT Slide
Lager Image
with 3, label
PPT Slide
Lager Image
with 2 and all edge
PPT Slide
Lager Image
with 1. Thus
PPT Slide
Lager Image
Step(2q+1)- For v 2q+1 , all edges v 2q +1 vj ( j = 1, 2,..., 2 q ) were labeled with 3. Thus label all edge v 2q+1 vj ( j = 2 q + 2,..., 3 q + 1) with 1. Thus S 2q+1 = 3 × 2 q + 2 × 0 + 1 × ( q ) = 7 q = S 2q − 1.
Step(2q+2)- For v 2q+2 , all edges v 2q+2 vj ( j = 1, 2,..., 2 q − 2) were labeled with 3, the edge v 2q+2 v 2q−1 , v 2q+2 v 2q were labeled with 2 and v 2q+2 v 2q+1 were labeled with 1. Thus label all edges v 2q+2 vj ( j = 2 q + 3,..., 3 q + 1) with 1 and S 2q+2 = 3 × (2 q − 2) + 2 × 2 + 1 × ( q ) = 7 q − 2 = S 2q+1 − 3.
Step(t)- ∀ t = 2 q + 3,..., 3 q − 2 all edges vtvj ( j = 1,..., 6 q + 2 − 2 t ) were labeled with 3, three edges vt v 6q+2−2t+i for i = 1, 2, 3 were labeled with 2 and all edges vtvj ( j = 6 q −2 t +6,..., t −1) were labeled with 1. Thus label all edges vtvj ( j = t +1,..., 3 q +1) with 1 and St = 3×(6 q +2−2 t )+2×3+1×(2 t −3 q −5) = 15 q + 7 − 4 t = S t−1 − 4.
Step(3q-1)- v 3q−1 , v 3q−1 vj ( j = 1, 2, 3, 4) were labeled with 3 and v 3q−1 v 5 , v 3q−1 v 6 , v 3q−1 v 7 were labeled with 2 and all edge v 3q−1 vj ( j = 8,..., 3 q − 2) were labeled with 1. Thus label v 3q−1 v 3q ; v 3q−1 v 3q+1 with 1 and S 3q−1 = 3×4+2 × 3 + 1 × (3 q − 7) = 3 q + 11 = S 3q−2 − 4.
Step(3q)- For v 3q , v 3q v 1 , v 3q v 2 were labeled with 3 and v 3q v 3 , v 3q v 4 , v 3q v 5 were labeled with 2 and all edge v 3q vj ( j = 6,..., 3 q − 1) were labeled with 1. Thus label the edge v 3q+1 v 3q with 1 and S 3q = 3×2+2×3+1×(3 q −5) = 3 q +7 = S 3q−1 − 4.
Step(3q+1)- Obviously, for the vertex v 3q+1 , the edge v 3q+1 v 1 were labeled with 3 and v 3q+1 v 2 , v 3q+1 v 3 were labeled with 2 and all edge v 3q+1 vj ( j = 4,..., 3 q ) were labeled with 1. Thus S 3q+1 = 3+2×2+1×(3 q −3) = 3 q +4 = S 3q − 3
Now, we start the proof of main theorem as follow.
Proof . Let K 3q+1 be a complete graph as order 3 q +1 for every integer number q , with the vertex set V ( K 3q+1 ) = { v 1 , v 2 ,..., v 3q+1 } and the edge set E ( K 3q+1 ) = { eij = vivj | vi , vj V ( K 3q+1 )} (| V ( K 3q+1 )| = 3 q +1 and
PPT Slide
Lager Image
It is easy to see that the above edge-weighting is a nice and proper 3-edge weighting w (or 1-2-3-edge weighting and vertex coloring) of K 3q+1 ( q ≥ 1). Because
PPT Slide
Lager Image
and for every edge eij = vivj incident to vi , we have an integer weight w ( vivj ) ∈ {1, 2, 3} such that this weighting naturally induces two distinct vertex coloring
PPT Slide
Lager Image
to vertices vi , vj .
An every edge eij = vivj ( i , j = 1, 2,..., 3 q + 1, i j ) weighted in Step ( i ) of above 3-edge weighting w . Also, from above 3-edge weighting w , one can see that all vertex color belong to the color set {9 q , 9 q −1,..., 7 q +1, 7 q , 7 q −2, 7 q − 5, 7 q − 9,..., 3 q + 11, 3 q + 7, 3 q + 4} (For example, see Figure 1 , 2 and 3 ). In Figure 1 , 2 and 3 , a proper 1-2-3-edge weighting and vertex coloring of complete graphs K 4 , K 7 , K 10 , K 13 and K 16 are shown.
PPT Slide
Lager Image
The 1-2-3-edge weighting and vertex coloring of complete graphs K4, K7 and K10.
PPT Slide
Lager Image
The 1-2-3-edge weighting and vertex coloring of K13.
PPT Slide
Lager Image
The 1-2-3-edge weighting and vertex coloring of complete graph K16.
Thus, the 3-edge weighting w : E ( K 3q+1 ) → {1, 2, 3} and the vertex coloring s : V ( K 3q+1 ) → {9 q , 9 q −1,..., 7 q +1, 7 q , 7 q −2, 7 q −5, 7 q −9,..., 3 q +11, 3 q + 7, 3 q + 4} is a proper 1-2-3-edge weighting and vertex coloring of K 3q+1 q ∈ ℕ and this complete the proof of theorem.
By using the proof of Theorem 1.1 (the 3-edge weighting w and the vertex coloring s ), one can see that the number of all edge weigh 3, 2 and 1 are equal to α 3q+1 = 3 q 2 + 1 = (| E ( K 3q+1 ) 3 |), β 3q+1 = 3 q − 2 = (| E ( K 3q+1 ) 2 |) and
PPT Slide
Lager Image
For example, E ( K 3q+1 ) 2 = { v 2 v 3q+1 , v 4 v 3q , v 5 v 3q−1 , v 5 v 3q , v 6 v 3q−1 , v 7 v 3q−2 , vs v 3q−1 , v 8 v 3q−2 ,..., v 2q−1 v 2q+2 , v 2q−1 v 2q+3 , v 2q v 2q+2 , v 2q+2 v 2q−3 , v 2q+2 v 2q−2 , v 2q+2 v 2q−1 , v 2q+3 v 2q−3 , v 2q+3 v 2q−2 , v 2q+3 v 2q−1 , v 2q+4 v 2q−5 , v 2q+4 v 2q−4 , v 2q+4 v 2q−3 ,..., v 3q−2 v 6 , v 3q−2 v 7 , v 3q−2 v 8 , v 3q−1 v 5 , v 3q−1 v 6 , v 3q−1 v 7 , v 3q v 3 v 3q v 4 , v 3q v 5 , v 3q+1 v 2 , v 3q+1 v 3 }.
3. Conclusions and Conjectures
We conclude our paper with the following open questions and conjectures:
Corollary 3.1 (The 1-2-3-conjecture [6 , 9] ). Every connected graph G = ( V , E ) non-isomorph to K 2 ( with at least two edges ) has an edge labeling f : E → {1, 2, 3} and vertex coloring S : V → { n − 1,...,3 n − 3}.
Corollary 3.2 ( n vertex coloring). There are distinct numbers of Sv's , v V ( G ), of a graph G of order n , for a 1-2-3-edge labeling and vertex coloring .
Corollary 3.3 (Proper vertex coloring). For all graph G of order n , there are the χ( G ) numbers of Sv's , v V ( G ), with this 1-2-3-edge labeling and vertex Coloring . Where χ( G ) is the number colors of the vertices on the graph G .
In this parer, we show that the complete graph K 3q+1 ( q ≥ 1), recognize in three Conjecture 3.1, 3.2 and 3.3.
Acknowledgements
The authors are thankful to Dr. Mehdi Alaeiyan, Mr Ali Ramin and Mr Seied Hamid Hosseini of Department of Mathematics, Iran University of Science and Technology (IUST) for their precious support and suggestions.
BIO
Mohammad Reza Farahani
Department of Applied Mathematics, Iran University of Science and Technology (IUST), Narmak, Tehran 16844, Iran.
e-mail: MR_Farahani@Mathdep.iust.ac.ir
References
Addario-Berry L. , Dalal K. , McDiarmid C. , Reed B.A. , Thomason A. (1982), (2007) Vertex-coloring edge-wheitings Combinatorical. J. 27 1 - 12    DOI : 10.1007/s00493-007-0041-6
Addario-Berry L. , Dalal K. , Reed B.A. (2008) Degree constrained sub- graphs Discrete Applied Mathematics J. 156 1168 - 1174    DOI : 10.1016/j.dam.2007.05.059
Alaeiyan M. , Farahani M.R. , Mohammadian S. (2013) The 1-2-3-edge labeling and vertex colors. Submitted for publish
Farahani M.R. (2013) On The 1-2-3-Edge Weighting and Vertex Coloring of Complete Graph. Int. J. Computational Sciences & Applications. Inpress
Farahani M.R. , Hosseini S.H. (2013) The 1-2-3-edge labeling and vertex coloring of complete graph Kn. Submitted for publish
Grytczuka J. , Dalal K. , Reed B.A. (2008) Thue type problems for graphs Discrete Mathe-matics J. 308 4419 - 4429    DOI : 10.1016/j.disc.2007.08.039
Kalkowski M. , Karonski M. , Pfender F. (2009) Vertax-Coloring Edge-Weithings With In-teger Weights At Most 6 Rostock. Math. Kolloq. 64 39 - 43
Kalkowski M. , Karonski M. , Pfender F. (2010) Vertex-coloring edge-weightings: To wards the 1-2-3-conjecture Combinatorial Theory (Series B) J. 100 347 - 349    DOI : 10.1016/j.jctb.2009.06.002
Karonskiy M. , Luczak T. , Thomason A. (2004) Edge weights and vertex colors Combina-torial Theory (Series B) J. 91 151 - 157    DOI : 10.1016/j.jctb.2003.12.001
Wang T. , Yu Q. (2008) On vertex-coloring 13-edge-weighting Front. Math. China. 3 (4) 1 - 7    DOI : 10.1007/s11461-008-0009-8