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
S_{v}
:=Σ
_{e∋v}
w
(
e
). A kedgeweighting of a graph
G
is an assignment of an integer weight,
w
(
e
) ∈ {1,2,...,
k
} to each edge
e
, such that two vertexcolor
S_{v}
,
S_{u}
be distinct for every edge
uv
. In this paper we determine an exact 3edgeweighting of complete graphs
k
_{3q+1}
∀
_{q}
∈ ℕ. Several open questions are also included.
AMS Mathematics Subject Classification : 05C15, 05C78.
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
kedgeweighting
of a graph
G
is an assignment of an integer weight,
w
(
e
) ∈ {1,2,...,
k
} to each edge
e
. The edgeweighting is proper if for every edge
e
=
uv
incident a proper vertexcoloring 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 kedgeweighting and vertexcoloring if it has a component which is isomorphic to
K_{2}
i.e., an edge component. Throughout this paper, we denoted the color of a vertex
v
by
S_{v}
:=Σ
_{u∈V(G)}
w
(
uv
), such that if
vw
is not in
V
(
G
)
w
(
vw
) = 0.
In particular a 3edgeweighting of
G
called
123edge weighting and vertex coloring
of
G
.
In 2002
[9]
,
Karonski
,
Luczak
and
Thomason
conjectured that every graph without an edge component permits a 123edge weighting and vertex coloring and proved their conjecture for the case of 3colorable 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 213edgeweighting and vertex coloring. In continue a constant bound of
k
= 30 was proved by
AddarioBerry
,
et.al
in 2007
[1]
. In next year, AddarioBerry’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 123edge 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 3edge weighting w
:
E
(
K
_{3q+1}
) → {1, 2, 3}
and a vertexcoloring 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
K_{n}
= (
V
(
K_{n}
);
E
(
K_{n}
)), a 3edge weighting is a function
w
:
E
(
K_{n}
) → {1, 2, 3} such that
is a color for any every vertex
v
∈
V
(
K_{n}
). The edge weighting
w
implies that
E
(
K_{n}
) =
E
(
K_{n}
)
_{1}
∪
E
(
K_{n}
)
_{2}
∪
E
(
K_{n}
)
_{3}
. Throughout this paper, we denoted the size of edge sets
E
(
K_{n}
),
E
(
K_{n}
)
_{2}
and
E
(
K_{n}
)
_{3}
by
γ_{n}
,
β_{n}
and
α_{n}
, respectively. Obviously
Before proving Theorem 1.1, for a general representation of complete graph
K
_{3q+1}
∀
_{q}
∈ ℕ, we present a proper 3edge weighting for all edges incident to a vertex
v
in 3
q
+ 1 following steps and obtain all summations
S_{v}
.
2.1.Algorithm for 123edge 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}
) = {
v_{i}v_{j}

i
≠
j
,
i
,
j
= 1, 2,..., 3
q
+ 1} and this implies that
Suppose ∀
i
= 1, 2,..., 3
q
+ 1;
w
(
v_{i}v_{i}
) = 0. So, we have
Step(1) For the vertex
v
_{1}
label all its edges with 3 (∀
v_{j}
∈
V
(
K
_{3q+1}
)
w
(
v
_{1}
v_{j}
) = 3 and
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}
v_{j}
) = 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}
v_{j}
(
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}
v_{j}
(
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
with 3, label
with 2 and all edge
with 1. Thus
Step(r) ∀
r
= 6, 8,..., 2
q
label all edges
with 3, label
with 2 and all edge
with 1. Thus
Step(2q+1) For
v
_{2q+1}
, all edges
v
_{2q}
+1
v_{j}
(
j
= 1, 2,..., 2
q
) were labeled with 3. Thus label all edge
v
_{2q+1}
v_{j}
(
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}
v_{j}
(
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}
v_{j}
(
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
v_{t}v_{j}
(
j
= 1,..., 6
q
+ 2 − 2
t
) were labeled with 3, three edges
v_{t}
v
_{6q+2−2t+i}
for
i
= 1, 2, 3 were labeled with 2 and all edges
v_{t}v_{j}
(
j
= 6
q
−2
t
+6,...,
t
−1) were labeled with 1. Thus label all edges
v_{t}v_{j}
(
j
=
t
+1,..., 3
q
+1) with 1 and
S_{t}
= 3×(6
q
+2−2
t
)+2×3+1×(2
t
−3
q
−5) = 15
q
+ 7 − 4
t
=
S
_{t−1}
− 4.
Step(3q1)
v
_{3q−1}
,
v
_{3q−1}
v_{j}
(
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}
v_{j}
(
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}
v_{j}
(
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}
v_{j}
(
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}
) = {
e_{ij}
=
v_{i}v_{j}

v_{i}
,
v_{j}
∈
V
(
K
_{3q+1}
)} (
V
(
K
_{3q+1}
) = 3
q
+1 and
It is easy to see that the above edgeweighting is a nice and proper 3edge weighting
w
(or 123edge weighting and vertex coloring) of
K
_{3q+1}
(
q
≥ 1). Because
and for every edge
e_{ij}
=
v_{i}v_{j}
incident to
v_{i}
, we have an integer weight
w
(
v_{i}v_{j}
) ∈ {1, 2, 3} such that this weighting naturally induces two distinct vertex coloring
to vertices
v_{i}
,
v_{j}
.
An every edge
e_{ij}
=
v_{i}v_{j}
(
i
,
j
= 1, 2,..., 3
q
+ 1,
i
≥
j
) weighted in
Step
(
i
) of above 3edge weighting
w
. Also, from above 3edge 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 123edge weighting and vertex coloring of complete graphs
K
_{4}
,
K
_{7}
,
K
_{10}
,
K
_{13}
and
K
_{16}
are shown.
The 123edge weighting and vertex coloring of complete graphs K_{4}, K_{7} and K_{10}.
The 123edge weighting and vertex coloring of K_{13}.
The 123edge weighting and vertex coloring of complete graph K_{16}.
Thus, the 3edge 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 123edge 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 3edge 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
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}
,
v_{s}
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 123conjecture
[6
,
9]
).
Every connected graph G
= (
V
,
E
)
nonisomorph 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 S_{v}'s
,
v
∈
V
(
G
),
of a graph G of order n
,
for a 123edge labeling and vertex coloring
.
Corollary 3.3
(Proper vertex coloring).
For all graph G of order n
,
there are the
χ(
G
)
numbers of S_{v}'s
,
v
∈
V
(
G
),
with this 123edge 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.
email: MR_Farahani@Mathdep.iust.ac.ir
AddarioBerry L.
,
Dalal K.
,
McDiarmid C.
,
Reed B.A.
,
Thomason A.
(1982), (2007)
Vertexcoloring edgewheitings
Combinatorical. J.
27
1 
12
DOI : 10.1007/s0049300700416
AddarioBerry 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 123edge labeling and vertex colors. Submitted for publish
Farahani M.R.
(2013)
On The 123Edge Weighting and Vertex Coloring of Complete Graph.
Int. J. Computational Sciences & Applications.
Inpress
Farahani M.R.
,
Hosseini S.H.
(2013)
The 123edge labeling and vertex coloring of complete graph Kn. Submitted for publish
Kalkowski M.
,
Karonski M.
,
Pfender F.
(2009)
VertaxColoring EdgeWeithings With Integer Weights At Most 6
Rostock. Math. Kolloq.
64
39 
43
Kalkowski M.
,
Karonski M.
,
Pfender F.
(2010)
Vertexcoloring edgeweightings: To wards the 123conjecture
Combinatorial Theory (Series B) J.
100
347 
349
DOI : 10.1016/j.jctb.2009.06.002