# Total Graph Interpretation of the Numbers of the Fibonacci Type

Authors: Urszula Bednarz; Iwona Włoch; Małgorzata Wołowiec-Musiał
Journal: Journal of Applied Mathematics
 (2015)

---

## Abstract

We give a total graph interpretation of the numbers of the Fibonacci type. This graph interpretation relates to an edge colouring by monochromatic paths in graphs. We will show that it works for almost all numbers of the Fibonacci type. Moreover, we give the lower bound and the upper bound for the number of all(
A
1
,
2
A
1
)-edge colourings in trees.


---

## Body

## 1. Introduction and Preliminary Results

For general concepts about combinatory graph theory and online encyclopedia of integer sequences, see, for example, [1], [2], and [3], respectively. By numbers of the Fibonacci type we mean numbers defined recursively by the kth-order linear recurrence relation of the form(1)
a
n
=
b
1
a
n
-
1
+
b
2
a
n
-
2
+
⋯
+
b
k
a
n
-
kfor n
≥
k, where k
≥
2 and b
i
≥
0, i
=
1
,
…
,
k, are integers and a
0
,
…
,
a
k
-
1 are given integers. For special values of k and b
i, i
=
1
,
…
,
k, the equality (1) gives the well-known recurrences which define the numbers of the Fibonacci type. They are listed below.(a)
Fibonacci numbersF
n:(2)
F
n
=
F
n
-
1
+
F
n
-
2
,
n
≥
2
w
i
t
h
F
0
=
F
1
=
1
.
(b)
Lucas numbersL
n:(3)
L
n
=
L
n
-
1
+
L
n
-
2
,
n
≥
2
w
i
t
h
L
0
=
2
,
L
1
=
1
.
(c)
Pell numbersP
n:(4)
P
n
=
2
P
n
-
1
+
P
n
-
2
,
n
≥
2
w
i
t
h
P
0
=
0
,
P
1
=
1
.
(d)
Pell-Lucas numbersQ
n:(5)
Q
n
=
2
P
n
-
1
+
P
n
-
2
,
n
≥
2
w
i
t
h
P
0
=
P
1
=
1
.
(e)
Jacobsthal numbersJ
n:(6)
J
n
=
J
n
-
1
+
2
J
n
-
2
,
n
≥
2
w
i
t
h
J
0
=
0
,
J
1
=
1
.
(f)
Jacobsthal-Lucas numbersj
n:(7)
j
n
=
j
n
-
1
+
2
j
n
-
2
,
n
≥
2
w
i
t
h
j
0
=
2
,
j
1
=
1
.
(g)
Padovan numbersP
v
(
n
):(8)
P
v
n
=
P
v
n
-
2
+
P
v
n
-
3
,
n
≥
3
w
i
t
h
P
v
0
=
P
v
1
=
P
v
2
=
1
.
(h)
Perrin numbersP
r
(
n
):(9)
P
r
n
=
P
r
n
-
2
+
P
r
n
-
3
,
n
≥
3
w
i
t
h
P
r
0
=
3
,
P
r
1
=
0
,
P
r
2
=
2
.
(i)
Tribonacci numbers of the first kindT
n:(10)
T
n
=
T
n
-
1
+
T
n
-
2
+
T
n
-
3
,
n
≥
3
w
i
t
h
T
0
=
T
1
=
T
2
=
1
.
(j)
Tribonacci numbers of the second kindT
n
∗:(11)
T
n
∗
=
T
n
-
1
∗
+
T
n
-
2
∗
+
T
n
-
3
∗
,
n
≥
3
w
i
t
h
T
0
∗
=
0
,
T
1
∗
=
T
2
∗
=
1
.These numbers are intensively studied in the literature; they have many interesting interpretations also in graphs. The graph interpretation of the Fibonacci numbers was initiated by Prodinger and Tichy in [4]. In that paper, among others, they showed connections between the Fibonacci and the Lucas numbers and the number of all independent sets in special graphs. Let N
I
(
G
) be the number of all independent sets in a graph G. By P
(
m
), C
(
m
), T
(
m
), and S
(
m
) we denote a path, a cycle, a tree, and a star of size m for m
≥
1, respectively. Then, N
I
(
P
(
m
)
)
=
F
m
+
2 and N
I
(
C
(
m
)
)
=
L
m; for details, see [4]. This simple observation gave an impetus for studying the graph parameter N
I
(
G
) in different classes of graphs and their products, from the pure mathematical point of view. This interest was multiplied by the fact that the parameter N
I
(
G
) of a molecular graph was introduced to the combinatorial chemistry by showing some relations between N
I
(
G
) and some physicochemical properties of chemical compounds. For these reasons, the parameter N
I
(
G
) is intensively studied in graphs.Theorem 1 (see [4]).
Letm
≥
1 be an integer. For a tree T
(
m
) of size m, F
m
+
2
≤
N
I
(
T
(
m
)
)
≤
2
m
+
1 holds. Moreover, N
I
(
T
(
m
)
)
=
F
m
+
2 iff T
(
m
)
=
P
(
m
) and N
I
(
T
(
m
)
)
=
2
m
+
1 iff T
(
m
)
=
S
(
m
)
.The graph parameterN
I
(
G
) relates to other numbers of the Fibonacci type. For Jacobsthal numbers J
n and Jacobsthal-Lucas numbers j
n, the following has been proved.Theorem 2 (see [5, 6]).
Letm
≥
1 be an integer. Then, N
I
(
P
(
m
)
[
K
2
]
)
=
J
m
+
3 and N
I
(
C
(
m
)
[
K
2
]
)
=
j
m.For other results related to the parameterN
I
(
G
) and their applications, see the last survey [7]. In this survey the authors collect and classify the results concerning the graph parameter N
I
(
G
), most of which are obtained quite recently. Actually for the chemical applications, the index N
I
(
G
) is named as the Merrifield-Simmons index.Considering the Fibonacci numbers and numbers of the Fibonacci type, we can collect other graph parameters related to the numbers of the Fibonacci type.LetZ
(
G
) be the number of all matchings of G. Then, Z
(
P
(
m
)
∘
K
1
)
=
P
m
+
2 and Z
(
C
(
m
)
∘
K
1
)
=
2
Q
m, where G
∘
H is the corona of two graphs. The index Z
(
G
) is well-known by the Hosoya index. Let N
I
L
(
G
) be the number of all independent sets in G including the set of leaves as a subset. Then, N
I
L
(
P
(
m
)
)
=
P
v
(
m
-
2
). For this graph parameter, see more details in [8].Theorem 3 (see [8]).
Letm
≥
2 be an integer. Then, for a tree T
(
m
) of size m, N
I
L
(
T
(
m
)
)
≤
P
v
(
m
-
2
) holds. Moreover, P
(
m
) is the extremal graph achieving the maximum value of N
I
L
(
T
(
m
)
).For the classical Fibonacci numbers and numbers of the Fibonacci type, there are many generalizations with respect to one or more parameters. We list some of these generalized numbers of the Fibonacci type. Letkandn be integers. We have the following.(1)
k-generalized Fibonacci numbers f
n (Miles Jr. [9]):(12)
f
n
=
f
n
-
1
+
f
n
-
2
+
⋯
+
f
n
-
k
,
k
≥
2
,
n
>
k
,
withf
j
=
0 for 0
≤
j
≤
k
-
2 and f
k
-
1
=
f
k
=
1.
(2)
Generalized Fibonacci numbersF
(
k
,
n
) (Kwaśnik and Włoch [10]):(13)
F
k
,
n
=
F
k
,
n
-
1
+
F
k
,
n
-
k
,
k
≥
2
,
n
≥
k
,
withF
(
k
,
n
)
=
n
+
1 for n
=
0,1
,
…
,
k
-
1.
(3)
k-Fibonacci numbers F
k
(
n
) (Falcón and Plaza [11]):(14)
F
k
n
=
k
F
k
n
-
1
+
F
k
n
-
2
,
k
≥
1
,
n
≥
2
,
withF
k
(
0
)
=
0 and F
k
(
1
)
=
1.
(4)
Generalized Pell numbersP
(
k
,
n
) (Włoch [12]):(15)
P
k
,
n
=
P
k
,
n
-
1
+
P
k
,
n
-
k
+
1
+
P
k
,
n
-
k
,
k
≥
2
,
n
≥
k
+
1
,
withP
2,0
=
0 and P
(
k
,
0
)
=
1 for k
≥
3 and P
(
k
,
1
)
=
1, P
(
k
,
n
)
=
2
n
-
2 for 2
≤
n
≤
k.
(5)
k-Lucas numbers L
k
(
n
) (Falcon [13]):(16)
L
k
n
=
k
L
k
n
-
1
+
L
k
n
-
2
,
k
≥
1
,
n
≥
2
,
withL
k
0
=
2 and L
k
(
1
)
=
k.
(6)
k-Pell numbers P
k
(
n
) (Catarino [14]):(17)
P
k
n
=
2
P
k
n
-
1
+
k
P
k
n
-
2
,
k
≥
1
,
n
≥
2
,
withP
k
(
0
)
=
0 and P
k
(
1
)
=
1.
(7)
k-Pell-Lucas numbers Q
k
(
n
) (Catarino and Vasco [15]):(18)
Q
k
n
=
2
Q
k
n
-
1
+
k
Q
k
n
-
2
,
k
≥
1
,
n
≥
2
,
withQ
k
(
0
)
=
Q
k
(
1
)
=
2.
(8)
Generalized Lucas numbersL
(
k
,
n
) (Włoch [16]):(19)
L
k
,
n
=
L
k
,
n
-
1
+
L
k
,
n
-
k
,
k
≥
2
,
n
≥
2
k
,
withL
(
k
,
n
)
=
n
+
1 for n
=
0,1
,
…
,
2
k
-
1.
(9)
Distance Pell numbersP
d
(
k
,
n
) (Szynal-Liana and Włoch [5]):(20)
P
d
k
,
n
=
P
d
k
,
n
-
1
+
P
d
k
,
n
-
2
+
P
d
k
,
n
-
k
,
k
≥
1
,
n
≥
k
,
withP
d
(
k
,
0
)
=
0 and P
d
(
k
,
i
)
=
1 for k
≤
i
+
2, i
≥
1, and P
d
(
k
,
i
)
=
0 for k
>
i
+
2, i
≥
1.
(10)
Distance companion Pell numbersQ
d
(
k
,
n
) (Szynal-Liana et al. [6]):(21)
Q
d
k
,
n
=
Q
d
k
,
n
-
1
+
Q
d
k
,
n
-
2
+
Q
d
k
,
n
-
k
,
k
≥
1
,
n
≥
k
,
withQ
d
k
,
0
=
k, Q
d
1,1
=
1, and Q
d
k
,
n
=
L
n for n
=
1
,
…
,
k
-
1.
(11)
Distance Jacobsthal numbersJ
(
k
,
t
,
n
) (Szynal-Liana et al. [6]):(22)
J
k
,
t
,
n
=
J
k
,
t
,
n
-
1
+
t
J
k
,
t
,
n
-
k
,
k
≥
2
,
n
≥
k
+
1
,
withJ
(
k
,
t
,
0
)
=
0 and J
(
k
,
t
,
n
)
=
1 for n
=
1
,
…
,
k.
(12)
Distance Jacobsthal-Lucas numbersJ
L
(
k
,
t
,
n
) (Szynal-Liana et al. [6]):(23)
J
L
k
,
t
,
n
=
J
L
k
,
t
,
n
-
1
+
t
J
L
k
,
t
,
n
-
k
,
k
≥
2
,
n
≥
k
,
withJ
L
(
k
,
t
,
0
)
=
k and J
L
(
k
,
t
,
n
)
=
1 for n
=
1
,
…
,
k
-
1.
(13)
(
2
,
k
)-distance Fibonacci numbers F
2
(
2
)
(
k
,
n
) of the second kind (Bednarz et al. [17]):(24)
F
2
2
k
,
n
=
F
2
2
k
,
n
-
2
+
F
2
2
k
,
n
-
k
,
k
≥
1
,
n
≥
k
+
1
,
withF
2
(
2
)
(
k
,
n
)
=
0 if n is odd and n
≤
k
-
1, F
2
(
2
)
(
k
,
n
)
=
1 if n is even and n
≤
k
-
1, F
2
(
2
)
(
k
,
k
)
=
0 if k
=
1, F
2
(
2
)
(
k
,
k
)
=
1 if k is odd and k
≥
3, and F
2
(
2
)
(
k
,
k
)
=
2 if k is even.
(14)
(
2
,
k
)-distance Lucas numbers L
2
(
2
)
(
k
,
n
) of the second kind (Bednarz et al. [17]):(25)
L
2
2
k
,
n
=
L
2
2
k
,
n
-
2
+
L
2
2
k
,
n
-
k
,
k
≥
1
,
n
≥
k
+
2
,
withL
2
(
2
)
(
1,0
)
=
2 and L
2
(
2
)
(
k
,
0
)
=
k for k
≥
2, L
2
(
2
)
(
k
,
1
)
=
0, L
2
(
2
)
(
1,2
)
=
3, and L
2
(
2
)
(
k
,
k
)
=
k if k is odd and L
2
(
2
)
(
k
,
k
)
=
k
+
2 if k is even, L
2
(
2
)
(
k
,
k
+
1
)
=
2 if k is odd and k
≠
1, L
2
(
2
)
(
k
,
k
+
1
)
=
0 if k is even, L
2
(
2
)
(
k
,
n
)
=
0 if n is odd and 3
≤
n
≤
k
-
1, and L
2
(
2
)
(
k
,
n
)
=
2 if n is even and 2
≤
n
≤
k
-
1.For most of these numbers also some graph interpretations with respect to distance independent sets or matchings were studied (see, e.g., [5, 6, 8, 10, 12, 18–20]).


## 2. Main Results

The main purpose of this section is to give a total graph interpretation for numbers of the Fibonacci type with respect to a special edge colouring of some graphs.LetG be an undirected, connected, simple graph. Let I
=
{
1
,
…
,
k
}, k
≥
2, and let I
i
=
{
1
,
…
,
b
i
}, b
i
≥
1. In particular, I
i can be empty (then we put b
i
=
0). Let C
=
⋃
i
∈
I
C
i be a nonempty family of colours, where C
i
=
{
i
A
j
;
j
∈
I
i
} for i
=
1
,
…
,
k. The set C
i will be called the set of b
i shades of the colour i. Consequently, for all i
≠
p, 1
≤
i, p
≤
k, i
A
j
≠
p
A
j holds and this implies that the family C has exactly ∑
i
=
1
k
|
C
i
|
=
∑
i
=
1
k
b
i colours.A graphG is (
i
A
j; i
∈
I, j
∈
I
i
)-edge coloured by monochromatic paths if for every maximal i
A
j-monochromatic subgraph H of G, where i
A
j
∈
C
i, 1
≤
i
≤
k, 1
≤
j
≤
b
i, there is a partition of H into edge disjoint paths of the length i. Clearly, if b
1
≠
0 then (i
A
j; i
∈
I, j
∈
I
i)-edge colouring by monochromatic paths always exists. With this type of edge colouring of a graph, we associate the following graph parameter.LetG be a graph which can be (i
A
j; i
∈
I, j
∈
I
i)-edge coloured by monochromatic paths. Let F be a family of distinct (i
A
j; i
∈
I, j
∈
I
i)-edge coloured graphs obtained by colouring of a graph G and (26)
F
=
G
1
,
G
2
,
…
,
G
l
,
l
≥
1
,where G
(
p
), 1
≤
p
≤
l, denotes a graph obtained by (i
A
j; i
∈
I, j
∈
I
i)-edge colouring by monochromatic paths of a graph G.For (i
A
j; i
∈
I, j
∈
I
i)-edge coloured graph G
(
p
) by θ
(
G
(
p
)
), we denote the number of all partitions of G
(
p
) for 1
≤
p
≤
l. Let (27)
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
G
=
∑
p
=
1
l
θ
G
p
.Considering thekth-order linear recurrence relation (1), we will show that there is a connection between this recurrence equation and the parameter σ
(
i
A
j
;
i
∈
I
,
j
∈
I
i
)
(
G
) for a special graph G.Theorem 4.
Letk
≥
2 and m
≥
k be integers. Then, (28)
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
P
m
=
b
1
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
P
m
-
1
+
⋯
+
b
k
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
P
m
-
k
.Proof.
Assume thatm
≥
k and let us consider (i
A
j; i
∈
I, j
∈
I
i)-edge colouring by monochromatic paths of the graph P
(
m
) with the numbering of its edges in the natural fashion.
Let us denote byσ
(
i
A
j
;
i
∈
I
,
j
∈
I
i
)
r
(
P
(
m
)
) the number of all (i
A
j; i
∈
I, j
∈
I
i)-edge colourings by monochromatic paths of the graph P
(
m
), such that the last edge of P
(
m
) is coloured by the colour from the fixed set C
r, where 1
≤
r
≤
k. It is clear that (29)
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
P
m
=
∑
r
=
1
k
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
r
P
m
.If the edge e
m
∈
P
(
m
) is coloured by one of the shades of colour r, that is, by r
A
j, 1
≤
r
≤
k, 1
≤
j
≤
b
r, then, according to the definition of (i
A
j; i
∈
I, j
∈
I
i)-edge colouring by monochromatic paths, the number σ
(
i
A
j
;
i
∈
I
,
j
∈
I
i
)
r
(
P
(
m
)
)
=
σ
(
i
A
j
;
i
∈
I
,
j
∈
I
i
)
(
P
(
m
-
r
)
) is the number of all (i
A
j; i
∈
I, j
∈
I
i)-edge colourings by monochromatic paths of the graph P
(
m
-
r
). Taking into account that we consider b
r shades of every colour r, we get(30)
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
P
m
=
b
1
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
P
m
-
1
+
⋯
+
b
k
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
P
m
-
k
,which ends the proof.For the special case ofσ
(
i
A
j
;
i
∈
I
,
j
∈
I
i
)
(
P
(
m
)
), we can prove the following.Theorem 5.
Letk and m be integers. Then,(1)
σ
(
A
1
,
2
A
1
)
(
P
(
m
)
)
=
F
m for m
≥
1,
(2)
σ
(
A
1
,
A
2
,
2
A
1
)
(
P
(
m
)
)
=
P
m
+
1 for m
≥
1,
(3)
σ
(
A
1
,
2
A
1
,
2
A
2
)
(
P
(
m
)
)
=
J
m
+
1 for m
≥
1,
(4)
σ
(
A
1
,
2
A
1
,
3
A
1
)
(
P
(
m
)
)
=
T
m
+
1
∗ for m
≥
1,
(5)
σ
(
2
A
1
,
3
A
1
)
(
P
(
m
)
)
=
P
v
(
m
-
2
) for m
≥
2,
(6)
σ
(
A
1
,
2
A
1
,
…
,
k
A
1
)
(
P
(
m
)
)
=
f
m
+
k
-
1 for k
≥
2 and m
≥
k
-
1,
(7)
σ
(
A
1
,
k
A
1
)
(
P
(
m
)
)
=
F
(
k
,
m
-
k
+
1
) for k
≥
2 and m
≥
k
-
1,
(8)
σ
(
A
1
,
…
,
A
k
,
2
A
1
)
(
P
(
m
)
)
=
F
k
(
m
+
1
) for k
≥
1 and m
≥
1,
(9)
σ
(
A
1
,
(
k
-
1
)
A
1
,
k
A
1
)
(
P
(
m
)
)
=
P
(
k
,
m
-
k
+
3
) for k
≥
2 and m
≥
k
-
3,
(10)
σ
(
A
1
,
A
2
,
2
A
1
,
…
,
2
A
k
)
(
P
(
m
)
)
=
P
k
(
m
+
1
) for k
≥
1 and m
≥
1,
(11)
σ
(
A
1
,
2
A
1
,
k
A
1
)
(
P
(
m
)
)
=
P
d
(
k
,
m
+
k
-
2
) for k
≥
1 and m
≥
k
-
2,
(12)
σ
(
A
1
,
k
A
1
,
k
A
2
,
…
,
k
A
t
)
(
P
(
m
)
)
=
J
(
k
,
t
,
m
+
1
) for k
≥
2 and m
≥
1,
(13)
σ
(
2
A
1
,
k
A
1
)
(
P
(
m
)
)
=
F
2
(
2
)
(
k
,
m
) for k
≥
1 and m
≥
1.Proof.
Letm be as in each statement of the theorem. For the initial terms in each case, we determine the number σ
(
i
A
j
;
i
∈
I
,
j
∈
I
i
)
(
G
) by inspection. We will analyze some cases.
(
1
) Consider (
A
1
,
2
A
1
)-edge colouring by monochromatic paths of P
(
m
). If m
=
1 then the unique edge of P
(
1
) is coloured by colour A
1. If m
=
2 then we have a path with two edges. So there are exactly two (
A
1
,
2
A
1
)-edge colourings of P
(
2
) in the first case using colour A
1 and in the second case using the colour 2
A
1. In each case, the graph P
(
2
) is monochromatic. Then, σ
(
A
1
,
2
A
1
)
(
P
(
1
)
)
=
1
=
F
1 and σ
(
A
1
,
2
A
1
)
(
P
(
2
)
)
=
2
=
F
2.
(
2
) Now consider (
A
1
,
A
2
,
2
A
1
)-edge colouring by monochromatic paths of P
(
m
). If m
=
1 then there are exactly two (
A
1
,
A
2
,
2
A
1
)-edge colourings of P
(
1
). The unique edge can be coloured either by A
1 or by A
2. Thus, σ
(
A
1
,
A
2
,
2
A
1
)
(
P
(
1
)
)
=
2
=
P
2. Let m
=
2. Then, using only colours A
1 and A
2 we can colour edges of the graph P
(
2
) as follows: A
1
A
1, A
1
A
2, A
2
A
1, A
2
A
2. Moreover, there is the unique colouring of the graph P
(
2
) using the colour 2
A
1. Then, P
(
2
) is 2
A
1-monochromatic. Consequently, σ
(
A
1
,
A
2
,
2
A
1
)
(
P
(
2
)
)
=
5
=
P
3.
(
7
)
Consider (
A
1
,
k
A
1
)-edge colouring by monochromatic paths of P
(
m
). If m
=
k
-
1, then there is a unique (
A
1
,
k
A
1
)-edge colouring using only colour A
1. Let m
=
k
+
i, where i
=
0
,
…
,
k
-
1. Then, in the path P
(
m
), one k
A
1-monochromatic subpath can exist at most or P
(
m
) is A
1-monochromatic. Because k
A
1-monochromatic path can be chosen on i
+
1 ways, σ
(
A
1
,
k
A
1
)
(
P
(
m
)
)
=
i
+
2
=
F
(
k
,
i
+
1
).
In the same way, we can verify the initial conditions in the remaining cases(
3
)
–
(
6
) and (
8
)
–
(
13
).
By the initial conditions and by Theorem4 the result follows.Analogously as for pathsP
(
m
) we can prove the following theorem for the cycle C
(
m
).Theorem 6.
Letk
≥
2 and m
≥
k
-
1 be integers. Then, (31)
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
C
m
=
∑
r
=
1
k
b
r
r
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
P
m
-
r
.Proof.
LetC
(
m
) be a cycle of a size m with the numbering of its edges in the natural fashion. Let σ
(
i
A
j
;
i
∈
I
,
j
∈
I
i
)
r
(
C
(
m
)
) denote the number of all (i
A
j; i
∈
I, j
∈
I
i)-edge colourings by monochromatic paths of C
(
m
) such that the edge e
1
∈
E
(
C
(
m
)
) has the colour from the fixed C
r, where 1
≤
r
≤
k. Clearly, (32)
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
C
m
=
∑
r
=
1
k
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
r
C
m
.If the edge e
1
∈
E
(
C
(
m
)
) is coloured by the colour r
A
j, where 1
≤
r
≤
k and 1
≤
j
≤
b
r, then (33)
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
C
m
=
r
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
P
m
-
r
.The factor r follows from the fact that the edge e
1 can belong to an r
A
j-monochromatic path (of length r) on r ways, 1
≤
r
≤
i.
Moreover, in the setC
r, we have b
r shades of the colour r and r can be chosen on k ways; thus, (34)
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
C
m
=
∑
r
=
1
k
b
r
r
σ
i
A
j
;
i
∈
I
,
j
∈
I
i
P
m
-
r
,which ends the proof.Using the above theorem, we can give a graph interpretation for the cyclic version of the Fibonacci type. Firstly, we recall some identities given in [6, 13, 16, 17] which will be useful to prove the next theorem.Forn
≥
1 and k
≥
1,(35)
L
k
n
=
F
k
n
-
1
+
F
k
n
+
1(see [13]). For k
≥
2 and n
≥
2
k,(36)
L
k
,
n
=
k
F
k
,
n
-
2
k
+
1
+
F
k
,
n
-
k(see [16]). For k
≥
3 and n
≥
k,(37)
Q
d
k
,
n
=
P
d
k
,
n
+
k
-
3
+
2
P
d
k
,
n
+
k
-
4
+
k
P
d
k
,
n
-
2(see [6]). For k
≥
3, n
≥
k
-
1, and t
≥
1,(38)
J
L
k
,
t
,
n
=
J
k
,
t
,
n
+
1
+
t
k
-
1
J
k
,
t
,
n
-
k
+
1(see [6]). For k
≥
2 and n
≥
k,(39)
L
2
2
k
,
n
=
2
F
2
2
k
,
n
-
2
+
k
F
2
2
k
,
n
-
k(see [17]).To prove the next theorem, we need the following lemma.Lemma 7.
Letk
≥
1 and m
≥
1 be integers. Then,(40)
2
P
k
m
+
2
k
P
k
m
-
1
=
Q
k
m
.Proof (by induction onm).
Ifm
=
1, then 2
P
k
(
1
)
+
2
k
P
k
(
0
)
=
2
=
Q
k
(
1
). Assume that formula (40) holds for an arbitrary m. We will prove it for m
+
1. By the recurrence definitions of the numbers P
k
(
m
) and Q
k
(
m
) and by induction hypothesis, we have(41)
Q
k
m
+
1
=
2
Q
k
m
+
k
Q
k
m
-
1
=
2
2
P
k
m
+
2
k
P
k
m
-
1
+
k
2
P
k
m
-
1
+
2
k
P
k
m
-
2
=
2
2
P
k
m
+
k
P
k
m
-
1
+
2
k
2
P
k
m
-
1
+
k
P
k
m
-
2
=
2
P
k
m
+
1
+
2
k
P
k
m
,which ends the proof of Lemma 7.Theorem 8.
Letk and m be integers. Then,(1)
σ
(
A
1
,
2
A
1
)
(
C
(
m
)
)
=
L
m, for m
≥
3,
(2)
σ
(
A
1
,
2
A
1
,
2
A
2
)
(
C
(
m
)
)
=
j
m, for m
≥
3,
(3)
σ
(
2
A
1
,
3
A
1
)
(
C
(
m
)
)
=
P
r
(
m
), for m
≥
5,
(4)
σ
(
A
1
,
…
,
A
k
,
2
A
1
)
(
C
(
m
)
)
=
L
k
(
m
), for k
≥
1 and m
≥
3,
(5)
σ
(
A
1
,
A
2
,
2
A
1
,
…
,
2
A
k
)
(
C
(
m
)
)
=
Q
k
(
m
), for k
≥
1 and m
≥
3,
(6)
σ
(
A
1
,
k
A
1
)
(
C
(
m
)
)
=
L
(
k
,
m
), for k
≥
2 and m
≥
2
k
-
1,
(7)
σ
(
A
1
,
2
A
1
,
k
A
1
)
(
C
(
m
)
)
=
Q
d
(
k
,
m
), for k
≥
3 and m
≥
k,
(8)
σ
(
A
1
,
k
A
1
,
…
,
k
A
t
)
(
C
(
m
)
)
=
J
L
(
k
,
t
,
m
), for k
≥
3 and m
≥
k
+
1,
(9)
σ
(
2
A
1
,
k
A
1
)
(
C
(
m
)
)
=
L
2
(
2
)
(
k
,
m
), for k
≥
2 and m
≥
k
+
1.Proof.
Letk and m be as in each statement of the theorem.
(
1
) From Theorem 6, we have that (42)
σ
A
1
,
2
A
1
C
m
=
σ
A
1
,
2
A
1
P
m
-
1
+
2
σ
A
1
,
2
A
1
P
m
-
2
.Moreover, by Theorem 5, by the recurrence relation of Fibonacci numbers and the well-known identity for Lucas numbers follows (43)
σ
A
1
,
2
A
1
C
m
=
F
m
-
1
+
2
F
m
-
2
=
F
m
+
F
m
-
2
=
L
m
,which ends the proof of (
1
).
(
2
) From Theorems 5 and 6, by the recurrence relation of Jacobsthal numbers and the well-known identity for Jacobsthal numbers, we obtain(44)
σ
A
1
,
2
A
1
,
2
A
2
C
m
=
σ
A
1
,
2
A
1
,
2
A
2
P
m
-
1
+
4
σ
A
1
,
2
A
1
,
2
A
2
P
m
-
2
=
J
m
+
4
J
m
-
1
=
J
m
+
1
+
2
J
m
-
1
=
j
mwhich ends the proof of (
2
).
Analogously, like in the previous cases, using Theorems5 and 6 and Lemma 7 and applying known identities for considered numbers, we prove the other conditions such as in what follows.
(
3
)   σ
(
2
A
1
,
3
A
1
)
(
C
(
m
)
)
=
2
σ
(
2
A
1
,
3
A
1
)
(
P
(
m
-
2
)
)
+
3
σ
(
2
A
1
,
3
A
1
)
(
P
(
m
-
3
)
)
=
2
P
v
(
m
-
4
)
+
3
P
v
(
m
-
5
)
=
2
P
v
(
m
-
2
)  +  P
v
(
m
-
5
)
=
P
r
(
m
).
(
4
)   σ
(
A
1
,
…
,
A
k
,
2
A
1
)
(
C
(
m
)
)
=
k
σ
(
A
1
,
…
,
A
k
,
2
A
1
)
(
P
(
m
-
1
)
)
+
2
σ
(
A
1
,
…
,
A
k
,
2
A
1
)
(
P
(
m
-
2
)
)
=
k
F
k
(
m
)
+
2
F
k
(
m
-
1
)
=
k
F
k
(
m
)  +  F
k
(
m
-
1
)
+
F
k
(
m
-
1
)
=
F
k
(
m
+
1
)
+
F
k
(
m
-
1
)
=
L
k
(
m
) by (35).
(
5
)   σ
(
A
1
,
A
2
,
2
A
1
,
…
,
2
A
k
)
(
C
(
m
)
)
=
2
σ
(
A
1
,
A
2
,
2
A
1
,
…
,
2
A
k
)
(
P
(
m
-
1
)
)
+
2
k
σ
(
A
1
,
A
2
,
2
A
1
,
…
,
2
A
k
)
(
P
(
m
-
2
)
)
=
2
P
k
(
m
)
+
2
k
P
k
(
m
-
1
)  =  Q
k
(
m
) by Lemma 7.
(
6
)
σ
(
A
1
,
k
A
1
)
(
C
(
m
)
)
=
σ
(
A
1
,
k
A
1
)
(
P
(
m
-
1
)
)
+
k
σ
(
A
1
,
k
A
1
)
(
P
(
m
-
k
)
)
=
F
(
k
,
m
-
k
)
+
k
F
(
k
,
m
-
2
k
+
1
)
=
L
(
k
,
m
) by (36), which ends the proof of (
6
).
(
7
)
σ
(
A
1
,
2
A
1
,
k
A
1
)
(
C
(
m
)
)
=
σ
(
A
1
,
2
A
1
,
k
A
1
)
(
P
(
m
-
1
)
)
+
2
σ
(
A
1
,
2
A
1
,
k
A
1
)
(
P
(
m
-
2
)
)
+
k
σ
(
A
1
,
2
A
1
,
k
A
1
)
(
P
(
m
-
k
)
) = P
d
(
k
,
m
+
k
-
3
)
+
2
P
d
(
k
,
m
+
k
-
4
)
+
k
P
d
(
k
,
m
-
2
)
=
Q
d
(
k
,
m
) by (37), which ends the proof of (
7
).
(
8
)
σ
(
A
1
,
k
A
1
,
…
,
k
A
t
)
(
C
(
m
)
)
=
σ
(
A
1
,
k
A
1
,
…
,
k
A
t
)
(
P
(
m
-
1
)
)
+
t
k
σ
(
A
1
,
k
A
1
,
…
,
k
A
t
)
(
P
(
m
-
k
)
)
=
J
(
k
,
t
,
m
)
+
t
k
J
(
k
,
t
,
m
-
k  +  1
)
=
J
(
k
,
t
,
m
)
+
t
(
k
-
1
)
J
(
k
,
t
,
m
-
k
+
1
)
+
t
J
(
k
,
t
,
m
-
k
+
1
)
=
J
(
k
,
t
,
m
+
1
)
+
t
(
k
-
1
)
J
(
k
,
t
,
m
-
k
+
1
)  =  J
L
(
k
,
t
,
m
) by (38), which ends the proof of (
8
).
(
9
)
σ
(
2
A
1
,
k
A
1
)
(
C
(
m
)
)
=
2
σ
(
2
A
1
,
k
A
1
)
(
P
(
m
-
2
)
)
+
k
σ
(
2
A
1
,
k
A
1
)
(
P
(
m
-
k
)
)
=
2
F
2
(
2
)
(
k
,
m
-
2
)
+
k
F
2
(
2
)
(
k
,
m
-
k
)  =  L
2
(
2
)
(
k
,
m
) by (39), which ends the proof of (
9
).
Thus, the theorem is proved.


## 3.(
A
1
,
2
A
1
)-Edge Colouring in Trees

We can study (i
A
j; i
∈
I, j
∈
I
i)-edge colouring by monochromatic paths in distinct classes of graphs. For arbitrary k and b
i, i
≥
0, the problem seems to be difficult but some interesting results can be obtained for fixed k and b
i, i
=
1
,
…
,
k. Assume that k
=
2 and b
1
=
b
2
=
1. Then, the (
A
1
,
2
A
1
)-edge colouring always exists in an arbitrary graph G. In this section, we consider the number of all (
A
1
,
2
A
1
)-edge colourings in trees.Theorem 9.
LetT
(
m
) be a tree of size m, m
≥
1. Then, (45)
F
m
≤
σ
A
1
,
2
A
1
T
m
≤
1
+
∑
j
≥
1
m
2
j
∏
p
=
0
j
-
1
2
j
-
2
p
+
1
.Moreover, for(46)
σ
A
1
,
2
A
1
P
m
=
F
m
,
T
m
=
P
mand for (47)
σ
A
1
,
2
A
1
S
m
=
1
+
∑
j
≥
1
m
2
j
∏
p
=
0
j
-
1
2
j
-
2
p
+
1
,
T
m
=
S
m
.Proof.
LetT
(
m
) be a tree of size m, m
≥
1. Firstly, we will show that (48)
σ
A
1
,
2
A
1
T
m
≥
F
m
.We prove it by induction on m. If m
=
1,2 then T
(
m
) is isomorphic to P
(
m
) and the result is obvious. Let x
∈
V
(
T
(
m
)
) be a leaf incident with the edge x
y
∈
E
(
T
(
m
)
) such that y
z
∈
E
(
T
(
m
)
) and T
(
m
)
∖
{
x
y
,
y
z
} is isomorphic to either T
(
m
-
2
)
∪
{
x
,
z
} or T
(
m
-
2
)
∪
{
x
,
y
}. Such leaf x
∈
V
(
T
(
m
)
) always exists in a tree, by the basic tree properties. This means that T
(
m
-
2
) is a tree. Since isolated vertices are not taken into consideration in (
A
1
,
2
A
1
)-edge colourings, it suffices to consider the tree T
(
m
-
2
).
Assume thatx, y, and z are as above and consider the following possibilities.
(i)x
y
∈
E
(
T
(
m
)
) has the colour A
1
.
Then, the subgraphT
(
m
)
∖
{
x
y
} is isomorphic to T
(
m
-
1
)
∪
{
x
} and has the (
A
1
,
2
A
1
)-edge colouring. By our assumption, there is at least F
m
-
1 such (
A
1
,
2
A
1
)-edge colourings of T
(
m
) in this case.
(ii)x
y
∈
E
(
T
(
m
)
) has the colour 2
A
1
.
Then, by the definition of the(
A
1
,
2
A
1
)-edge colouring, it immediately follows that there is a 2
A
1-monochromatic subgraph with a partition θ into 2
A
1-monochromatic paths of length 2.
LetH
≤
T
(
m
) be a maximal 2
A
1-monochromatic subgraph with a partition θ. Let y
z
∈
E
(
H
) have the colour 2
A
1 and the path x
y
,
y
z belongs to θ. Then, the subgraph T
(
m
)
∖
{
x
y
,
y
z
} also has (
A
1
,
2
A
1
)-edge colouring and |
E
(
T
(
m
)
∖
{
x
y
,
y
z
}
)
|
=
m
-
2. Clearly, the edge x
y
∈
E
(
T
(
m
)
) belongs to at least one partition θ of the 2
A
1-monochromatic subgraph of T
(
m
) into 2
A
1-monochromatic paths of length 2. Consequently, if x
y
∈
E
(
T
(
m
)
) has the colour 2
A
1, then the number of all (
A
1
,
2
A
1
)-edge colourings of T
(
m
) is greater than or equal to the number σ
(
A
1
,
2
A
1
)
(
T
(
m
)
∖
{
x
y
,
y
z
}
). Since T
(
m
)
∖
{
x
y
,
y
z
} has two isolated vertices, it suffices to consider T
(
m
-
2
), so σ
(
A
1
,
2
A
1
)
(
T
(
m
)
∖
{
x
y
,
y
z
}
)
≥
σ
(
A
1
,
2
A
1
)
(
T
(
m
-
2
)
)
≥
F
m
-
2 by the induction hypothesis. From the above, σ
(
A
1
,
2
A
1
)
(
T
(
m
)
)
≥
F
m
-
1
+
F
m
-
2
=
F
m. By Theorem 5, the equality is obvious.
Now we show that(49)
σ
A
1
,
2
A
1
T
m
≤
1
+
∑
j
≥
1
m
2
j
∏
p
=
0
j
-
1
2
j
-
2
p
+
1
.Since T
(
m
) is a connected graph, the maximum value is attained if both edges are adjacent. This means that T
(
m
) is the star. Then, there is a maximum number of substars with even number of edges. Consequently, it suffices to calculate the number of all substars of a star with even number of edges. Since |
E
(
T
(
m
)
)
|
=
m and we choose even number of edges, we have at least ∑
j
≥
1
m
2
j possibilities of choosing of subset of even edges. Moreover, 2
j edges can be partitioned into (
2
j
-
1
)
(
2
j
-
3
)
·
⋯
·
3
·
1 ways. Additionally, T
(
m
) can be A
1-monochromatic.
All this together gives thatσ
(
A
1
,
2
A
1
)
(
T
(
m
)
)
≤
1
+
∑
j
≥
1
m
2
j
∏
p
=
0
j
-
1
[
2
j
-
(
2
p
+
1
)
]. The proof of equalities is obvious.


## 4. Concluding Remarks

Studying the parameterσ
(
i
A
j
;
i
∈
I
,
j
∈
I
i
)
(
G
), we can find the graph interpretation with respect to (i
A
j; i
∈
I, j
∈
I
i)-edge colourings by monochromatic paths for other numbers of the Fibonacci type not considered in this paper. For some of them, such as the Tribonacci numbers T
n, it does not work in paths and cycles. We can ask about the existence of a graph G for which σ
(
i
A
j
;
i
∈
I
,
j
∈
I
i
)
(
G
)
=
T
n. It is also interesting to consider problems of determining the parameter σ
(
i
A
j
;
i
∈
I
,
j
∈
I
i
)
(
G
) in distinct classes, clearly for a special (i
A
j; i
∈
I, j
∈
I
i)-edge colouring by monochromatic paths.



---

*Source: 837917-2015-10-19.xml*