Also available at http://amc.imfm.si
ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 3 (2010) 215–235
On the extremal values of
the ratios of number of paths
Damir Vukičević
Department of Mathematics, Faculty of Mathematics and Natural Sciences
University of Split, Nikole Tesle 12, HR-21000 Split, Croatia
Tomaž Pisanski
Department of Theoretical Computer Science, IMFM and
University of Ljubljana, Jadranska 19, 1000 Ljubljana, Slovenia
Received 12 July 2008, accepted 1 January 2010, published online 26 December 2010
Abstract
In this paper, we analyze the ratios of the numbers of paths pi (G) and pj (G) of differ-
ent length in graph G. Namely, we are interested in the extremal values of these ratios for
acyclic and cyclic graphs with given maximal degree. The values of infinum and supremum
for graphs with given maximal degree are obtained. Also, the infinum of these ratios for
trees with given maximal degree are obtained. Suprema for trees of given maximal degree
are given when ratios of paths of length 1 and 2 are observed, and when ratios of paths of
lengths 1 and 3 are observed. As the main result, a linear algorithm (in terms of maximal
degree) for finding suprema of the ratios of the numbers of paths of length 2 and 3 for trees
with given maximal degree is presented.
Keywords: Extremal graph, path, push to leaves.
Math. Subj. Class.: 05C35, 05C38
1 Introduction
In this paper, we analyze the possible values of the ratio of the numbers of the paths of
lengths i and j, i > j. Namely we are interested in the extremal values [2] of the ratio
pi(G)
pj(G)
where pi (G) and pj (G) are the numbers of (unoriented) paths of length i and j,
respectively. We restrict ourselves to the simple graphs and henceforth the term graph shall
imply simple graph.
E-mail addresses: vukicevi@pmfst.hr (Damir Vukičević), tomaz.pisanski@fmf.uni-lj.si (Tomaž Pisanski)
Copyright c© 2010 DMFA Slovenije
216 Ars Math. Contemp. 3 (2010) 215–235
Denote by T (∆, j) the family of all trees with maximum degree ∆ that contain at least
one path of length j and by G (∆, j) family of connected graphs of maximum degree ∆ that
contain at least one path of length j. We define functions: φGij ,Φ
G
ij , φ
T
ij ,Φ
T
ij : N\ {1} → R
by
φGij (∆) = inf
G∈G(∆,j)
pi (G)
pj (G)
;
φTij (∆) = inf
T∈T (∆,j)
pi (T )
pj (T )
;
ΦGij (∆) = sup
G∈G(∆,j)
pi (G)
pj (G)
;
ΦTij (∆) = sup
T∈T (∆,j)
pi (T )
pj (T )
.
for all i, j ∈ N, i > j.
Remark 1.1. Removing the requirement of connectivity in the definition of G (∆, j) , then
φGij (∆) = 0, since
lim
x→∞
pi (G+ x · Pj+1)
pj (G+ x · Pj+1)
= lim
x→∞
pi (G)
pj (G) + x
= 0.
for all G ∈ G (∆, j) where G+ x · Pj+1 is the disjoint union of G and x paths of length j.
On the other hand if G is a graph with connected components G1, . . . , Gk we have
pi (G)
pj (G)
≤ max
{
pi (G1)
pj (G1)
, . . . ,
pi (Gk)
pj (Gk)
}
≤ max
{
ΦGij (1) ,Φ
G
ij (2) , . . . ,Φ
G
ij (∆)
}
= {see remark 2.14} ≤ ΦGij (∆)
hence ΦGij does not change whether we require connectivity or not. Therefore, we can
restrict ourselves to connected graphs. From now on, we use the term graph to imply
simple connected graph.
Finding an extremal value of, not a single invariant, but an arithmetic operation on
two invariants is not a new concept. It is the concept at the core of AutoGraphX software
[1]. Here, we choose paths. They are well known mathematical objects. But, they are
also important descriptors in chemistry, especially paths of length two and three. Their
numbers are closely related to the Zagreb indices M1 and M2 which are very well known
in chemistry (see [3, 6, 8] and references within), defined by:
M1 (G) =
∑
v∈V (G)
dG (v)
2
;
M2 (G) =
∑
uv∈E(G)
dG (u) · dG (v) ;
where dG (u) is the degree of a vertex u in the graph G, V (G) is the set of vertices of G,
and E (G) is the set of edges of G. It can be shown that:
p2 (G) =
1
2
M1 (G)− e (G) ,
D. Vukičević and T. Pisanski: On the extremal values of the ratios of number of paths 217
where e (G) is the number of edges of graph G and that
p3 (G) = M2 (G)−M1 (G) + e (G)
for all triangle-free graphs. Comparisons of the Zagreb indices have been extensively stud-
ied [4, 9, 10, 11]. Besides this, path numbers are themselves interesting molecular descrip-
tors. References about the use of path numbers in defining molecular descriptors and their
applications in chemistry can be found in [7].
2 Results for the infimum
Denote by G (∆, x) the graph presented in the following figure:
where e (G) is the number of edges of graph G and that
p3 (G) =M2 (G)−M1 (G) + e (G)
for all triangle-free graphs. Comparisons of the Zagreb indices have been exten-
sively studied [4,9,10,11]. Besides this, path numbers are themselves i teresting
molecular descriptor . References about t u of path numbers in defining
molecular descriptors and their applications in chemistry can b found in [7].
2 Results for the infimum
Denote by G (∆, x) the graph prese ted in the following figure:
...
...
u1
u2
u3
u 
v w1 w2 wx
-1
Let us prove:
Proposition 2 It holds that φGij (∆) = 0 and φ
T
ij (∆) = 0 for all j < i, i ≥ 3
and ∆ ∈ N\ {1} .
Proof. Just note that pi (G (∆, j − 1)) = 0 and that pj (G (∆, j − 1)) > 0.
Proposition 3 It holds that
φG21 (2) = φ
T
21 (2) =
1
2
and φG21 (∆) = φ
T
21 (∆) = 1
for all ∆ ∈ N\ {1, 2} .
Proof. The only graphs with ∆ = 2 are the path Pn on n vertices and the cycle
Cn on n vertices, where n ≥ 3. It holds that:
p2 (Cn)
p1 (Cn)
=
n
n
= 1,
and
p2 (Pn)
p1 (Pn)
=
n− 2
n− 1 ,
3
Let us prove:
Proposition 2.1. It holds that φGij (∆) = 0 and φTij (∆) = 0 for all j < i, i ≥ 3 and
∆ ∈ N\ {1} .
Proof. Just note that pi (G (∆, j − 1)) = 0 and that pj (G (∆, j − 1)) > 0.
Prop sition 2.2. It holds that
T φG21 ( ) φ
T
21 ( ) 1
for all ∆ ∈ N\ {1, 2} .
Proof. The only graphs with ∆ = 2 are the path Pn on n vertices and the cycle Cn on n
vertices, where n ≥ 3. It holds that:
,
and
2 ( )
1 ( )
,
hence
φG21 (2) = φ
T
21 (2) = inf
n≥3
n− 2
n− 1
=
1
2
.
218 Ars Math. Contemp. 3 (2010) 215–235
Note that
p2 (G (∆, x))
p1 (G (∆, x))
=
(
∆
2
)
+ (x− 1) ·
(
2
2
)
∆− 1 + x
,
hence
φG21 (∆) ≤ φT21 (∆) ≤ lim
x→∞
(
∆
2
)
+ (x− 1) ·
(
2
2
)
∆− 1 + x
= 1.
In order to prove that
φT21 (∆) ≥ φG21 (∆) ≥ 1,
for every ∆ ≥ 3, it is sufficient to show that
p2 (G)− p1 (G) ≥ 0 for each G with ∆ ≥ 3
Denote by ni the number of vertices of degree i in graph G with maximum degree at least
3, and by v (G) the (total) number of its vertices. We have
e (G) ≥ v (G)− 1∑∆
i=1 i · ni
2
≥
∆∑
i=1
ni − 1
n1 ≤
∆∑
i=3
(i− 2)ni + 2
n1 ≤
∆∑
i=3
i · ni
hence
p2 (G)− p1 (G) =
∆∑
i=1
(
i
2
)
ni −
∑∆
i=1 i · ni
2
=
1
2
∆∑
i=1
(
i2 − 2i
)
ni =
=
1
2
[
∆∑
i=3
(
i2 − 2i
)
ni − n1
]
≥ 1
2
[
∆∑
i=3
(
i2 − 2i
)
ni −
∆∑
i=3
i · ni
]
=
=
1
2
∆∑
i=1
(
i2 − 3i
)
ni ≥ 0.
Let P be any path. We say that P ′ is an end-subpath of P if it is a subpath of P and if
it contains an end-vertex of P.
Proposition 2.3. Let ∆ ≥ 2 and i > j. Then,
ΦGij (∆) = (∆− 1)
i−j
.
Proof. Let G be any graph. Note that each path of length i contains two paths of length
j as end-subpaths. On the other hand any path of length j can be end-subpath of at most
D. Vukičević and T. Pisanski: On the extremal values of the ratios of number of paths 219
2·(∆− 1)i−j paths of length i, because we have 2 choices for the direction of the extension
and at most ∆− 1 choices for adding each subsequent vertex. Therefore,
pj (G) ≤
2 · (∆− 1)i−j
2
≤ (∆− 1)i−j ,
hence
ΦGij (∆) ≤ (∆− 1)
i−j
.
Now, letG be a ∆-uniform graph (i.e. a graph in which all vertices have degree ∆) without
a cycle of length less then ∆ + 1. The existence of such graph follows from the results of
paper [5]. Then
pi (G)
pj (G)
=
1
2 · v (G) ·∆ · (∆− 1)
i−1
1
2 · v (G) ·∆ · (∆− 1)
j−1 = (∆− 1)
i−j
.
This proves the Theorem.
Determining the functions ΦTij is a much harder problem. Here, we restrict ourselves to
the cases i, j ≤ 3, i.e. to analyses of the functions ΦT21, ΦT31 and ΦT32. First, let us determine
ΦT21 :
Proposition 2.4. Let ∆ ≥ 2. Then
ΦT21 (∆) =
∆
2
.
Proof. Let T be any tree and ni number of the vertices of degree i, i = 1, . . . ,∆. It holds
that:
p2 (T )
p1 (T )
=
∑∆
i=1
(
i
2
)
ni
1
2
∑∆
i=1 i · ni
=
∑∆
i=1
(
i2 − i
)
ni∑∆
i=1 i · ni
= (∗) .
From e (T ) = v (T )− 1, it follows that∑∆
i=1 i · ni
2
=
∆∑
i=1
ni − 1
n1 − 2 =
∆∑
i=3
(i− 2)ni.
Hence
(∗) =
n1 ·
(
12 − 1
)
+ n2 ·
(
22 − 2
)
+
∑∆
i=3
(
i2 − i
)
ni
2 · 1 + (n1 − 2) · 1 + n2 · 2 +
∑∆
i=3 i · ni
=
0 + 2n2 +
∑∆
i=3
(
i2 − i
)
ni
2 + 2n2 +
∑∆
i=3 (2i− 2) · ni
≤ max
{{
0
2
,
2
2
}
∪
{
i2 − i
2i− 2
: i = 3, ..,∆
}}
=
∆
2
.
220 Ars Math. Contemp. 3 (2010) 215–235
Therefore ΦT21 (∆) ≤ ∆2 . Let T (∆, k) be a tree with the distinguished vertex v such that
all vertices have degree either ∆ or 1, and all leaves are at distance k from the root. Then
lim
k→∞
p2 (T (∆, k))
p1 (T (∆, k))
= lim
k→∞
(
1 + ∆ ·
∑k−2
i=0 (∆− 1)
i
)
·
(
∆
2
)[(
1 + ∆ ·
∑k−2
i=0 (∆− 1)
i
)
·∆ + ∆ · (∆− 1)k−1
]
/2
= lim
k→∞
∆ · (∆−1)
k−1−1
∆−2 ·∆ · (∆− 1)
∆ · (∆−1)
k−1−1
∆−2 ·∆ + ∆ · (∆− 1)
k−1
=
= lim
k→∞
∆ · (∆− 1)k−1 ·∆ · (∆− 1)
∆ · (∆− 1)k−1 ·∆ + ∆ · (∆− 1)k−1 · (∆− 2)
=
=
∆ · (∆− 1)
∆ + (∆− 2)
=
∆2 −∆
2∆− 2
=
∆
2
.
Hence, ΦT21 (∆) ≥ ∆2 .
Now, we shall need the concept of ”pushed to leaves” function. Let T be a rooted tree
with root r and let ρ : E (T ) → R be any function. The ”pushed to leaves” function
ρr : L (T ) → R (L (T ) from the set of leaves to the set of real numbers is defined by
pushing the weight of the edges to the leaves in the following way: Let l be any leaf and
rv1 . . . vkl a path from r to l. Then
ρr (l) =
ρ (rv1)
(d (v1)− 1) (d (v2)− 1) . . . (d (vk)− 1)
+
ρ (v1v2)
(d (v2)− 1) . . . (d (vk)− 1)
+
+ · · ·+ ρ (vk−1vk)
d (vk)− 1
+ ρ (vkl) .
An example of how the weight of a single edge is pushed to the leaves is presented in the
following figure:in the following figure:
v
f(vw)
w
·1/2
·1/2
·1/2
·1/2
·1
·1/3
·1/3
·1/3
f(vw)/2
f(vw)/4
f(vw)/12
f(vw)/12
f(vw)/12
r
It can easily be seen that
∑
uv∈E(T )
ρ (uv) =
∑
v∈L(T )
ρr (v) . Now, let us
prove:
Proposition 6 Let ∆ ≥ 2. Then
ΦT31 (∆) = ∆− 1.
Proof. First, let us prove that ΦT31 (∆) = ∆−1. Let T be any tree. Note that the
number of paths of length 3 having a middle edge uv is (d (u)− 1) · (d (v)− 1) .
Hence
p3 (T ) =
∑
uv∈E(T )
(d (u)− 1) · (d (v)− 1) ;
p1 (T ) =
∑
uv∈E(T )
1
Choose any vertex r ∈ V (T ) \L (T ) . Since p3 and p2 are expressed as the
sum of the contributions of edge-weights, the functions pr1 and p
r
2 can be defined
and we have:
p3 (T )
p1 (T )
=
pr3 (T )
pr1 (T )
=
∑
v∈L(T )
pr3 (v)
∑
v∈L(T )
pr1 (v)
≤ max
v∈L(T )
pr3 (v)
pr1 (v)
Let vv1v2...vk−1vk (vk = r) be a path from v to r and denote di = d (vi) We
7
It can easily be seen that
∑
uv∈E(T ) ρ (uv) =
∑
v∈L(T ) ρ
r (v) . Now, let us prove:
Proposition 2.5. Let ∆ ≥ 2. Then
ΦT31 (∆) = ∆− 1.
D. Vukičević and T. Pisanski: On the extremal values of the ratios of number of paths 221
Proof. First, let us prove that ΦT31 (∆) = ∆ − 1. Let T be any tree. Note that the number
of paths of length 3 having a middle edge uv is (d (u)− 1) · (d (v)− 1) . Hence
p3 (T ) =
∑
uv∈E(T )
(d (u)− 1) · (d (v)− 1) ;
p1 (T ) =
∑
uv∈E(T )
1
Choose any vertex r ∈ V (T ) \L (T ) . Since p3 and p2 are expressed as the sum of
the contributions of edge-weights, the functions pr1 and p
r
2 can be defined and we have:
p3 (T )
p1 (T )
=
pr3 (T )
pr1 (T )
=
∑
v∈L(T )
pr3 (v)∑
v∈L(T )
pr1 (v)
≤ max
v∈L(T )
pr3 (v)
pr1 (v)
Let vv1v2 . . . vk−1vk (vk = r) be a path from v to r and denote di = d (vi) We have:
max
v∈L(T )
pr3 (v)
pr2 (v)
=
=
[
(1− 1) · (d1 − 1) + (d1−1)·(d2−1)d1−1 +
(d2−1)·(d3−1)
(d1−1)·(d2−1)+
+ · · ·+ (dk−1−1)·(dk−1)(d1−1)·(d2−1)·····(dk−2−1)·(dk−1−1)
]
[
1 + 1d1−1 +
1
(d1−1)·(d2−1)+
+ · · ·+ 1(d1−1)·(d2−1)·····(dk−2−1) +
1
(d1−1)·(d2−1)·····(dk−2−1)·(dk−1−1)
]
≤
(d2 − 1) + d3−1(d1−1) + · · ·+
dk−1
(d1−1)·(d2−1)·····(dk−2−1)[
1 + 1d1−1 +
1
(d1−1)·(d2−1)+
+ · · ·+ 1(d1−1)·(d2−1)·····(dk−2−1) +
1
(d1−1)·(d2−1)·····(dk−2−1)·(dk−1−1)
] .
≤
∆− 1 + ∆−1(d1−1) + · · ·+
∆−1
(d1−1)·(d2−1)·····(dk−2−1)[
1 + 1d1−1 +
1
(d1−1)·(d2−1)+
+ · · ·+ 1(d1−1)·(d2−1)·····(dk−2−1) +
1
(d1−1)·(d2−1)·····(dk−2−1)·(dk−1−1)
]
≤ ∆− 1.
Hence, ΦT31 (∆) ≤ ∆− 1. Let T (∆, k) be defined as above. We have:
lim
k→∞
p3 (T (∆, k))
p1 (T (∆, k))
=
= lim
k→∞
(
∆ ·
∑k−2
i=0 (∆− 1)
i
)
· (∆− 1)2 +
(
∆ · (∆− 1)k−1
)
· (∆− 1) · (1− 1)(
∆ ·
∑k−1
i=0 (∆− 1)
i
)
= lim
k→∞
∆ · (∆−1)
k−1−1
∆−1−1 · (∆− 1)
2
∆ · (∆−1)
k−1
∆−1−1
= lim
k→∞
(∆− 1)k−1 · (∆− 1)2
(∆− 1)k
= ∆− 1
Hence, ΦT31 (∆) ≥ ∆− 1.
222 Ars Math. Contemp. 3 (2010) 215–235
Determining of ΦT32 is much more complex problem. Let us start with the simplest case:
Proposition 2.6. ΦT32 (2) = 1.
Proof. The tree with maximum degree 2 is a path. Denote by Pn the path on n vertices. It
holds that p3(Pn)p2(Pn) =
n−3
n−2 and therefore
sup
T∈T (2,2)
p3 (T )
p2 (T )
= sup
n≥3
n− 3
n− 2
= 1.
Denote
f (x1, x2, . . . , xk) =
x1x2
x1
+ x2x3x1x2 + · · ·+
xk−1xk
x1...xk−1
x1 +
x1+x2
x1
+ x2+x3x1x2 + · · ·+
xk−1+xk
x1...xk−1
.
Note that f (x1, x2, . . . , xk) ≤ m/2 for all x1, x2, . . . , xm. Hence, it can be defined:
Γ (m) = sup
k∈N, x1,...,xk−1∈{1,...,m}
f (x1, x2, . . . , xk−1,m) .
Note that k = 1 on the right hand-side implies that we observe f (m) . Now, we shall prove
several auxiliary lemmas:
Lemma 2.7. Φ32 (∆) = 2 · Γ (∆− 1) for all ∆ > 2.
Proof. Recall that the number of paths of length 3 with a middle edge uv is (d (u)− 1) ·
(d (v)− 1) and that the number of paths of length 2 with middle vertex v is
(
d(v)
2
)
. Hence
p3 (T ) =
∑
uv∈E(T )
(d (u)− 1) · (d (v)− 1) ;
p2 (T ) =
∑
v∈V (T )
(
d (v)
2
)
=
1
2
∑
v∈V (T )
d (v) · (d (v)− 1) =
=
1
2
∑
v∈V (T )
∑
u∈V (T ):uv∈E(T )
(d (v)− 1) = 1
2
∑
uv∈E(T )
[(d (u)− 1) + (d (v)− 1)] .
Choose any vertex r ∈ V (T ) of degree ∆. Since p3 and p2 are expressed as the sum
of the contributions of edge-weights, functions pr1 and p
r
2 can be defined and we have:
p3 (T )
p2 (T )
=
pr3 (T )
pr2 (T )
=
∑
v∈L(T )
pr3 (v)∑
v∈L(T )
pr2 (v)
.
First, let us prove that
Φ32 (∆) ≤ 2 · Γ (∆− 1) .
It is sufficient to prove that for each T ∈ T (∆, 2) it holds that:
p3 (T )
p2 (T )
=
∑
v∈L(T )
pr3 (v)∑
v∈L(T )
pr2 (v)
≤ 2 · sup
k∈N, x1,...,xk−1∈{1,...,∆−1}
f (x1, x2, . . . , xk−1,∆− 1) .
D. Vukičević and T. Pisanski: On the extremal values of the ratios of number of paths 223
Note that ∑
v∈L(T )
pr3 (v)∑
v∈L(T )
pr2 (v)
≤ max
l∈L(T )
pr3 (l)
pr2 (l)
.
Denote by l the leaf for which the observed ratio obtains its maximum and let lv1v2 . . .
vq (vq = r) be a path from l to r. Denote di = d (vi) We have:
max
v∈L(T )
pp3 (v)
pp2 (v)
=
=
[
(1− 1) · (d1 − 1) + (d2−1)(d1−1)(d1−1) +
+ (d3−1)(d2−1)(d1−1)(d2−1) + · · ·+
(dq−1−1)(dq−1)
(d1−1)(d2−1)·(dq−1−1)
]
1
2
[
(1− 1) + (d1 − 1) + (d2−1)+(d1−1)(d1−1) +
+ (d3−1)+(d2−1)(d1−1)(d2−1) + · · ·+
(dq−1−1)+(dq−1)
(d1−1)(d2−1)·(dq−1−1)
]
= 2 · f (d1 − 1, d2 − 1, . . . , dq − 1)
≤ 2 · sup
k∈N, x1,...,xk−1∈{1,...,∆−1}
f (x1, x2, . . . , xk−1,∆− 1) = 2 · Γ (∆− 1) .
Now, let us prove that
Φ (∆) ≥ 2 · Γ (∆− 1) .
It is sufficient to prove that
Φ (∆) ≥ 2 · f (x1, x2, . . . , xk−1,∆− 1)
for each (x1, . . . , xk−1) where xi ∈ {1, . . . ,∆− 1} , i = 1, . . . , k. Set xk = ∆ − 1.
Denote by T (x1, . . . , xk) a tree such that the following hold:
1) There is a distinguished vertex r ∈ V (T (x1, . . . , xk)) of degree xk + 1 such that
all leaves are at distance k from r
2) Let lv1 . . . vk−1r be a path from any leaf l to v. Then, d (vi) = xi + 1 for every
vertex vi.
We have:
Φ (∆) ≥ p3 (T (x1, . . . , xk))
p2 (T (x1, . . . , xk))
=
∑
v∈L(T (x1,...,xk))
pr3 (v)∑
v∈L(T (x1,...,xk))
pr2 (v)
= 2 · f (x1, . . . , xk) .
Lemma 2.8. Let m ≥ 2, then
Γ (m) ≤ m
3/2
m+ 1
224 Ars Math. Contemp. 3 (2010) 215–235
Proof. For each k ∈ N, each x1, . . . , xk−1 ∈ {1, . . . ,m} , xk = m, and each λ ∈ [0, 1],
we have
x1x2
x1
+ x2x3x1x2 + · · ·+
xk−1xk
x1...xk−1
x1 +
x1+x2
x1
+ x2+x3x1x2 + · · ·+
xk−1+xk
x1...xk−1
=
=
x1x2
x1
+ x2x3x1x2 + · · ·+
xk−1xk
x1...xk−1
(1− λ)x1 + λx
2
1+x1+(1−λ)x2
x1
+
λx22+x2+(1−λ)x3
x1x2
+ · · ·+ λx
2
k−1+xk−1+xk
x1...xk−1
=

λx21+x1+(1−λ)x2
x1
· x1x2
λx21+x1+(1−λ)x2
+
+
λx22+x2+(1−λ)x3
x1x2
· x2x3
λx22+x2+(1−λ)x3
+ · · ·+
λx2k−1+xk−1+xk
x1...xk−1
· xk−1xk
λx2k−1+xk−1+xk

(1− λ)x1 + λx
2
1+x1+(1−λ)x2
x1
+
λx22+x2+(1−λ)x3
x1x2
+ · · ·+ λx
2
k−1+xk−1+xk
x1...xk−1
= (∗)
Let
S = inf
λ∈[0,1]
max
a,b∈{1,...,m}
ab
a+ λa2 + (1− λ) b
We have
(∗) ≤
[
x1+x2+λx
2
2
x2x3...xk
· S + (1−λ)x2+x3+λx
2
3
x3...xk
· S + · · ·+ + (1−λ)xk−1+xk+λx
2
k
xk
· S
]
[
x1+x2+λx22
x2x3...xk
+
(1−λ)x2+x3+λx23
x3...xk
+ · · ·+ (1−λ)xk−1+xk+λx
2
k
xk
] ≤ S
Let us calculate the upper bound of maxa,b∈{1,...,m} aba+λa2+(1−λ)b . We have
max
a,b∈{1,...,m}
ab
a+ λa2 + (1− λ) b
=
= max
a,b∈{1,...,m}
ab
a2 ·
(
λ+ 1a
)
+ (1− λ) b
≤ max
a,b∈{1,...,m}
ab
2 ·
√(
λ+ 1a
)
a2 · b (1− λ)
= max
a,b∈{1,...,m}
√
b
2 ·
√
(1− λ)
(
λ+ 1a
)
≤ {increasing in a and b} ≤
√
m
2 ·
√
(1− λ)
(
λ+ 1m
)
Using simple analytical calculation to maximize (1− λ)
(
λ+ 1m
)
for λ ∈ [0, 1] , we obtain
S = inf
λ∈[0,1]
√
m
2 ·
√
(1− λ)
(
λ+ 1m
) = m3/21 +m.
which proves the claim.
D. Vukičević and T. Pisanski: On the extremal values of the ratios of number of paths 225
Denote
X (m) = {(x1,m,m) : x1 ∈ {1, . . . ,m}}∪
∪
{
(x1, x2,m) : x1 ∈
{
1, . . . ,
⌊
m3/2
m+ 1
⌋}
, x2 ∈ {1, . . . ,m}
}
∪
∪
{
(x1, x2, x3) : x1, x2 ∈
{
1, . . . ,
⌊
m3/2
m+ 1
⌋}
, x3 ∈ {1, . . . ,m}
}
gm (x1, x2, x3) =
x1x2
x1
+ x2x3x1x2 +
x3m
x1x2x3
+ 1x1x2x3 ·
m2
m−1
x1 +
x1+x2
x1
+ x2+x3x1x2 +
x3+m
x1x2x3
+ 1x1x2x3 ·
2m
m−1
and
Ψ (m) = max
(x1,x2,x3) ∈X(m)
gm (x1, x2, x3)
Let us prove:
Lemma 2.9. Let m ≥ 2, then
m
m+ 1
≤ Ψ (m) ≤ m
3/2
m+ 1
≤ m
2
.
Proof. First, let us prove that Γ (m) ≥ mm+1 . It is sufficient to prove that
g (1,m,m) ≥ m
m+ 1
,
i.e. that
2m+ 1 + 1m−1
4 +m+ 2m +
2
m(m−1)
≥ m
m+ 1
2m2 + 3m+ 1 +
m+ 1
m− 1
≥ m2 + 4m+ 2 + 2
m− 1
m2 ≥ m
which is obviously true.
Simple calculation shows that
m3/2
m+ 1
≤ m
2
.
Now, let us prove that Γ (m) ≤ m
3/2
m+1 . It is sufficient to prove that for each
(x1, x2, x3) ∈ X,
it holds that:
gm (x1, x2, x3) ≤
m3/2
m+ 1
.
Note that
lim
n→∞
f
x1, x2, x3,m, . . . ,m︸ ︷︷ ︸
n-times
 = gm (x1, x2, x3) .
226 Ars Math. Contemp. 3 (2010) 215–235
Hence,
gm (x1, x2, x3) ≤ Γ (m) ≤
m3/2
m+ 1
.
This proves the Lemma.
Let us prove:
Lemma 2.10. Let k and m ≥ 2 be positive integers and r real number such that mm+1 ≤
r ≤ m2 , and k ≥ 2. Then
max
t1,t2,...,tk∈{1,...,m}
t1t2 − rt1 − rt2
t1
+
t2t3 − rt2 − rt3
t1t2
+ · · ·+ tk−1tk − rtk−1 − rtk
t1t2t3 . . . tk−1
≤ (m− 2r) ·
1− 1
mk
1− 1m
.
Proof. We prove the claim by induction on k. First suppose that k = 2. It is sufficient to
prove that
t1t2 − rt1 − rt2
t1
≤ m− 2r
Note that m − 2r ≥ 0. If t1 ≤ r then t1t2 − rt1 − rt2 is negative and the claim holds. If
t1 > r, the left hand-side is increasing in t2, hence
t1t2 − rt1 − rt2
t1
≤ t1m− rt1 − rm
t1
= m− r − rm
t1
≤ {increasing in t1} ≤ m− 2r.
Now, suppose that k > 2 and that claim holds for smaller values of k. We have:
t1t2 − rt1 − rt2
t1
+
t1t2 − rt1 − rt2
t1t2
+
t2t3 − rt2 − rt3
t1t2t3
+ · · ·+ tk−1tk − rtk−1 − rtk
t1t2t3 . . . tk−1
=
t1t2 − rt1 − rt2
t1
+
1
t1
·
(
t2t3 − rt2 − rt3
t2
+
t3t4 − rt3 − rt4
t2t3
+ · · ·+ tk−1tk − rtk−1 − rtk
t2t3 . . . tk−1
)
≤ {by the inductive hypothesis}
=
t1t2 − rt1 − rt2
t1
+
1
t1
(m− 2r) ·
1− 1
mk−1
1− 1m
If t1 ≤ r then
t1t2 − rt1 − rt2
t1
+
1
t1
(m− 2r) ·
1− 1
mk−1
1− 1m
≤ 1
t1
(m− 2r) ·
1− 1
mk−1
1− 1m
≤ (m− 2r) ·
1− 1
mk−1
1− 1m
≤ (m− 2r) ·
1− 1
mk
1− 1m
.
D. Vukičević and T. Pisanski: On the extremal values of the ratios of number of paths 227
Otherwise,
t1t2 − rt1 − rt2
t1
+
1
t1
(m− 2r) ·
1− 1
mk−1
1− 1m
≤ {increasing in t2}
≤ mt1 − rt1 − rm
t1
+
1
t1
(m− 2r) ·
1− 1
mk−1
1− 1m
= m− r + 1
t1
·
[
(m− 2r) ·
1− 1
mk−1
1− 1m
− rm
]
= (∗)
In order to prove that (∗) is increasing in t1, we need to prove that
(m− 2r) ·
1− 1
mk−1
1− 1m
− rm ≤ 0.
It is sufficient to prove that
m− 2r
1− 1m
≤ rm,
but this is equivalent to
m ≤ rm− r + 2r
r ≥ m
m+ 1
Therefore, (∗) is increasing in t1, and
(∗) ≤ m− r + 1
m
·
[
(m− 2r) ·
1− 1
mk−1
1− 1m
− rm
]
= (m− 2r) ·
(
1 +
1
m
·
1− 1
mk−1
1− 1m
)
= (m− 2r) ·
1− 1
mk
1− 1m
,
which proves the Lemma.
Now, let us prove the key Lemma.
Lemma 2.11. Let m ≥ 2, then
Γ (m) = Ψ (m) .
Proof. Denote r = Ψ (m) and denote (y1, y2, y3) ∈ X (m) such that gm (y1, y2, y3) = r.
We have:
Γ (m) = sup
k∈N,x1,...,xk∈{1,2,...,m}
f (x1, . . . , xk) ≥ lim
k→∞
f
y1, y2, y3,m, . . . ,m︸ ︷︷ ︸
(k−3)-times

= lim
k→∞
y1y2
y1
+ y2y3y1y2 +
y3m
y1y2y3
+ m
2
y1y2y3
·
(
1
m +
1
m2 + · · ·+
1
mk−4
)
y1 +
y1+y2
y1
+ y2+y3y1y2 +
y3+m
y1y2y3
+ 2my1y2y3 ·
(
1
m +
1
m2 + · · ·+
1
mk−4
)
= gm (y1, y2, y3) = r
228 Ars Math. Contemp. 3 (2010) 215–235
Suppose to the contrary that
sup
k∈N,x1,...,xk−1∈{1,2,...,m}
f (x1, . . . , xk−1,m) > r. (2.1)
Denote by S1 set of finite ordered sequences (x1, . . . , xk−1, xk) such that xk = m and
f (x1, . . . , xk) > r.
Note that this last relation can be rewritten as
h (x1, . . . , xk) = −rx1 +
x1x2 − rx1 − rx2
x1
+
x2x3 − rx2 − rx3
x1x2
+ · · ·+ xk−1xk − rxk−1 − rxk
x1 . . . xk−1
> 0 (2.2)
From (2.1) , it follows that S1 is a non-empty set. Let S2 be the set of sequences in S1
which have one of the following two properties:
1) There are no entries from [r,m〉 and all ms are located at the end of the sequence;
2) There is a single entry from the set [r,m〉; there is no m before this entry and all
entries after this one are equal to m.
Let us prove that S3 is non-empty. Let (b1, . . . , bk2) ∈ S2. Let i be the first entry greater
or equal r (note that at least bk2 = m ≥ r). If i = k2, then (b1, . . . , bk2) ∈ S2, hence
suppose that i < k2. In order to prove that
b1, . . . , bi, m, . . . ,m︸ ︷︷ ︸
(k2−i)-times
 ∈ S2, it is sufficient
to prove that
h
b1, . . . , bi, m, . . . ,m︸ ︷︷ ︸
(k2−i)-times
 ≥ h (b1, . . . , bk2) ≥ 0,
i.e. that
h
b1, . . . , bi, m, . . . ,m︸ ︷︷ ︸
(k2−i)-times
− h (b1, . . . , bk2) ≥ 0.
We have:h
b1, . . . , bi, m, . . . ,m︸ ︷︷ ︸
(k2−i)-times
− h (b1, . . . , bk2)
 · b1b2 . . . .bi =
= (bim− rm− rbi) +
m ·m− 2rm
m
+
m ·m− 2rm
m2
+ · · ·+ m ·m− 2rm
mk2−i−1
− (bibi+1 − rbi − rbi+1)−
bi+1bi+2 − rbi+1 − rbi+2
bi+1
− . . .
− bk2−1bk2 − rbk2−1 − rbk2
bi+1 . . . bk2
=
= [(bi − r) · (m− bi+1)]
+
[ (
m·m−2rm
m +
m·m−2rm
m2 + · · ·+
m·m−2rm
mk2−i−1
)
−(
bi+1bi+2−rbi+1−rbi+2
bi+1
+ · · ·+ bk2−1bk2−rbk2−1−rbk2bi+1...bk2
) ] .
D. Vukičević and T. Pisanski: On the extremal values of the ratios of number of paths 229
The first square bracket is non-negative because it is the product of two non-negative num-
bers. From Lemma 2.9 it follows that mm+2 ≤ r ≤
m
2 and then from Lemma 2.10, it follows
that the second square bracket is non-negative, so S2 is non-empty. Let c = (c1, . . . , ck2)
be an element of S2 with the following properties:
1) c has the least number of entries smaller then r;
2) Among all the elements of S2 with the same number of entries smaller then r, c is
the shortest sequence.
Note that all these entries are at the beginning of the sequence. Hence, assume that
c1, . . . , cj are smaller then r and cj+1, . . . , ck3 are larger then r. Distinguish two cases:
CASE 1: h (c1, . . . , ck3) ≥ h (c1, c2)
SUBCASE 1.1: j ≥ 3.
Because of the minimality of (c1, . . . , ck3) , it follows that (c1, c3, c4, ck3) /∈ S3, hence
h (c1, . . . , ck3) > 0
h (c1, c3, c4, . . . , ck3) < 0
Therefore
h (c1, . . . , ck3) > h (c1, c3, c4, . . . , ck3) .
We have:
h (c1, . . . , ck3) ≤ h (c1, . . . , ck3) + (c2 − 1) · (h (c1, . . . , ck3)− h (c1, c2))
≤ −rc1 +
c1c2 − rc1 − rc2
c1
+
c2c3 − rc2 − rc3
c1
+
c3c4 − rc3 − rc4
c1c3
+ . . .
+
ck3−1ck3 − rck3−1 − rck3
c1c3 . . . ck3−1
≤
≤ h (c1, c3, c4, . . . , ck3) +
c1c2 − rc1 − rc2
c1
+
c2c3 − rc2 − rc3
c1
− c1c3 − rc1 − rc3
c1
≤ h (c1, c3, c4, . . . , ck3) +
≤0︷ ︸︸ ︷
(c1 − r)c2
c1
+
c2 ·
≤0︷ ︸︸ ︷
(c3 − r)
c1
− c1c3
c1
≤ h (c1, c3, c4, . . . , ck3) ,
which is a contradiction.
SUBCASE 1.2: j ≤ 2.
If k3 = 2, then c2 = m and
0 < −rc1 +
c1m− rc1 − rm
c1
<
< −rc1 +
c1m− rc1 − rm
c1
+
m2 − 2rm
c1m
+
m2 − 2rm
c1m2
,
hence (c1,m,m,m) ∈ S1. If k3 = 3, then c3 = m and
0 < −rc1 +
c1c2 − rc1 − rc2
c1
+
c2m− rc2 − rm
c1c2
<
< −rc1 +
c1c2 − rc1 − rc2
c1
+
c2m− rc2 − rm
c1c2
+
m2 − 2rm
c1c2m
,
230 Ars Math. Contemp. 3 (2010) 215–235
hence (c1, c2,m,m) ∈ S1. If k3 > 3, then c3 ≥ r and all entries after c3 are equal to m.
Hence, in any case there is an element of S1 of the form c′ =
z1, z2, z3,m . . . ,m︸ ︷︷ ︸
t-times
 ,
where t ≥ 1 and (z1, z2, z3) ∈ X. Since, c′ ∈ S1, it follows that f (c′) > g (z1, z2, z3) ,
i.e.
x1x2
x1
+ x2x3x1x2 +
x3m
x1x2x3
+ 1x1x2x3 ·m
2 · 1−
1
mt
m−1
x1 +
x1+x2
x1
+ x2+x3x1x2 +
x3+m
x1x2x3
+ 1x1x2x3 · 2m ·
1− 1
mt
m−1
>
x1x2
x1
+ x2x3x1x2 +
x3m
x1x2x3
+ 1x1x2x3 ·m
2 · 1m−1
x1 +
x1+x2
x1
+ x2+x3x1x2 +
x3+m
x1x2x3
+ 1x1x2x3 · 2m ·
1
m−1
(2.3)
Denote
α1 =
x1x2
x1
+
x2x3
x1x2
+
x3m
x1x2x3
β1 = x1 +
x1 + x2
x1
+
x2 + x3
x1x2
+
x3 +m
x1x2x3
γ1 =
1
x1x2x3
· 2m ·
1− 1mt
m− 1
δ1 =
1
x1x2x3
· 2m · 1
m− 1
Inequality (2.3) can be rewritten as
α1 +
m
2 γ1
β1 + γ1
>
α1 +
m
2 δ1
β1 + δ1
α1δ1 − α1γ1 +
m
2
γ1β1 −
m
2
β1δ1 > 0(
α1 −
m
2
β1
)
(δ1 − γ1) > 0
Since δ1 > γ1,it follows that α1 − m2 β1 > 0, but
α1−
m
2
β1 =
=
x1x2 − m2 x1 −
m
2 x2
x1
+
x2x3 − m2 x2 −
m
2 x3
x1x2
+
x3m− m2 x3 −
m
2 m
x1x2x3
− m
2
x1
≤ {inequality between arithmetic and geometric mean} ≤
≤
x1x2 −m
√
x1x2
x1
+
x2x3 −m
√
x2x3
x1x2
+
x3m−m
√
x3m
x1x2x3
− m
2
x1 ≤
≤ {m ≥
√
x1x2,
√
x2x3,
√
x3m} ≤ −
m
2
x1 ≤ 0,
which is a contradiction.
CASE 2: h (c1, . . . , ck3) < h (c1, c2)
D. Vukičević and T. Pisanski: On the extremal values of the ratios of number of paths 231
In this case h (c1, c2) > 0, hence f (c1, c2) > Ψ (m) ≥ gm (c1, c2,m) ,i. e.
c1c2
c1
c1 +
c1+c2
c1
>
c1c2
c1
+ c2mc1c2 +
m2
c1c2m
+ 1c1c2m ·
m2
m−1
c1 +
c1+c2
c1
+ c2+mc1c2 +
2m
c1c2m
+ 1c1c2m ·
2m
m−1
c2
c1 +
c1+c2
c1
>
c2 +
(
c2m
c1c2
+ 1c1c2 ·
m2
m−1
)
(
c1 +
c1+c2
c1
)
+
(
c2+m
c1c2
+ 1c1c2 ·
2m
m−1
) .
In order to obtain a contradiction, it is sufficient to prove that
c2m
c1c2
+ 1c1c2 ·
m2
m−1
c2+m
c1c2
+ 1c1c2 ·
2m
m−1
≥ c2
c1 +
c1+c2
c1
c2m+
m2
m−1
c2 +m+
2m
m−1
≥ c1c2
c21 + c1 + c2
Note that
c1c2
c21 + c1 + c2
≤
c1 · m2 + c2 ·
m
2
c21 + c1 + c2
≤ m
2
=
m2
m−1
2m
m−1
,
hence it is sufficient to prove that
c2m
c2 +m
≥ c1c2
c21 + c1 + c2
.
This is equivalent to c21c2m+ c
2
2m ≥ c1c22,which obviously holds. Hence, a contradiction
is obtained.
From Lemmas 2.7 and 2.11, our main result follows:
Theorem 2.12. Let ∆ ≥ 3, then
Φ32 (∆) = 2 ·Ψ (∆− 1)
This Theorem is very useful, because the number Ψ (∆− 1) can be determined in
∼ ∆2 operations. The program for calculating the function Ψ is produced and Table 1 of
values for Φ32 (∆) is obtained.
Remark 2.13. Note that X has ∼ ∆2 elements. However, we can restrict our search for
the maximum to only linear number of elements. Let Gm : [1,m]
3 → R be the function
defined by
Gm (x1, x2, x3) =
x1x2
x1
+ x2x3x1x2 +
x3m
x1x2x3
+ 1x1x2x3 ·
m2
m−1
x1 +
x1+x2
x1
+ x2+x3x1x2 +
x3+m
x1x2x3
+ 1x1x2x3 ·
2m
m−1
Let
h : [1,m]→ R
232 Ars Math. Contemp. 3 (2010) 215–235
∆ Φ32(∆) ∆ Φ32(∆) ∆ Φ32(∆) ∆ Φ32(∆) ∆ Φ32(∆)
1 Not def. 41 6.6904 81 9.3623 121 11.3872 161 13.0876
2 1.0000 42 6.7731 82 9.4180 122 11.4327 162 13.1281
3 1.5000 43 6.8571 83 9.4730 123 11.4779 163 13.1683
4 1.8750 44 6.9393 84 9.5273 124 11.5227 164 13.2083
5 2.1538 45 7.0195 85 9.5810 125 11.5671 165 13.2480
6 2.4074 46 7.0980 86 9.6339 126 11.6111 166 13.2875
7 2.6667 47 7.1747 87 9.6862 127 11.6547 167 13.3267
8 2.8913 48 7.2498 88 9.7379 128 11.6980 168 13.3657
9 3.0877 49 7.3232 89 9.7889 129 11.7410 169 13.4045
10 3.2609 50 7.3950 90 9.8442 130 11.7835 170 13.4430
11 3.4146 51 7.4653 91 9.9000 131 11.8258 171 13.4813
12 3.5794 52 7.5341 92 9.9552 132 11.8711 172 13.5193
13 3.7500 53 7.6015 93 10.0098 133 11.9167 173 13.5571
14 3.9080 54 7.6675 94 10.0638 134 11.9619 174 13.5947
15 4.0546 55 7.7321 95 10.1172 135 12.0068 175 13.6321
16 4.1912 56 7.8031 96 10.1701 136 12.0514 176 13.6692
17 4.3186 57 7.8750 97 10.2224 137 12.0957 177 13.7062
18 4.4378 58 7.9457 98 10.2741 138 12.1396 178 13.7429
19 4.5495 59 8.0151 99 10.3253 139 12.1832 179 13.7793
20 4.6730 60 8.0834 100 10.3760 140 12.2265 180 13.8156
21 4.8000 61 8.1505 101 10.4261 141 12.2695 181 13.8516
22 4.9211 62 8.2165 102 10.4757 142 12.3121 182 13.8900
23 5.0367 63 8.2813 103 10.5248 143 12.3545 183 13.9286
24 5.1472 64 8.3451 104 10.5734 144 12.3965 184 13.9669
25 5.2528 65 8.4079 105 10.6215 145 12.4383 185 14.0050
26 5.3540 66 8.4696 106 10.6691 146 12.4797 186 14.0430
27 5.4509 67 8.5304 107 10.7162 147 12.5209 187 14.0807
28 5.5439 68 8.5902 108 10.7629 148 12.5617 188 14.1182
29 5.6331 69 8.6490 109 10.8091 149 12.6023 189 14.1555
30 5.7322 70 8.7069 110 10.8589 150 12.6426 190 14.1927
31 5.8333 71 8.7639 111 10.9091 151 12.6825 191 14.2296
32 5.9313 72 8.8260 112 10.9588 152 12.7223 192 14.2663
33 6.0262 73 8.8889 113 11.0081 153 12.7617 193 14.3028
34 6.1182 74 8.9509 114 11.0570 154 12.8009 194 14.3392
35 6.2073 75 9.0120 115 11.1054 155 12.8397 195 14.3753
36 6.2939 76 9.0724 116 11.1534 156 12.8813 196 14.4112
37 6.3778 77 9.1319 117 11.2010 157 12.9231 197 14.4470
38 6.4594 78 9.1906 118 11.2481 158 12.9646 198 14.4826
39 6.5386 79 9.2486 119 11.2949 159 13.0058 199 14.5180
40 6.6156 80 9.3058 120 11.3412 160 13.0468 200 14.5532
Figure 1: Table of values for for Φ32 (∆).
D. Vukičević and T. Pisanski: On the extremal values of the ratios of number of paths 233
be any function. Denote by MaxInt (h) its maximum on the set {1, . . . ,m} . Let us observe
the following functions
hm : [1,m]→ R defined by hm (x1) = Gm (x1,m,m)
where m ∈ N\ {1} ;
hx1,m : [1,m]→ R defined by hx1,m (x2) = Gm (x1, x2,m)
where m ∈ N\ {1} , x1 ∈ N and x1 ≤ m;
hx1,x2,m : [1,m]→ R defined by hx1,x2,m (x3) = Gm (x1, x2, x2)
where m ∈ N\ {1} , x1, x2 ∈ N and x1, x2 ≤ m.
It can be easily seen that all of these functions are infinitely differentiable. Also, using
Mathematica, it can be verified that they have at most two stationary points (null-points of
the first derivation). Let h : [1,m]→ R be an infinitely derivable function:
1) with no stationary points - then MaxInt (h) = max {h (1) , h (m)} ;
2) with one stationary point x - then MaxInt (h) = max {h (1) , h (m) , h (bxc) , h (dxe)} ;
3) with two stationary points x and y - then
MaxInt (h) = max {h (1) , h (m) , h (bxc) , h (dxe) , h (byc) , h (dye)} .
Hence, in order to determine the Ψ (m) it is sufficient to check at most
6 ·
(
1 +
⌊
m3/2
m+ 1
⌋
+
⌊
m3/2
m+ 1
⌋2)
values, which can be done in linear time.
Remark 2.14. In order to prove that the function Φ32 is increasing, it is sufficient to show
that
x1x2
x1
+ x2x3x1x2 +
x3m
x1x2x3
+ 1x1x2x3 ·
m2
m−1
x1 +
x1+x2
x1
+ x2+x3x1x2 +
x3+m
x1x2x3
+ 1x1x2x3 ·
2m
m−1
≤
x1x2
x1
+ x2x3x1x2 +
x3(m+1)
x1x2x3
+ 1x1x2x3 ·
(m+1)2
m
x1 +
x1+x2
x1
+ x2+x3x1x2 +
x3+m+1
x1x2x3
+ 1x1x2x3 ·
2(m+1)
m
for every m ≥ 3 and x1, x2, x3 which maximizes gm. We need to prove that
x1x2
x1
+ x2x3x1x2 +
x3m
x1x2x3
+ 1x1x2x3 ·
m2
m−1
x1 +
x1+x2
x1
+ x2+x3x1x2 +
x3+m
x1x2x3
+ 1x1x2x3 ·
2m
m−1
≤
(
x1x2
x1
+ x2x3x1x2 +
x3m
x1x2x3
+ 1x1x2x3 ·
m2
m−1
)
+(
x1 +
x1+x2
x1
+ x2+x3x1x2 +
x3+m
x1x2x3
+ 1x1x2x3 ·
2m
m−1
)
+
+
(
x3
x1x2x3
+ 1x1x2x3 ·
(
(m+1)2
m −
m2
m−1
))
+
(
1
x1x2x3
+ 1x1x2x3 ·
(
2(m+1)
m −
2m
m−1
))
234 Ars Math. Contemp. 3 (2010) 215–235
It is sufficient to show that
x1x2
x1
+ x2x3x1x2 +
x3m
x1x2x3
+ 1x1x2x3 ·
m2
m−1
x1 +
x1+x2
x1
+ x2+x3x1x2 +
x3+m
x1x2x3
+ 1x1x2x3 ·
2m
m−1
≤
x3
x1x2x3
+ 1x1x2x3 ·
(
(m+1)2
m −
m2
m−1
)
1
x1x2x3
+ 1x1x2x3 ·
(
2(m+1)
m −
2m
m−1
)
x1x2
x1
+ x2x3x1x2 +
x3m
x1x2x3
+ 1x1x2x3 ·
m2
m−1
x1 +
x1+x2
x1
+ x2+x3x1x2 +
x3+m
x1x2x3
+ 1x1x2x3 ·
2m
m−1
≤
(
m2 −m
)
x3 +m
2 −m− 1
(m2 −m)− 2
.
From the proof of the Lemma 2.11, it follows that
x1x2
x1
+ x2x3x1x2 +
x3m
x1x2x3
+ 1x1x2x3 ·
m2
m−1
x1 +
x1+x2
x1
+ x2+x3x1x2 +
x3+m
x1x2x3
+ 1x1x2x3 ·
2m
m−1
≤ x3
and the claim follows.
The behavior of this function on its boundary is described by the following theorem:
Theorem 2.15. It holds that
lim
∆→∞
log Φ32 (∆)
log ∆
=
1
2
.
Proof. First, let us prove that lim∆→∞
log Φ32(∆)
log ∆ ≤
1
2 . We have:
lim
∆→∞
log Φ32 (∆)
log ∆
= lim
∆→∞
log (2 · Γ (∆− 1))
log ∆
≤ {from Lemma 2.8} ≤
≤ lim
∆→∞
log
(
2 · (∆−1)
3/2
∆
)
log ∆
≤ lim
∆→∞
(
log 2 + 12 log ∆
log ∆
)
=
1
2
.
Now, let us prove that lim∆→∞
log Φ32(∆)
log ∆ ≥
1
2 . We have:
lim
∆→∞
log Φ32 (∆)
log ∆
= lim
∆→∞
log (2 · Γ (∆− 1))
log ∆
≥ lim
∆→∞
log (2 ·Ψ (∆− 1))
log ∆
≥ lim
∆→∞
log
(
2 · g∆−1
(⌈√
∆− 1
⌉
,∆,∆
))
log ∆
= lim
∆→∞
log
(
2 ·
d√∆−1e·∆−1
d√∆−1e +
∆−1
d√∆−1e+
1
d√∆−1e+
1
d√∆−1e·(∆−2)
d√∆−1e+ d
√
∆−1e+∆−1
d√∆−1e +
2
d√∆−1e+
2
d√∆−1e·(∆−1) +
2
d√∆−1e·(∆−1)·(∆−1)
)
log ∆
≥ lim
∆→∞
log
(
2 · ∆−1
9d√∆−1e
)
log ∆
≥ lim
∆→∞
log
(
2
9 ·
√
∆− 1
)
log ∆
=
1
2
.
3 Acknowledgement
Partial support of Croatian Ministry of Science, Education and Sports is gratefully acknowl-
edged (grant no. 177–0000000-0884 and grant no. 037-0000000-2779). Help with English
language of Sarah Michelle Rajtmajer is also gratefully acknowledged.
D. Vukičević and T. Pisanski: On the extremal values of the ratios of number of paths 235
References
[1] M. Aouchiche, J. M. Bonnefoy, A. Fidahoussen, G. Caporossi, P. Hansen, P. L. Hiesse, J.
Lacheré and A. Monhait, Variable neighborhood search for extremal graphs 14, The Auto-
GraphiX 2 system, in: L. Liberti and N. Maculan (eds.), Global Optimization: From Theory to
Implementation, Springer, 2005.
[2] B. Bollobás, Extremal Graph Theory, Academic Press, London, 1978.
[3] I. Gutman and K. C. Das, The First Zagreb Index 30 Years After, MATCH – Commun. Math.
Comput. Chem. 50 (2004), 83–92.
[4] P. Hansen and D. Vukičević, Comparing the Zagreb Indices, Croatica Chemica Acta 80 (2007),
165–168.
[5] W. Imrich, Explicit Construction of Regular Graphs Without Small Cycles, Combinatorica 4
(1984), 53–39.
[6] S. Nikolić, G. Kovačević, A. Miličević and N. Trinajstić, The Zagreb Indices 30 Years After,
Croat. Chem. Acta 76 (2003), 113–124.
[7] R. Todeschini and V. Consonni, Handbook of Molecular Descriptors, Wiley-VCH, Weinheim,
2000.
[8] N. Trinajstić, Chemical Graph Theory, CRC Press, Boca Raton, 1992.
[9] D. Vukičević, Comparing variable Zagreb indices, MATCH – Commun. Math. Comput. Chem.
57 (2007), 633–641.
[10] D. Vukičević and A. Graovac, Comparing Zagreb M1 and M2 indices for acyclic molecules,
MATCH – Commun. Math. Comput. Chem. 57 (2007), 587–590.
[11] D. Vukičević and A. Graovac, Comparing variable Zagreb M1 and M2 indices for acyclic
molecules, MATCH – Commun. Math. Comput. Chem. 60 (2008), 37–44.