On a Number of Colors in Cyclically Interval Edge Colorings of Simple Cycles ()
1. Introduction
We consider undirected, simple, finite and connected graphs. For a graph
, we denote by 
and 
the sets of its vertices and edges, respectively. The set of edges of 
incident with a vertex 
is denoted by
. For any
, 
denotes the degree of the vertex 
in
. For a graph
, 
denotes the maximum degree of a vertex of
. A simple cycle with 
edges 
is denoted by
. A simple path with 
edges 
is denoted by
. The terms and concepts that we do not define can be found in [1].
For an arbitrary finite set
, we denote by 
the number of elements of
. The set of positive integers is denoted by
. For any subset 
of the set
, we denote by 
and 
the subsets of all even and all odd elements of
, respectively.
An arbitrary nonempty subset of consecutive integers is called an interval. An interval with the minimum element 
and the maximum element 
is denoted by
. An interval 
is called a 
-interval if
.
For any real number
, we denote by 
the maximum (minimum) integer which is less (greater) than or equal to
.
For any positive integer 
define
.
For any nonnegative integer 
define
A function 
is called a proper edge 
-coloring of a graph G, if all colors are used, and no two adjacent edges receive the same color.
The minimum value of 
for which there exists a proper edge 
-coloring of a graph 
is denoted by 
[2].
If 
is a graph, and 
is its proper edge 
-coloring, where
, then we define
.
If
, 
, and 
is a proper edge 
-coloring of a graph
, then we set
.
A proper edge 
-coloring 
of a graph 
is called an interval 
-coloring of 
[35] if for any
, the set 
is a
-interval. For any
, we denote by 
the set of graphs for which there exists an interval 
-coloring. Let
.
For any
, we denote by 
and 
the minimum and the maximum possible value of
, respectively, for which
. For a graph
, let us set
.
A proper edge 
-coloring 
of a graph 
is called a cyclically interval 
-coloring of
, if for any
, at least one of the following two conditions holds:
1) 
is a 
-interval2) 
is a 
-interval.
For any
, we denote by 
the set of graphs for which there exists a cyclically interval 
-coloring. Let
.
For any
, we denote by 
and 
the minimum and the maximum possible value of
, respectively, for which
. For a graph
, let us set
.
It is clear that for any
, an arbitrary interval 
- coloring 
of a graph 
is also a cyclically interval 
-coloring of
. Thus, for any
, 
and
. Let us also note that for an arbitrary graph
,
. It is also clear that for any
, the following inequality is true:
and
In [5,6], for any tree
, it is proved that
, 
is an interval, and the exact values of the parameters
, 
are found. In [7,8], for any tree
, it is proved that
. Some interesting results on cyclically interval 
-colorings and related topics were obtained in [9-14].
In this paper, for any integer
, it is proved that
, and the set 
is found.
2. Main Results
Remark 1. Clearly, for any integer
,
,
.
Therefore, if
, then a proper edge 
coloring of 
does not exist, and
.
Remark 2. It is not difficult to see that for any integer
, 
and
.
Proposition 1. For any integer
, 
,
Proof is trivial.
Theorem 1. For any integers 
and
, satisfying the conditions 
and
, 
if and only if
.
Proof. First let us prove, that if
, 
and
then
.
Assume the contrary: there are
, 
and
for which a cyclically interval 
-coloring 
of the graph 
exists.
Let us construct a graph 
removing from the graph 
the subset 
of its edges. Let us construct a graph 
removing from the graph 
all its isolated vertices.
Case A. 
is a connected graph.
Let us denote by 
the simple path with pendant edges 
and 
which is isomorphic to the graph
.
Case A.1. 
is odd.
Clearly,
. It means that 
is an even number, satisfying the inequality
.
Case A.1.1. 
is odd.
Clearly,
. Since 
is a cyclically interval 
-coloring of
, we conclude from the definition of
, that for a graph
, there exists an interval 
-coloring 
with
. Consequently, the number 
is odd, what contradicts the same parity of 
and
.
Case A.1.2. 
is even.
Clearly,
. Since 
is a cyclically interval 
-coloring of
, we conclude from the definition of
, that for a graph
, there exists an interval 
-coloring 
with 
and
. Consequently, the number 
is even, what contradicts the different parity of 
and
.
Case A.2. 
is even.
Clearly,
. It means that
is an odd number, satisfying the inequality
.
Case A.2.1. 
is odd.
Clearly,
. Since 
is a cyclically interval 
-coloring of
, we can conclude from the definition of
, that for a graph
, there exists an interval 
-coloring 
with
. Consequently,
which is impossible.
Case A.2.2. 
is even.
Clearly,
. Since 
is a cyclically interval 
-coloring of
, we can conclude from the definition of
, that for a graph
, there exists an interval 
-coloring 
with 
and
.
Since 
is odd, the number 
is also odd, but it is impossible because of the same parity of 
and
.
Case B. 
is a graph with 
connected components,
.
Assume that:
1) 
are connected components of 
numbered in succession at bypassing of the graph 
in some fixed direction2) 
are vertices of 
numbered in succession at bypassing mentioned in 1)3) 
are edges of 
numbered in succession at bypassing mentioned in 1)4)
, 
, 
,
.
Define functions
,
,
as follows. For any
, set:
.
For any
, set
Now let us define subgraphs 
of the graph
.
For any
, let 
be the subgraph of 
induced by the subset
of its vertices. Let 
be the subgraph of 
induced by the subset
of its vertices.
Let
.
For any
, we define a point 
of the 2- dimensional rectangle coordinate system by the following way:
.
Let us define a graph
. Set
Clearly,
.
Let
,
.
An edge 
of the graph 
is called horizontal if the points 
and 
have the same ordinate.
Let us denote by 
the set of all horizontal edges of the graph
. Set
. It is easy to note that the numbers 
and 
are both even.
Now let us define a function 
by the following way. For an arbitrary 
set:
Clearly,
.
Case B.1. 
is odd.
Clearly,
. It means that 
is an even number, satisfying the inequality
. It is not difficult to see that in this case, for an arbitrary
, 
is odd, and, moreover, for an arbitrary
, 
is even. Since 
is even, we conclude that the odd number
is represented as a sum of two even numbers, which is impossible.
Case B.2. 
is even.
Clearly,
.
It means that 
is an odd number, satisfying the inequality
.
It is not difficult to see that in this case, for an arbitrary
, 
is odd, and, moreover, for an arbitrary
, 
is even.
Case B.2.1.
.
In this case, evidently, there are different integers 
and 
in the set
, for which there exist interval 
-colorings 
and 
of the graphs 
and
, respectively. Consequently,
which is impossible.
Case B.2.2.
.
Without loss of generality assume that
.
Since 
is even, we conclude that the even number
is represented as a sum of one odd and two even numbers, which is impossible.
Case B.2.3.
.
Clearly, for any
, the set 
contains exactly one of the colors 1 and
.
Case B.2.3.a).
,
.
It is not difficult to see that in this case there is
, for which the set 
contains the color
. It means that there exists an interval 
-coloring of the graph 
which colors pendant edges of 
by the color 1. Consequently,
which is impossible.
Case B.2.3.b).
,
.
It is not difficult to see that in this case there is
, for which the set 
contains the color 2. It means that there exists an interval 
- coloring of the graph 
which colors pendant edges of 
by the color 1. Consequently,
which is impossible.
Case B.2.3.c).
,
.
Let us choose 
and 
satisfying the conditions
,
.
Let 
be the maximum color of the set
.
Let 
be the minimum color of the set
.
Clearly,
.
It is not difficult to see that there exists an interval 
-coloring of the graph 
which colors pendant edges of 
by the color 1. Hence,
.
It is not difficult to see that there exists an interval 
-coloring of the graph 
which colors pendant edges of 
by the color 1. Hence,
.
Consequently, we obtain that
which is impossible.
Thus, we have proved that if
, 
and
then
.
Now let us prove that if
, 
, 
, 
then
.
Assume the contrary. It means that there are
,
, and
, which satisfy the conditions 
and
Case 1. 
is odd.
In this case 
and
, andtherefore,
. It means that there exists
, for which
.
Let us note that the equality 
implies
, which is incompatible with the condition
. Hence,
.
Now, to see a contradiction, it is enough to note that the existence of an interval 
-coloring of a graph 
with the existence of an interval 2-coloring of a graph 
provides the existence of a cyclically interval 
-coloring of the graph
.
Case 2. 
is even.
In this case 
and
and, therefore,
.
It follows from Remark 2 that
.
Clearly, there exists
,
for which
.
Let us note that the equality
implies
, which is incompatible with the condition
. Hence,
is an even number, satisfying the inequality
.
Now, to see a contradiction, it is enough to note that the existence of an interval 
-coloring of a graph
with the existence of an interval 2-coloring of a graph
provides the existence of a cyclically interval 
-coloring of the graph
.
Thus, we have proved, that if
, 
,
, 
then
.
Theorem 1 is proved.
It means that we also have Theorem 2. For an arbitrary integer
,
3. Acknowledgements
The author thanks P.A. Petrosyan and N.A. Khachatryan for their attention to this work.