# Extremal Trees with respect to Number of(A,B,2C)-Edge Colourings

Authors: Krzysztof Piejko
Journal: Journal of Applied Mathematics
 (2015)

---

## Abstract

We determine the smallest and the largest number of(A,B,2C)-edge colourings in trees. We prove that the star is a unique tree that maximizes the number of all of the (A,B,2C)-edge colourings and that the path is a unique tree that minimizes it.


---

## Body

## 1. Introduction and Preliminary Results

For a general concept, see [1]. The Fibonacci sequence {Fn} is defined recursively by the second-order recurrence relation Fn=Fn-1+Fn-2 for n≥2 with the initial conditions F0=F1=1. A related sequence is the Pell sequence {Pn} defined by Pn=2Pn-1+Pn-2 for n≥2 with P0=0, P1=1. Table 1 includes first terms of the sequence {Pn}. The terms of Fibonacci and Pell sequences are called Fibonacci numbers and Pell numbers, respectively. The numbers of the Fibonacci type play an important role in distinct areas of mathematics and they have many different applications and interpretations. Some of them are closely related to the Hosoya index Z(G) (defined as a number of all matchings in the graph G, including the empty matching) and the Merrifield-Simmons index σ(G) (defined as a number of all independent sets in G, including the empty set); see [2] and its references. It is well-known that σ(Pn)=Fn and Z(Pn∘K1)=Pn+1, for n≥1, where Pn is an n-vertex path, Kn is an n-vertex complete graph, and G∘H denotes the corona of two graphs. The numbers of the Fibonacci type in the graph theory were studied intensively also in [3–15].Table 1
The first terms of{Pn} and {sn}.
n
0
1
2
3
4
5
6
7
8
9
10
11
P
n
0
1
2
5
12
29
70
169
408
985
2378
5741
s
n
1
2
5
14
43
142
499
1850
7193
123109
538078
2430355Consider a simple, undirected graphG with the vertex set V(G) and the edge set E(G). In [11] we introduced an (a1A1,a2A2,…,apAp)-edge colouring of a graph G defined in the following way. Let G be p-edge coloured graph with the set of colours {A1,A2,…,Ap}, where p≥2. Moreover, let a1,a2,…,ap be positive integers. We say that a subgraph of G is M-monochromatic if all its edges are coloured alike by colour M∈{A1,A2,…,Ap}. The graph G is said to be (a1A1,a2A2,…,apAp)-edge coloured, if every maximal (with respect to set inclusion) Ai-monochromatic subgraph of G can be partitioned into edge-disjoint paths of the length ai, i=1,2,…,p. This type of edge colouring of graph generalizes the edge colouring introduced by Piejko and Włoch in [10] and the edge colouring by monochromatic paths introduced by Trojnar-Spelina and Włoch in [13]. Many interesting results concerning some special kinds of (a1A1,a2A2,…,apAp)-edge colouring of graphs can be found in [10, 11]. We recall some of them.Let{A,B,C} be the set of colours. By (A,B,2C)-edge colouring we denote the 3-edge colouring of graph G, such that every C-monochromatic subgraph of G can be partitioned into edge-disjoint paths of the even length. Let δ(G) be the number of all (A,B,2C)-edge colourings of the graph G. The following result was given in [10].Theorem 1 (see [10]).
Letn≥2 be an integer. Then δ(Pn)=Pn.Let{sn} be the sequence defined by the relation sn=2sn-1+(n-1)sn-2 for n≥2 with the initial conditions s0=1, s1=2. We can find a few first terms of {sn} in Table 1.The sequence{sn} has many distinct interpretations also in graphs. It is worth mentioning that sn is the Hosoya index of the corona of the complete graphs Kn and K1; that is, Z(Kn∘K1)=sn for n≥1. For more interpretations see [16, 17].Another interpretation of the sequence{sn} in graphs, which is closely related to (A,B,2C)-edge colouring of n-edge star K1,n, was given in [11].Theorem 2 (see [11]).
Letn be a positive integer. Then δ(K1,n)=sn.In [12] Prodinger and Tichy proved that the star is a tree that maximizes the Merrifield-Simmons index, while the path is a tree that minimizes it. In this paper we obtain an analogous result for the number of (A,B,2C)-edge colourings in trees.LetG and H be given graphs with distinguished vertices x∈V(G) and y∈V(H). By Gx∗Hy we denote the graph obtained from G and H by identifying vertices x and y (see Figure 1) and by Gx+Hy we denote the graph obtained from G and H by adding the edge xy (see Figure 2).Figure 1
The graphGx∗Hy.Figure 2
The graphGx+Hy.Fore∈E(G) the notation G∖{e} means the graph obtained from G by deleting the edge e. We prove the following.Theorem 3.
Letx∈V(G), y∈V(H) and let x1,x2,…,xk∈V(G) be neighbours of x and let y1,y2,…,yl∈V(H) be neighbours of y, where k and l are positive integers. Then (1)δGx+Hy=2δGδH+δH∑i=1kδG∖xxi+δG∑j=1lδH∖yyj,(2)δGx∗Hy≥δGδH+∑i=1k∑j=1lδH∖yyjδG∖xxi.Furthermore, if l=1 then (3)δGx∗Hy=δGδH+δH∖yy1∑i=1kδG∖xxi.Proof.
ByδA, δB, and δC we denote the number of all (A,B,2C)-edge colourings of the graph Gx+Hy such that an edge xy has a colour A, B, or C, respectively. It can be easily seen that δA and δB are equal to the number of all (A,B,2C)-edge colourings of the graph G, multiplied by the number of all (A,B,2C)-edge colourings of the graph H. Moreover, δC is equal to the number of all (A,B,2C)-edge colourings of the graph H multiplied by the number of all (A,B,2C)-edge colourings of graphs G∖{xxi}, where i=1,2,…,k, plus the number of all (A,B,2C)-edge colourings of the graph G multiplied by the number of all (A,B,2C)-edge colourings of graphs H∖{yyj}, where j=1,2,…,l. In other words, δA=δB=δ(G)δ(H) and (4)δC=δH∑i=1kδG∖xxi+δG∑j=1lδH∖yyj.Since δ(Gx+Hy)=δA+δB+δC, then we obtain equality (1).
Byei we denote the edge xxi∈E(G), where i=1,2,…,k and by ej′ we denote the edge yyj∈E(H), where j=1,2,…,l. Assume that r=min{k,l} and for t∈{0,1,2,…,r} let ζ(t) be the number of all (A,B,2C)-edge colourings of the graph Gx∗Hy with exactly tC-monochromatic paths {e,e′}⊂E(Gx∗Hy), such that e∈{e1,e2,…,ek} and e′∈{e1′,e2′,…,el′}. Observe that ζ(0)=δ(G)δ(H) and (5)ζ1=∑i=1k∑j=1lδG∖xxiδH∖yyj.It should be noted that δ(Gx∗Hy)=∑t=0rζ(t) and so δ(Gx∗Hy)≤ζ(0)+ζ(1), which gives inequality (2). Moreover, if l=1 then also r=1 and we obtain equality (3). This completes the proof.


## 2. The Largest Number of(A,B,2C)-Edge Colourings in Trees

In this section we will show that, among all trees with the given number of verticesn, the star K1,n-1 maximizes the number of (A,B,2C)-edge colourings. Moreover the star K1,n-1 is the unique tree with such property. To prove it we need the following.Theorem 4.
Letm≥2 be an integer. Then for a graph G and arbitrary x∈V(G) one has (6)δGx∗K1,mv<δGx∗K1,mv0,where v is the leaf of K1,m and v0 is the center of K1,m.Proof.
LetV(K1,m)={v0,v1,…,vm} and E(K1,m)={v0v1,v0v2,…,v0vm}. Let x∈V(G) be the vertex of degree k≥1 and let x1,x2,…,xk∈V(G) be neighbours of x. By (3) in Theorem 3 we have (7)δGx∗K1,mv=δGδK1,m+δK1,m-1∑i=1kδG∖xxiand by inequality (2) in Theorem 3 we have (8)δGx∗K1,mv0≥δGδK1,m+∑i=1k∑j=1mδK1,m∖v0vjδG∖xxi.It should be noted that ∑j=1mδ(K1,m∖{v0vj})=mδ(K1,m-1) and so (8) gives (9)δGx∗K1,mv0≥δGδK1,m+mδK1,m-1∑i=1kδG∖xxi.Since m≥2, then from (7) and (9) we have δ(Gx∗K1,mv)<δ(Gx∗K1,mv0), which completes the proof.Theorem 5.
Letn≥2 be an integer and let Tn be a tree with n vertices. Then (10)δTn≤δK1,n-1.Proof (by induction on the number of vertices of degreek≥2 in the tree Tn).
LetTn,t be an n-vertex tree with exactly t vertices of degree k≥2. If t=1 then the result is obvious, because Tn,1 is an n-vertex star K1,n-1. Assume that inequality (10) holds for Tn,t with arbitrary t≥1. We will prove that it holds for Tn,t+1. Note that for each tree Tn,t+1 there exists x∈V(Tn,t+1), such that Tn,t+1 is isomorphic to Tn-m+1,tx∗K1,m-1v, where v is the leaf of the star K1,m-1 and m≥3. Applying Theorem 4 we have (11)δTn,t+1=δTn-m+1,tx∗K1,m-1v<δTn-m+1,tx∗K1,m-1v0,where v0 is the center of the star K1,m-1. Note that Tn-m+1,tx∗K1,m-1v0 is the n-vertex tree with t vertices of the degree k≥2. Thus, by the induction hypothesis we have δ(Tn,t+1)≤δ(K1,n-1), which completes the proof.Remark 6.
From Theorems4 and 5 we can see that the star K1,n-1 is a unique graph which maximizes the number of (A,B,2C)-edge colourings in trees of given order n.


## 3. The Smallest Number of(A,B,2C)-Edge Colourings in Trees

Now we show that, among all trees with the given number of verticesn, the path Pn minimizes the number of all (A,B,2C)-edge colourings and that it is the unique tree with such property. To prove it we need some initial results. First we prove the following property of the Pell numbers.Theorem 7.
Letq≥2 and mi≥1 be integers for i=1,2,…,q. Then (12)∑i=1qPm-miPmi>Pm-1,where m=m1+m2+⋯+mq+1.Proof (by induction onq).
Forq=2 we have (13)∑i=12Pm1+m2+1-miPmi=Pm1Pm2+1+Pm1+1Pm2>Pm1+m2.We can check the above inequality using the well-known identity for the Pell numbers (14)PnPm+1+Pn-1Pm=Pn+m.Assume that inequality (12) holds for an arbitrary q≥2. We show that it holds for q+1; namely, (15)∑i=1q+1Pm+mq+1-miPmi>Pm+mq+1-1,where mq+1 is a positive integer and m=m1+m2+⋯+mq+1. Using (14) and the induction hypothesis we obtain (16)∑i=1q+1Pm+mq+1-miPmi=∑i=1qPm+mq+1-miPmi+PmPmq+1=∑i=1qPm-mi+1Pmq+1+Pm-miPmq+1-1Pmi+PmPmq+1=Pmq+1∑i=1qPm-mi+1Pmi+Pmq+1-1∑i=1qPm-miPmi+PmPmq+1>Pmq+1Pm-1+Pmq+1-1Pm-1+PmPmq+1>Pm-1Pmq+1-1+PmPmq+1=Pm+mq+1-1,which ends the proof.Letm1,m2,…,mq, q≥2, be positive integers. By Sm1,m2,…,mq we denote the subdivision of a star K1,q in such way that in the resulting graph an ith edge of K1,q is replaced by a path of length mi, i=1,2,…,q. For m1=m2=⋯=mq=1 the graph S1,1,…,1 is a star K1,q and for q=2 the graph Sm1,m2 is a path Pm1+m2+1. For q=3 the star subdivision Sm1,m2,m3 is called a tripod. In [11] we proved that (17)δSm1,m2,m3=Pm1+m2+m3+1+2Pm1Pm2Pm3for all positive integers m1, m2, and m3. We will use the following notations: (18)VSm1,m2,…,mq=y0∪y11,y21,…,ym11∪y12,y22,…,ym22∪⋯∪y1q,y2q,…,ymqq,ESm1,m2,…,mq=y0y11,y11y21,…,ym1-11ym11∪y0y12,y12y22,…,ym2-12ym22∪⋯∪y0y1q,y1qy2q,…,ymq-1qymqq.Theorem 8.
Letm1,m2,…,mq, q≥3, be positive integers. Then (19)δSm1,m2,…,mq>Pm1+m2+⋯+mq+1.Proof (by induction onq).
Ifq=3 then the result we have immediately from (17). Assume that the inequality holds for t=3,4,…,q, with arbitrary q≥3. We will prove that it holds for t=q+1. Note that Sm1,…,mq,mq+1 is isomorphic to Sm1,…,mqy0∗Pmq+1+1v, where y0 is the center of Sm1,…,mq, v is the leaf of Pmq+1+1, and mq+1 is a positive integer. Thus, applying (3) of Theorem 3 we obtain (20)δSm1,…,mq,mq+1=δPmq+1+1δSm1,…,mq+δPmq+1∑i=1qδSm1,…,mq∖y0y1i.Note that for all i∈{1,2,…,q}(21)δSm1,…,mq∖y0y1i=δSm1,m2,…,mi-1,mi+1,…,mqδPmi.By induction hypothesis we have δ(Sm1,m2,…,mi-1,mi+1,…,mq)>Pm-mi for all i∈{1,2,…,q} and m=m1+m2+⋯+mq+1. Therefore (21) and Theorems 1 and 7 give (22)∑i=1qδSm1,…,mq∖y0y1i>∑i=1qPm-miPmi>Pm-1.Thus by (20), (22), and Theorem 1 we have (23)δSm1,…,mq,mq+1>Pmq+1+1δSm1,…,mq+Pmq+1Pm-1.By the induction hypothesis we have δSm1,…,mq>Pm and so (23) gives (24)δSm1,…,mq,mq+1>Pmq+1+1Pm+Pmq+1Pm-1.Using identity (14) we have δ(Sm1,…,mq,mq+1)>Pm+mq+1=Pm1+⋯+mq+mq+1+1, which completes the proof.Theorem 9.
Letm1,m2,…,mq, q≥2, be positive integers and let m=m1+m2+⋯+mq+1. Then for a graph G and arbitrary x∈V(G) one has (25)δGx+Sm1,m2,…,mqy0>δGx+Pmv,where y0 is the center of Sm1,m2,…,mq and v is the leaf of the path Pm.Proof.
Letx∈V(G) be the vertex of degree k≥1 and let x1,x2,…,xk∈V(G) be neighbours of x. Note that Gx+Sm1,m2,…,mqy0 is isomorphic to Gx∗Sm1,m2,…,mq,1y, where Sm1,m2,…,mq,1 is the graph obtained from Sm1,m2,…,mq by adding a vertex y and an edge y0y. Therefore, equality (3) of Theorem 3 gives (26)δGx+Sm1,m2,…,mqy0=δGδSm1,m2,…,mq,1+δSm1,m2,…,mq∑i=1kδG∖xxi.Moreover equality (1) of Theorem 3 gives (27)δGx+Pmv=2δGδPm+δPm∑i=1kδG∖xxi+δGδPm-1.By (27), Theorem 1, and the definition of (Pn) we obtain (28)δGx+Pmv=δGPm+1+Pm∑i=1kδG∖xxi.From Theorem 8 we have δ(Sm1,m2,…,mq,1)>Pm+1 and δ(Sm1,m2,…,mq)≥Pm and so (26) and (28) give δ(Gx+Sm1,m2,…,mqy0)>δ(Gx+Pmv), which ends the proof.Theorem 10.
Letn≥2 be an integer and let Tn be a tree with n vertices. Then (29)δTn≥δPn.Proof (by induction on the number of vertices of degreek≥3 in the tree Tn).
LetTn,t be the n-vertex tree with exactly t vertices of degree k≥3. If t=0 then the result is obvious, because Tn,0 is an n-vertex path Pn. Assume that inequality (29) holds for Tn,t with arbitrary t≥0. We will prove that it holds for Tn,t+1. Note that for each tree Tn,t+1 there exists x∈V(Tn,t+1), such that Tn,t+1 is isomorphic to Tn-m,tx+Sm1,m2,…,mqy0, where y0 is the center of Sm1,m2,…,mq, m=m1+m2+⋯+mq+1, and q≥2. Applying Theorem 9 we have (30)δTn,t+1=δTn-m,tx+Sm1,m2,…,mqy0>δTn-m,tx+Pmv,where v is the leaf of the path Pm. Note that Tn-m,tx+Pmv is the n-vertex tree with t vertices of degree k≥3. Thus by the induction hypothesis we have δ(Tn,t+1)≥δ(Pn) and the proof is complete.Remark 11.
From Theorems9 and 10 we can see that the path Pn is a unique graph which minimizes the number of (A,B,2C)-edge colourings in trees of given order n.From previous theorems we have also the following.Corollary 12.
IfTn is a tree with the number of vertices n≥2, then (31)Pn≤δTn≤sn-1.Moreover, ifTn is different from Pn and K1,n-1, then (32)Pn<δTn<sn-1.



---

*Source: 463650-2015-12-14.xml*