Divulgaciones Matem´aticas Vol. 22, No. 1 (2021), pp. 31–39
The graph of a base power b, associated to a
positive integer number
El grafo potencia de base b, asociado a un entero positivo
Daniel Brito (danieljosb@gmail.com)
Oscar Castro (oscarecastrop@gmail.com)
Lope Mar´ın (lmata73@gmail.com)
Department of Mathematics, University of Oriente,
Cuman´a, Bolivarian Republic of Venezuela.
Abstract
Many concepts of Number Theory were used in Graph Theory and several types of graphs
have been introduced. We introduced the graph of a base power bZ+ {1}, associated to
a positive integer number nZ+, denoted for GPb(n), with set of vertices V={x}n
x=1 and
with set of edges:
E={{x, y} 2V:rZ+ {0}, such that |yx|=br},
and we study some of its properties, in special for case b= 2.
Key words and phrases: Hamiltonian Cycle; Hamilton-connectivity; Pancyclicity.
Resumen
Muchos conceptos de la Teor´ıa de umeros han sido utilizados en la Teor´ıa de Grafos y
distintos tipos de grafos se han introducido. Introducimos el grafo de una potencia de base
bZ+ {1}, asociada a un entero nZ+, denotado por GPb(n), con conjunto de ertices
V={x}n
E={{x, y} 2V:rZ+ {0}, tal que |yx|=br},
y estudiamos algunas de sus propiedades, en especial para el caso b= 2.
1 Introduction
Agraph Gconsist of a nonempty set V(G) of elements represented for points, called vertices
and a set E(G) of elements represented for lines segments with ends an unique pair of vertices,
this lines are called edges or sides and it is said that the pair of vertices are adjacent. A graph
MSC (2020): Primary 97N70, 05C45,; Secondary 05C38.
Autor de correspondencia: Oscar Castro
32 D. Brito - O. Castro - L. Mar´ın
without loops (there is no an edge with equal ends vertices) and without multiple edges (there
are no two or more edges with the same ends vertices) is called a simple graph. Two graph
are isomorphic if both graphs have same properties and diﬀerent graphics representation. Let
xV(G), the degree of x, denoted for dG(x), is the number of times that xis end of edges in
G. Thus, δ(G) and ∆(G) denote, respectively, the minimun degree and maximun degree of G. A
graph Gis complete if every two distinct vertices in Gare adjacent. A complete graph with n
vertices is denoted by Kn. A path is a subgraph Pof a graph G(graph with subsets of V(G) and
E(G), respectively) formed by an alternating succession of adjacent vertices, furthermore, Phas
an initial vertex and ﬁnal vertex, called extreme. A graph Gis called connected if there is a path
between any two distinct vertices in G. If there is no repetition of vertices in the path, it is said
to be an elemental path. Let Pbe the path between the vertices xand y, also denoted by xP y
or yP x indistinctly, but if we denoted xP +ywhen Pis traversed from xto ythen we denoted
xP ywhen Pis traversed from yto x. A Hamiltonian path of a graph is an elemental path
containing all the vertices of the graph. A cycle in a graph is an elemental path whose extreme
vertices are the same. A Hamiltonian cycle, in a graph, is a cycle that visits each vertex of the
graph. A Hamiltonian graph is a graph that contain a Hamiltonian cycle. A Hamilton-connected
graph is a graph that contains a Hamiltonian path between each pair of vertices. A pancyclic
graph is a graph that contains cycles of all the lengths, among 3 and n. In this paper only we
consider simple graphs and we refer the reader to [3] for the deﬁnitions not given here.
The motivation of this paper is related with the use of the concepts of Number Theory and
Graph Theory, to obtain other types of graphs as in [1] and [6]. We deﬁne a graph associated
to a positive integer number n, denoted by G(n), as a graph with set of vertices V={xk}n
k=1,
such that xkis a succession in Cnand set of side E={{xi, xj} 2V/xiΦxjiΨj}, with Φ, Ψ
relations between xiand xjin Vand between i,jin Z+, respectively, and 2 Vthe power set of V
[5]. In particular, we introduce the graph of a base power bZ+ {1}, associated to a positive
integer number nZ+, denoted for GPb(n), with set of vertices V={x}n
x=1 and with set of
edges:
E={{x, y} 2V:rZ+ {0}, such that |yx|=br},
and we characterized the degree for any vertex in GPb(n), the minimun degree and maximun
grade of GPb(n) in function of nand b, moreover, we study the Hamilton-connectivity and the
pancyclicity of GP2(n) and some other applications of the GPb(n) graph for case n= 2.
2 The graph of a power of a given base, associated to a
positive integer
Let dGPb(n)(x), δ(GPb(n)) and ∆(GPb(n)) be, respectively, the degree of xin GPb(n), the min-
imun degree and maximun degree of GPb(n).
Lemma 1. For all bZ+{1}, for all nZ+and for all xV(GPb(n)), we have dGPb(n)(x) =
0, if n= 1 and for n > 1:
dGPb(n)(x) = (blog b(x1)c+blog b(nx)c+ 2,if 1< x < n
blog b(n1)c+ 1,if x= 1,n.
Proof. Let bZ+{1}and nZ+. If n= 1 then GPb(1) = K1, in consequence dGPb(1)(x) = 0,
for xV(GPb(1)). If n > 1, we have qn=blog b(n)c, with qn=max{iZ+ {0}/ b in}
Divulgaciones Matem´aticas Vol. 22, No. 1 (2021), pp. 31–39
The graph of a base power b, associated... 33
and, moreover, we consider two cases for xV(GPb(n)), x= 1, n or x=h, l, indistinctly (see
Figure 1):
Figure 1: GPb(n),with qn=max{iZ+ {0}/ b in}.
Case 1. If x= 1, then by deﬁnition of GPb(n), xis adjacent
2, b + 1, b2+ 1,··· , b r+ 1
| {z }
r+1
or if x=n, then by deﬁnition of GPb(n), xis adjacent to
n1, n b, n b2,··· , n br
| {z }
r+1
.
Thus, as br+ 1 n, we have dGPb(n)(x) = r+ 1, if
r=(qn,if n>bqn
qn1,if n=bqn.
But for each b, n Z+ {1},
blog b(n1)c=(qn,if n>bqn
qn1,if n=bqn.(1)
Therefore, dGPb(n)(x) = blog b(n1)c+ 1, for x= 1, n.
Case 2. If x=hor x=l, indistinctly, then 1 < x < n (see Figure 1) and by deﬁnition of
xbr,··· , x b2, x b, x 1
| {z }
r+1
and to
1 + x, b +x, b2+x, ··· , b s+x
| {z }
s+1
.
Thus, as 1 xbrand bs+xn, we have dGPb(n)(x) = r+s+ 2, if
r=(qx,if x>bqx
qx1,if x=bqx
and s=qnx. But by equation 1, it follows that qx=max{iZ+ {0}/ b ix}, furthermore,
qnx=max{iZ+{0}/ b inx}. Therefore, we obtain that dGPb(n)(x) = blog b(x1)c+
blog b(nx)c+ 2.
Divulgaciones Matem´aticas Vol. 22, No. 1 (2021), pp. 31–39
34 D. Brito - O. Castro - L. Mar´ın
Theorem 1. For all bZ+ {1},for all nZ+and for all xV(GPb(n)), we have:
1. dGPb(n)(x) = dGPb(n)(nx+ 1).
2. δ(GPb(n)) = dGPb(n)(1) = dGPb(n)(n).
3. ∆(GPc(n)) b2[log b(n1
2) + 1]c, if n3.
Proof. (Numeral 1). Follows from Lemma 1.
(Numeral 2). Let bZ+{1}. If n= 1 then GPb(1) = K1, in consequence dGPb(1)(x) = 0, for
xV(GPb(1)). Thus, δ(GPb(1)) = ∆(GPb(1)) = 0. Furthermore, if n= 2 then GPb(2) = K2,
therefore dGPb(2)(x) = 1, for all xV(K2), in consequence δ(GPb(2)) = ∆(GPb(2)) = 1. This is,
δ(GPb(1)) = dGPb(1)(1) = 0 and δ(GPb(2)) = dGPb(2)(1) = dGPb(2)(2) = 1, for all bZ+ {1}.
If n3, by the proof of Numeral 1, is suﬃcient that 1 < x bn+1
2cfor prove that dGPb(n)(1) =
dGPb(n)(n)dGPb(n)(x), for all xV(GPb(n)). We consider two cases for xV(GPb(n)), x= 2
or 3 x bn+1
2c:
Case 1. If x= 2, by Lemma 1 and the equation 1, we have dGPb(n)(2) = blog b(n2)c+2 and
qn1 blog b(n2)c≤blog b(n1)c qn. Therefore blog b(n2)c+ 2 blog b(n1)c+ 1 =
dGPb(n)(1) = dGPb(n)(n).
Case 2. If 3 x bn+1
2cand nis even, then 3 xn
2=bn+1
2c, so that 3 xnx
and n1(nx)(x1) (w, z Zand 2 wzw+zwz), in consequence
log b(n1) log b(nx) + log b(x1).
If 3 x bn+1
2cand nis odd, then 3 xn
2<bn+1
2c=n+1
2, in consequence we need to
prove, only that x=n+1
2implies log b(n1) log b(nx) + log b(x1). Indeed, if n= 2k+ 1,
with kZ+{1}(3 xn+1
2), then x=n+1
2=k+1 and as 2kk2,kZ+{1}, similarity,
we obtain that n1(nx)(x1). Therefore, log b(n1) log b(nx) + log b(x1).
Likewise, as bwc+bzc bw+zc bw+zc+ 1 bwc+bzc+ 2,w, z Rthen we have
blog b(n1)c+1 blog b(x1)c+blog b(nx)c+2 . This is, dGPb(n)(1) = dGPb(n)(n)dGPb(n)(x),
if 3 x bn+1
2c(see Lemma 1).
(Numeral 3). If n= 3 we consider that ∆(K3) = 2 = b2[log b(31
2) + 1]c, for all bZ+{1}.
If n= 4 then, by deﬁnition of GPb(n),
∆(GPb(4)) = 2log b41
2+ 1=(3,if b= 2
2,if b > 2.
If n5, we consider that the maximum of the function f(x) = log b(x1)+log b(nx)+2, in
the interval [2, n1], is 2 log b(n1
2)+2 for x=n+1
2, (f(x) is continuous and diﬀerentiable function
in ]2, n 1[ and [2, n 1], respectively), whereby f(x) reach the maximum valor (Weierstrass’s
Extreme Valor Theorem and Critical Value of f[4]. Furthermore, we consider the proof of
Numeral 1 and the Lemma 1. Thus, we have ∆(GPb(n)) b2[log b(n1
2) + 1]c.
We consider other interesting properties. For all bZ+ {1}and for all nZ+,GPb(n)
GPb(n+ 1) (GPb(n) is subgraph of GPb(n+ 1)). Furthermore, GPb(n) contain a Hamiltonian
path, denoted by HP , such that for n > 1, E(HP ) = {{x, x + 1}}n1
x=1 . However, some graphs
of base power b, associated to a positive integer number n, no contain a Hamiltonian cycle, for
example GP3(9) contain a Hamiltonian path HP: 1,2,3,4,5,6,7,8,9 and no contain a Hamiltonian
cycle (see Figure 2).
Divulgaciones Matem´aticas Vol. 22, No. 1 (2021), pp. 31–39
The graph of a base power b, associated... 35
Figure 2: GP3(9).
Otherwise, if n=bs+br, with n3, bZ+{1},s, r Z+{0}and, without loss of gen-
erality, qn=r(see equation 1) then HC :n, HP , b r+1,1, HP +, b r, n is a Hamiltonian cycle in
GPb(n). For example GP3(12) contain a Hamiltonian cycle HC : 12,11,10,1,2,3,4,5,6,7,8,9,12,
because n= 12 = 3 + 32(see Figure 3).
Figure 3: GP3(12).
In consequence, for any B=bin Z+, if A=r=s= 2 or if A=b+ 1, with r=b+ 2
and s=b+ 1, then GPB(ABA) is Hamiltonian. This is, the GPb(2b2) and GPb((b+ 1)bb+1) are
Hamiltonian. Thus, there exists an inﬁnite subsuccession, in the ABA numbers sequence (have
the form aba,aZ+), associated to a Hamiltonian graph of a base power Bto a positive integer
number ABA. The ABA numbers, sequence A171607 in the OEIS (The On-Line Encyclopedia
of Integer Sequences) [7], is a generalization of the Cullen and Woodall numbers. The Cullen
numbers are given by the expression a2a+ 1, (sequence A002064 in the OEIS, [8]) and Woodall
numbers by a2a1, aZ+(sequence A003261, [9]).
Furthermore, for nZ+ {1}ﬁxed, if b then GPb(n)HP n1, this is, if b > n
implies that the graph GPb(n) is the Hamiltonian path HP with length n1 (Lemma 1 and the
proof of Numeral 1 in the Theorem 1). For example, for n = 4, see Figure 4.
Figure 4: b→∞⇒GPb(4) HP 3.
Also, thanks to the Lemma 1, we can obtain the degree sequence of any GPb(n). A non-
decreasing sequence ql, q2, . . . , qnof non-negative integers is the degree sequence or graphic se-
quence, if only if there is a graph Gwith nvertices xl, x2, . . . , xn, such that the dG(xi) = qifor
i= 1,2, . . . , n [2].
Divulgaciones Matem´aticas Vol. 22, No. 1 (2021), pp. 31–39
36 D. Brito - O. Castro - L. Mar´ın
3 The graph GP2(n)
In this section, we studied the graphs of base power 2, associated to a positive integer number n,
when are pancyclic, Hamiltonian and Hamilton-connected.
Theorem 2. For all integer n3,GP2(n)is pancyclic.
Proof. For n= 3, GP2(3) = K3, which is pancyclic (see Figure 5, below).
Figure 5: GP2(n), with n= 1,2,3,5.
Let n4. By deﬁnition of GP2(n),there is a Hamiltonian path, HP in GP2(n), with initial
vertex 1 and ﬁnal vertex n, its vertices set contain a consecutive positives integer succession.
Likewise, GP2(n) have sides {xi, xi+1}for i= 1,2,3, . . . , pkand {yj, yj+1}for j= 1,2,3, . . . , qk,
with xi= 2i1, yj= 2j,pk=k
2par(k), qk=k
21, for k= 4,5,6, . . . , n, and par(h) =
1+(1)h
2(parity of hZ). Therefore, we consider in GP2(n) the n3 cycles:
Ck:x1, x2,··· , xpk+1, yqk+1,··· , y2, y1, x1,
furthermore, we observe that V(Ck) = {xi}pk+1
i=1 {yj}qk+1
j=1 ,|V(Ck)|=kand as K3=GP2(3)
GP2(n), for all integer n3, GP2(n) also contain the cycle C3: 1,3,2,1, thus, we obtain GP2(n)
is pancyclic.
We observe that for k=n, in the proof of Theorem 2, GP2(n) contains a Hamiltonian cycle,
therefore, for all n3, GP2(n) is a Hamiltonian graph. For example, GP2(4) and GP2(5) are
isomorphic, respectively, to the graphs in Figure 6.
Figure 6: The isomorphic of GP2(n), with n= 4,5.
We observe the cycles in GP2(4):
C3: 1,3,2,1 C4: 1,3,4,2,1.
And observe the cycles in GP2(5):
Theorem 3. For all nZ+ {4},GP2(n)is Hamilton-connected.
Divulgaciones Matem´aticas Vol. 22, No. 1 (2021), pp. 31–39
The graph of a base power b, associated... 37
C3: 1,3,2,1 C4: 1,3,4,2,1 C5: 1,3,5,4,2,1.
Proof. For n= 1,2,3, follows from the deﬁnition of GP2(n), moreover, GP2(1), GP2(2) and
GP2(3) are isomorphic to the complete graph K1,K2and K3, respectively (see Figure 5,
further behind). Thus, for n > 4 we apply induction over n.
If n= 5, we consider the elemental paths in GP2(5) (observing Figure 6):
HP 4: 1,2,3,4,5 2P5: 2,1,3,4,5 3P5: 3,1,2,4,5 4P5: 4,3,2,1,5
1P4: 1,2,3,5,4 2P4: 2,1,3,5,4 3P4: 3,2,1,5,4
1P3: 1,2,4,5,3 2P3: 2,1,5,4,3
1P2: 1,3,5,4,2
Then, GP2(5) is Hamilton-connected.
If n= 6 (see Figure 7), we consider four cases, based in the construction of the Hamiltonian
paths in GP2(5):
Figure 7: GP2(6).
Case 1. The elemental paths in GP2(6), expanding the Hamiltonian paths in GP2(5) deﬁne
previously:
1P5: 1,2,3,4,6,5 2P5: 2,1,3,4,6,5 3P5: 3,1,2,4,6,5
1P4: 1,2,3,5,6,4 2P4: 2,1,3,5,6,4 3P4: 3,2,1,5,6,4
1P3: 1,2,4,6,5,3 2P3: 2,1,5,6,4,3
1P2: 1,3,5,6,4,2
Case 2. For the Hamiltonian paths HP 5, 2P6, 3P6, 4P6 and 5P6 in GP2(6), we extend the
Hamiltonian paths in GP2(5) to:
HP 5: 1,2,3,4,5,62P6: 2,1,3,4,5,63P6: 3,1,2,4,5,64P6: 4,3,2,1,5,6
Case 3. For the Hamiltonian path 4P5 in GP2(6) , we extend the Hamiltonian path 4P2 in
GP2(4) (see Figure 6), therefore 4P5 : 4,3,1,2,6,5.
Case 4. For the Hamiltonian path 5P6 in GP2(6) , we extend the Hamiltonian path 2P5 in
GP2(5) (see Figure 6), therefore 5P6 : 5,4,3,1,2,6.
Thus, GP2(6) is Hamilton-connected.
Successively, by construction, from the Hamiltonian paths in GP2(5), suppose that theorem
is true for 6 n=h(inductive hypothesis: GP2(h) is Hamilton-connected), we will demonstrate
that GP2(h+ 1) is Hamilton-connected:
Divulgaciones Matem´aticas Vol. 22, No. 1 (2021), pp. 31–39
38 D. Brito - O. Castro - L. Mar´ın
If we consider n=h+ 1, all elemental paths in GP2(h+ 1), with length h, contain hvertices
of any elemental paths in GP2(h) and contain h1 vertices of any elemental paths in GP2(h1)
(GP2(h1) GP2(h)GP2(h+ 1)). Therefore, for x, y V(GP2(h+ 1)) diﬀerent, without
loss of generality, suppose x<y, we chosen the vw-elemental path in GP2(h) (or in GP2(h1)),
and we consider four cases, for found the xy-elemental path, with length h, in GP2(h+ 1):
Case 1. If, simultaneously, v6=h1, w6=hand x, y 6=h+ 1, then by construction, from
the Hamiltonian paths in GP2(5) until GP2(h), in GP2(h), we obtain the elemental paths with
length h1 :
vP w :v, ··· , h 1, h, ··· , w
or
vP w :v, ··· , h, h 1,··· , w
which are expanded, respectively, to the elemental paths in GP2(h+ 1), with length h:
xP y :v, ··· , h 1,h + 1, h, ··· , w
or
xP y :v, ··· , h, h + 1, h 1,··· , w.
Case 2. Let v=x, if w=hthen y=h+ 1, so that, in GP2(h), we obtain the elemental
path, with length h1 (inductive hypothesis):
vP w :v, ··· , w.
which is extended to, the path in GP2(h+ 1), with length h:
xP y :v, ··· , w, h + 1.
Case 3. If x=h1 then y=h. Thus, we chosen the vw-Hamiltonian path in GP2(h1)
(for 5 h1< h, we consider the inductive hypothesis), with v=h1 and w=h+ 1 2rfor
r > 1, and we obtain the elemental path, with length h:
xP y :v, ··· , w, h + 1,h.
Case 4. If x=hand y=h+ 1, we chosen the vw- Hamiltonian path in GP2(h), with v=h
and w=h+ 1 2rfor r > 1 (inductive hypothesis), we obtain the elemental path, with length
h:
xP y :v, ··· , w, h + 1.
Finally, if n= 4, we observe in the Figure 6 above, that in GP2(4) does not exists a Hamil-
tonian path 2P3, in consequence GP2(n) is Hamilton-connected for all nZ+ {4}.
We observe that the graph GP2(n) has interesting properties obtained by construction, with-
out the need for many conditions.
Given Theorem 2 and Theorem 3, for any integer n16, GP2(n) are examples of an inﬁnity
of Hamiltonian graphs, such that k
k+1 nn
2>∆(GP2(n)), with kZ+or n > 2∆(GP2(n))
dGP2(n)(x) + dGP2(n)(y) for any x, y V(GP2(n)). In all cases, we consider Lemma 1, Theorem 1
and 4
2(n1) > n, for all integer n7 and 2n
2>(n1)2, for all integer n16. In consequence,
the hypothesis of Seymour’s Conjecture, of Dirac’s Theorem and of Ore’s Theorem (see [3]) are
Divulgaciones Matem´aticas Vol. 22, No. 1 (2021), pp. 31–39
The graph of a base power b, associated... 39
no necessary for the graph GP2(n) with n16. Furthermore, by Lemma 1, Theorem 2 and the
inequalities shows above, we obtain that the sequence degree of GP2(n), for all integer n16, no
satisﬁes the hypothesis of Chv´atal’s Theorem [2]. In consequence, {GP2(n)}
n=16 is a succession
of Hamiltonian graphs whose degree sequence is majorized by a graphic sequence which is not
forcibly Hamiltonian. A sequence q1, q2, . . . , qkmajorizes a sequence d1, d2, . . . , dkif and only if
qidi, for all ik, with kZ+and a graphic sequence is forcibly Hamiltonian, if and only if
every graph with this degree sequence is Hamiltonian [2].
Finally, thanks to GP2(n), we show that any sequence of consecutive positive integers, {n}m
n=1,
is associated, simultaneously, to a nontrivial pancyclic (Hamiltonian) and Hamilton-connected
graph.
References
[1] Abawajy, J., Kelarev, A. and Chowdhury, M., Power Graphs: A Survey, Electronic Journal
of Graph Theory and Applications, 1(2)(2013), 125-147.
[2] Chatal, V., On Hamilton’s Ideal, Journal of Combinatorial Theory, 12(B)(1972), 163–168.
[3] Diestel, R., Graph Theory (2th ed.), Springer, New York, 2000.
[4] Leithold, L., El alculo (7th ed.), Oxford University Press, exico, 1998.
[5] Lipschutz, S., Teor´ıa de Conjuntos y Temas Aﬁnes, McGraw-Hill/Interamericana de exico
S. A. de C.V., M´exico, 1994.
[6] Mukherjee, H., Hamiltonicity of the Power Graph of Abelian Groups, in :https://arxiv.
org/pdf/1505.00584(2017), consulted 05/07/2017, 01:25 a.m.
[7] Munafo, R., Expressible as A*BAin a nontrivial way, in: https://oeis.org/
A171607(2009) consulted 20/11/2019, 02:14 a.m.
[8] Sloane, N., Cullen numbers: n2n+ 1, in :https://oeis.org/A002064(2012), consulted
20/11/2019, 00:14 a.m.
[9] Sloane, N., Woodall (or Riesel) numbers: n2n1, in: https://oeis.org/A003261(2012),
consulted 20/11/2019, 01:05 a.m.
Divulgaciones Matem´aticas Vol. 22, No. 1 (2021), pp. 31–39