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 b∈Z+− {1}, associated to

a positive integer number n∈Z+, denoted for GPb(n), with set of vertices V={x}n

x=1 and

with set of edges:

E={{x, y} ∈ 2V:∃r∈Z+∪ {0}, such that |y−x|=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 N´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

b∈Z+− {1}, asociada a un entero n∈Z+, denotado por GPb(n), con conjunto de v´ertices

V={x}n

x=1 y conjunto de lados

E={{x, y} ∈ 2V:∃r∈Z+∪ {0}, tal que |y−x|=br},

y estudiamos algunas de sus propiedades, en especial para el caso b= 2.

Palabras y frases clave: Ciclo Hamiltoniano; Hamilton-conectividad; Panciclicidad.

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

Recibido 21/01/2021. Revisado 23/02/2021. Aceptado 30/05/2021.

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

x∈V(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Φxj∨iΨ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 b∈Z+− {1}, associated to a positive

integer number n∈Z+, denoted for GPb(n), with set of vertices V={x}n

x=1 and with set of

edges:

E={{x, y} ∈ 2V:∃r∈Z+∪ {0}, such that |y−x|=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 b∈Z+−{1}, for all n∈Z+and for all x∈V(GPb(n)), we have dGPb(n)(x) =

0, if n= 1 and for n > 1:

dGPb(n)(x) = (blog b(x−1)c+blog b(n−x)c+ 2,if 1< x < n

blog b(n−1)c+ 1,if x= 1,n.

Proof. Let b∈Z+−{1}and n∈Z+. If n= 1 then GPb(1) = K1, in consequence dGPb(1)(x) = 0,

for x∈V(GPb(1)). If n > 1, we have qn=blog b(n)c, with qn=max{i∈Z+∪ {0}/ b i≤n}

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 x∈V(GPb(n)), x= 1, n or x=h, l, indistinctly (see

Figure 1):

Figure 1: GPb(n),with qn=max{i∈Z+∪ {0}/ b i≤n}.

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

n−1, 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

qn−1,if n=bqn.

But for each b, n ∈Z+− {1},

blog b(n−1)c=(qn,if n>bqn

qn−1,if n=bqn.(1)

Therefore, dGPb(n)(x) = blog b(n−1)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

GPb(n), xis adjacent to

x−br,··· , 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 ≤x−brand bs+x≤n, we have dGPb(n)(x) = r+s+ 2, if

r=(qx,if x>bqx

qx−1,if x=bqx

and s=qn−x. But by equation 1, it follows that qx=max{i∈Z+∪ {0}/ b i≤x}, furthermore,

qn−x=max{i∈Z+∪{0}/ b i≤n−x}. Therefore, we obtain that dGPb(n)(x) = blog b(x−1)c+

blog b(n−x)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 b∈Z+− {1},for all n∈Z+and for all x∈V(GPb(n)), we have:

1. dGPb(n)(x) = dGPb(n)(n−x+ 1).

2. δ(GPb(n)) = dGPb(n)(1) = dGPb(n)(n).

3. ∆(GPc(n)) ≤ b2[log b(n−1

2) + 1]c, if n≥3.

Proof. (Numeral 1). Follows from Lemma 1.

(Numeral 2). Let b∈Z+−{1}. If n= 1 then GPb(1) = K1, in consequence dGPb(1)(x) = 0, for

x∈V(GPb(1)). Thus, δ(GPb(1)) = ∆(GPb(1)) = 0. Furthermore, if n= 2 then GPb(2) = K2,

therefore dGPb(2)(x) = 1, for all x∈V(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 b∈Z+− {1}.

If n≥3, 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 x∈V(GPb(n)). We consider two cases for x∈V(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(n−2)c+2 and

qn−1≤ blog b(n−2)c≤blog b(n−1)c ≤ qn. Therefore blog b(n−2)c+ 2 ≥ blog b(n−1)c+ 1 =

dGPb(n)(1) = dGPb(n)(n).

Case 2. If 3 ≤x≤ bn+1

2cand nis even, then 3 ≤x≤n

2=bn+1

2c, so that 3 ≤x≤n−x

and n−1≤(n−x)(x−1) (w, z ∈Zand 2 ≤w≤z⇒w+z≤wz), in consequence

log b(n−1) ≤log b(n−x) + log b(x−1).

If 3 ≤x≤ bn+1

2cand nis odd, then 3 ≤x≤n

2<bn+1

2c=n+1

2, in consequence we need to

prove, only that x=n+1

2implies log b(n−1) ≤log b(n−x) + log b(x−1). Indeed, if n= 2k+ 1,

with k∈Z+−{1}(3 ≤x≤n+1

2), then x=n+1

2=k+1 and as 2k≤k2,∀k∈Z+−{1}, similarity,

we obtain that n−1≤(n−x)(x−1). Therefore, log b(n−1) ≤log b(n−x) + log b(x−1).

Likewise, as bwc+bzc ≤ bw+zc ⇔ bw+zc+ 1 ≤ bwc+bzc+ 2,∀w, z ∈Rthen we have

blog b(n−1)c+1 ≤ blog b(x−1)c+blog b(n−x)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(3−1

2) + 1]c, for all b∈Z+−{1}.

If n= 4 then, by deﬁnition of GPb(n),

∆(GPb(4)) = 2log b4−1

2+ 1=(3,if b= 2

2,if b > 2.

If n≥5, we consider that the maximum of the function f(x) = log b(x−1)+log b(n−x)+2, in

the interval [2, n−1], is 2 log b(n−1

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(n−1

2) + 1]c.

We consider other interesting properties. For all b∈Z+− {1}and for all n∈Z+,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}}n−1

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 n≥3, b∈Z+−{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,∀a∈Z+), 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 a2a−1, ∀a∈Z+(sequence A003261, [9]).

Furthermore, for n∈Z+− {1}ﬁxed, if b→ ∞ then GPb(n)→HP n−1, this is, if b > n

implies that the graph GPb(n) is the Hamiltonian path HP with length n−1 (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 n≥3,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 n≥4. 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= 2i−1, yj= 2j,pk=k

2−par(k), qk=k

2−1, for k= 4,5,6, . . . , n, and par(h) =

1+(−1)h

2(parity of h∈Z). Therefore, we consider in GP2(n) the n−3 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 n≥3, 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 n≥3, 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 n∈Z+− {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 h−1 vertices of any elemental paths in GP2(h−1)

(GP2(h−1) ⊆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(h−1)),

and we consider four cases, for found the xy-elemental path, with length h, in GP2(h+ 1):

Case 1. If, simultaneously, v6=h−1, 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 h−1 :

vP w :v, ··· , h −1, h, ··· , w

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

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 h−1 (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=h−1 then y=h. Thus, we chosen the vw-Hamiltonian path in GP2(h−1)

(for 5 ≤h−1< h, we consider the inductive hypothesis), with v=h−1 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

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 n∈Z+− {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 n≥16, GP2(n) are examples of an inﬁnity

of Hamiltonian graphs, such that k

k+1 n≥n

2>∆(GP2(n)), with k∈Z+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(n−1) > n, for all integer n≥7 and 2n

2>(n−1)2, for all integer n≥16. 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 n≥16. Furthermore, by Lemma 1, Theorem 2 and the

inequalities shows above, we obtain that the sequence degree of GP2(n), for all integer n≥16, 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

qi≥di, for all i≤k, with k∈Z+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] Chv´atal, 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 C´alculo (7th ed.), Oxford University Press, M´exico, 1998.

[5] Lipschutz, S., Teor´ıa de Conjuntos y Temas Aﬁnes, McGraw-Hill/Interamericana de M´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: n∗2n+ 1, in :https://oeis.org/A002064(2012), consulted

20/11/2019, 00:14 a.m.

[9] Sloane, N., Woodall (or Riesel) numbers: n∗2n−1, 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