EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS
Vol. 12, No. 2, 2019, 499-505
ISSN 1307-5543 – www.ejpam.com
Published by New York Business Global

On Topologies Induced by Graphs Under Some Unary
and Binary Operations

Caen Grace S. Nianga1,∗, Sergio R. Canoy Jr.1

1 Department of Mathematics and Statistics, College of Science and Mathematics,
Center of Graph Theory, Algebra, and Analysis-PRISM, Mindanao State University-Iligan
Institute of Technology, 9200 Iligan City, Philippines

Abstract. Let G = (V (G), E(G)) be any simple undirected graph. The open hop neighborhood
of v ∈ V (G) is the set N2

G(v) = {u ∈ V (G) : dG(u, v) = 2}. Then G induces a topology τG on V (G)
with base consisting of sets of the form F 2

G[A] = V (G)\N2
G[A], where

N2
G[A] = A ∪ {v ∈ V (G) : N2

G(v) ∩ A 6= ∅} and A ranges over all subsets of V (G). In this
paper, we describe the topologies induced by the complement of a graph, the join, the corona, the
composition and the Cartesian product of graphs.

2010 Mathematics Subject Classifications: 05C76

Key Words and Phrases: Join, Corona, Lexicographic product, Cartesian product, Open hop
neighborhood

1. Introduction

Let G = (V (G), V (H)) be any simple undirected graph. The distance d(u, v) be-
tween two vertices u and v in G is the length of a shortest path joining u and v. Let
v ∈ V (G). The neighborhood of v is the set N(v) consisting of all u ∈ V (G) which are
adjacent with v and the closed neighborhood is N [v] = N(v) ∪ {v}. For any A ⊆ V (G),
N(A) = {x : xa ∈ E(G) for some a ∈ A} is called the neighborhood of A and
N [A] = N(A) ∪ A is called the closed neighborhood of A. Moreover, for each v ∈ V (G),
the open hop neighborhood of v is the set N2

G(v) = {u ∈ V (G) : dG(u, v) = 2} and the
closed hop neighborhood of v is the set N2

G[v] = {v} ∪ N2
G(v). Also, for any A ⊆ V (G),

N2
G(A) = {v ∈ V (G) : N2

G(v) ∩ A 6= ∅} is called the open hop neighborhood of A and the
set N2

G[A] = A ∪N2
G(A) is the called closed hop neighborhood of A. Denote by F 2

G[A] the
complement of N2

G[A], i.e., F 2
G[A] = V (G)\N2

G[A].
In 1983, Diesto and Gervacio in [5] proved that given a simple graphG = (V (G), E(G)),

G induces a topology on V (G), denoted by τG, with base consisting of sets of the form

∗Corresponding author.
DOI: https://doi.org/10.29020/nybg.ejpam.v12i2.3421

Email addresses: caengrace1997@gmail.com (C. Nianga),
sergio.canoy@g.msuiit.edu.ph (S. Canoy Jr.)

http://www.ejpam.com 499 c© 2019 EJPAM All rights reserved.



C. Nianga, S. Canoy / Eur. J. Pure Appl. Math, 12 (2) (2019), 499-505 500

FG(A) = V (G)\NG(A), where NG(A) = A ∪ {x : xa ∈ E for some a ∈ A} and A ranges
over all subsets of V (G). Their construction was further investigated in [2], [3] and [6]. In
particular, Canoy and Lemence in [2] described the topologies induced by the complement
of a graph, the join of graphs, composition and Cartesian product of graphs.

In [1], Canoy and Gimeno presented another way of constructing a topology τG from
a connected graph G by considering the family Ω(G) = {F 2

G[A] : A ⊆ V (G)} where
F 2
G[A] = {x ∈ V (G) : x /∈ A and dG(x, a) 6= 2 for all a ∈ A}. They showed that this family

is a base for some topology τG on V (G). This construction is also studied by Nianga et
al, in [4] for any graph G. It is also shown that the family BG = {F 2

G[A] : A ⊆ V (G)}
and SG = {F 2

G[v] : v ∈ V (G)} are, respectively, base and subbase for the topology τG on
V (G).

Concepts on Graph Theory and Topology are taken from [7] and [8], respectively.

2. Results

Definition 1. The complement of graph G, denoted by G is the graph with V (G) = V (G)
and uv ∈ E(G) if and only if uv /∈ E(G), where u, v ∈ V (G) = V (G).

Theorem 1. Let G be any graph and G its complement. Then for each v ∈ V (G),

F 2
G

[v] =


FG[v] ∪

 ⋂
u∈FG[v]

NG(u)

 , if FG[v] 6= ∅

NG(v), if FG[v] = ∅.

(1)

Proof. Let G be any graph and G its complement. Let v ∈ V (G) and set
A = ∩u∈FG[v]NG(u). Suppose FG[v] = ∅. Then NG(v) = V (G)\{v}. Hence, v is an isolated

vertex in G. Thus, F 2
G

[v] = NG(v). Suppose FG[v] 6= ∅. Let u ∈ FG[v]. Then u 6= v and

u /∈ NG(v). Hence, u 6= v and u ∈ NG(v). Thus, u ∈ F 2
G

[v]. Next, let w ∈ A. Then
w ∈ NG(u) for all u ∈ FG[v]. Since u /∈ NG(v), it follows that w 6= v. Also, w /∈ NG(u)
for all u ∈ NG(v). It implies that dG(w, v) 6= 2. Hence, w ∈ F 2

G
[v]. Consequently,

FG[v] ∪ [∩u∈FG[v]NG(u)] ⊆ F 2
G

[v]. Next, let x ∈ F 2
G

[v]. Then x 6= v and x /∈ N2
G

(v).
If x ∈ FG[v], then we are done. Suppose x /∈ FG[v]. Then x ∈ NG(v). Suppose
further that there exists u ∈ FG[v] such that x /∈ NG(u). Thus, u ∈ NG(v) and
x ∈ NG(u). Also, since x ∈ NG(v), x /∈ NG(v). Thus, dG(x, v) = 2, that is, x ∈ N2

G
(v), a

contradiction. Therefore, x ∈ NG(u) for all u ∈ FG[v]. This shows that x ∈ A.
Accordingly, F 2

G
[v] ⊆ FG[v] ∪ [∩u∈FG[v]NG(u)]. This establishes the desired equality.

Theorem 2. Let G be any graph and G its complement. If v is an isolated vertex of G
(or of G), then {v} ∈ τG ∩ τG.

Proof. Suppose v is an isolated vertex of G (or of G). Then
{v} = F 2

G[V (G)\{v}] = F 2
G[V (G)\{v}] and so, {v} ∈ BG and {v} ∈ BG. Thus, {v} ∈ τG

and {v} ∈ τG. Therefore, {v} ∈ τG ∩ τG.



C. Nianga, S. Canoy / Eur. J. Pure Appl. Math, 12 (2) (2019), 499-505 501

Remark 1. The converse of theorem 17 is not true.

Consider G = P5 = [a, b, c, d, e]. Then {e} = F 2
G[a, b] and {e} = FG[a, c]. However, e

is not an isolated vertex of G nor of G.

Definition 2. The join G1 + G2 of graphs G1 and G2 is the graph G with
V (G) = V (G1) ∪ V (G2) and

E(G) = E(G1) ∪ E(G2) ∪ {uv : u ∈ V (G1) and v ∈ V(G2)}.

Theorem 3. Let G = (V (G), E(G)) and H = (V (H), E(H)) be graphs and let
∅ 6= A ⊆ V (G) and ∅ 6= B ⊆ V (H). Then

(i) F 2
G+H [A] = V (H) ∪ [∩a∈ANG(a)] ;

(ii) F 2
G+H [B] = V (G) ∪ [∩b∈BNH(b)] and

(iii) F 2
G[∅] = V (G) ∪ V (H).

Proof. Let G = (V (G), E(G)) and H = (V (H), E(H)) be graphs. Let ∅ 6= A ⊆ V (G)
and ∅ 6= B ⊆ V (H).

(i) Note that

N2
G+H [A] = A ∪ {v ∈ V (G+H) : dG+H(v, a) = 2 for some a ∈ A}.

Since V (H) ⊆ NG+H(A),

N2
G+H [A] = A ∪ {v ∈ V (G) : dG+H(v, a) = 2 for some a ∈ A}

= A ∪ {v ∈ V (G) : dG(v, a) 6= 1 for some a ∈ A}.

Hence,
F 2
G+H [A] = V (H) ∪ [∩a∈ANG(a)] .

(ii) Similarly,
F 2
G+H [B] = V (G) ∪ [∩b∈BNH(b)] .

(iii) Clearly, F 2
G+H [∅] = V (G) ∪ V (H).

Remark 2. Let G be any graph and let A1, A2 ⊆ V (G). Then

N2
G[A1 ∪A2] = N2

G[A1] ∪N2
G[A2].

Theorem 4. Let G = (V (G), E(G)) and H = (V (H), E(H)) be graphs. Then for any
A ⊆ V (G+H) such that A ∩ V (G) = AG 6= ∅ and A ∩ V (H) = AH 6= ∅,

F 2
G+H [A] = F 2

G+H [AG] ∩ F 2
G+H [AH ].



C. Nianga, S. Canoy / Eur. J. Pure Appl. Math, 12 (2) (2019), 499-505 502

Proof. Let A ⊆ V (G + H). Suppose A ∩ V (G) = AG 6= ∅ and A ∩ V (H) = AH 6= ∅.
Then x ∈ F 2

G+H [A] if and only if x /∈ N2
G+H [A]. By Remark 2, x ∈ F 2

G+H [A] if and only
if x ∈ F 2

G+H [AG] ∩ F 2
G+H [AH ].

The next theorem follows from Theorem 3 (i) and (ii).

Corollary 1. Let G = (V (G), E(G)) and H = (V (H), E(H)) be graphs. Then for any
v ∈ V (G) ∪ V (H),

F 2
G+H [v] =

{
V (H) ∪NG(v), if v ∈ V (G)
V (G) ∪NG(v), if v ∈ V (H).

(2)

Definition 3. The corona G ◦H of graphs G and H is the graph obtained by taking one
copy of G and |V (G)| copies H and then forming the sum 〈v〉 + Hv = v + Hv for each
v ∈ V (G), where Hv is a copy of H corresponding to the vertex v.

Theorem 5. Let G = (V (G), E(G)) and H = (V (H), E(H)) be graphs. Then for any
a ∈ V (G ◦H),

F 2
G◦H [a] =


F 2
G[a] ∪

 ⋃
v∈V (G)\NG(a)

V (Hv)

 , if a ∈ V (G)

NHw(a) ∪ [V (G)\NG(w)] ∪

 ⋃
v∈V (G)\{w}

V (Hv)

 , if a ∈ V (Hw)

(3)

Proof. Let x ∈ F 2
G◦H [a]. Then x 6= a and x /∈ N2

G◦H(a). Consider the following cases:
Case 1. Suppose a ∈ V (G). If x ∈ V (G), then x /∈ N2

G(a) since x /∈ N2
G◦H(a). Hence,

x ∈ F 2
G[a]. Suppose x /∈ V (G). Let u ∈ V (G) such that x ∈ V (Hu). If u = a, then

x ∈ V (Hu) and u ∈ V (G)\NG(a). Suppose u 6= a. Since x /∈ N2
G(a) and dG◦H(a, y) = 2

for all y ∈ V (Hz) with z ∈ NG(a), it follows that u ∈ V (G)\NG(a). Thus,

F 2
G◦H [a] ⊆ F 2

G[a] ∪
[
∪v∈V (G)\NG(a)V (Hv)

]
= X.

Now, let w ∈ X. If w ∈ F 2
G[a], then w /∈ N2

G[a]. Hence, w /∈ N2
G◦H [a]. This implies that

w ∈ F 2
G◦H [a]. Suppose w ∈ ∪v∈V (G)\NG(a)V (Hv). Then there exists v ∈ V (G)\NG(a)

such that w ∈ V (Hv). It follows that w 6= a and dG◦H(w, a) 6= 2. Thus, w ∈ F 2
G◦H [a].

Therefore,
F 2
G[a] ∪

[
∪v∈V (G)\NG(a)V (Hv)

]
⊆ F 2

G◦H [a].

Case 2. Suppose a ∈ V (Hw) for some w ∈ V (G). If x = w, then x ∈ V (G)\NG(w).
Suppose x 6= w. If x ∈ V (G), then dG(x,w) 6= 1 because dG◦H(x, a) 6= 2. Hence,
x ∈ V (G)\NG(w). Suppose x ∈ V (Hq) for some q ∈ V (G). If q = w, then x ∈ V (Hw).
Since x 6= a and a ∈ V (Hw), x ∈ NHw(a) (otherwise, dG◦H(a, x) = 2). Suppose q 6= w.
Then x ∈ V (Hq) and q ∈ V (G)\{w}. Thus,

z ∈ NHw(a) ∪ [V (G)\NG(w)] ∪
[
∪v∈V (G)\{w}V (Hv)

]
= Y.



C. Nianga, S. Canoy / Eur. J. Pure Appl. Math, 12 (2) (2019), 499-505 503

Suppose now that p ∈ Y. If p ∈ NHw(a), then dG◦H(p, a) = dHw(p, a) = 1. Hence,
p ∈ F 2

G◦H [a]. If p ∈ V (G)\NG(w), then dG◦H(p, w) = dG(p, w) 6= 1. Hence, p 6= a and
dG◦H(a, p) 6= 2. This implies that p ∈ F 2

G◦H [a]. Finally, if p ∈ ∪v∈V (G)\{w}V (Hv), then
there exists r ∈ V (G)\{w} such that p ∈ V (Hr). Since

dG◦H(a, p) = dG◦H(a,w) + dG◦H(r, w) + dG◦H(r, p) = 2 + dG◦H(r, w) ≥ 3,

it follows that p ∈ F 2
G◦H [a]. Therefore,

NHw(a) ∪ [V (G)\NG(w)] ∪
[
∪v∈V (G)\{w}V (Hv)

]
⊆ F 2

G◦H [a].

Accordingly, the desired equality follows.

Definition 4. The lexicographic product (composition) of graphs G and H, denoted by
G[H], is the graph with V (G[H]) = V (G)×V (H) and (u, v)(u′, v′) ∈ E(G[H]) if and only
if either uu′ ∈ E(G) or u = u′ and vv′ ∈ E(H).

Theorem 6. Let G = (V (G), E(G)) and H = (V (H), E(H)) be any two graphs and let
(v, a) ∈ V (G[H]). Then

F 2
G[H][(v, a)] =

(
F 2
G[v]× V (H)

)
∪
(
{v} × F 2

H [a]
)
.

Proof. Note that (x, q) ∈ F 2
G[H][(v, a)] if and only if (x, q) 6= (v, a) and

dG[H]((x, q), (v, a)) 6= 2. Consider the following cases:
Case 1. Suppose x = v. Then q 6= a. Since

dG[H]((v, q), (v, a)) = dH(a, q) 6= 2, q ∈ F 2
H [a],

q ∈ F 2
H [a]. Hence, (x, q) ∈ {v} × F 2

H [a].
Case 2. Suppose x 6= v. Then

dG(x, v) = dG[H]((x, q), (v, a)) 6= 2.

Hence, x ∈ F 2
G[v] and (x, q) ∈ F 2

G[v]× V (H). Therefore,

F 2
G[H][(v, a)] ⊆

(
F 2
G[v]× V (H)

)
∪
(
{v} × F 2

H [a]
)
.

Next, let (w, p) ∈ F 2
G[v] × V (H). Then w ∈ F 2

G[v], that is, w 6= v and dG(w, v) 6= 2. It
follows that (w, p) 6= (v, a) and

dG[H]((w, p), (v, a)) = dG(w, v) 6= 2.

This shows that (w, p) ∈ F 2
G[H][(v, a)]. Hence, F 2

G[v] × V (H) ⊆ FG[H][(v, a)]. Finally,

let (z, t) ∈ {v} × F 2
H [a]. Then z = v and t ∈ F 2

H [a]. Hence, t 6= a and dH(a, t) 6= 2.
Consequently, (z, t) 6= (v, a) and

dG[H]((z, t), (v, a)) = dH(a, t) 6= 2,

showing that (z, t) ∈ F 2
G[H][a]. Thus, {v} × F 2

H [a] ⊆ F 2
G[H][(v, a)]. This establishes the

desired equality.



C. Nianga, S. Canoy / Eur. J. Pure Appl. Math, 12 (2) (2019), 499-505 504

Definition 5. The Cartesian Product of two graphs G1 and G2 denoted by G1�G2 is a
graph with V (G1�G2) = V (G1) × V (G2) and two vertices a = (u1, u2) and b = (v1, v2)
are adjacent in G1�G2 if and only if either u1 = v1 and u2v2 ∈ E(G2) or u2 = v2 and
u1v1 ∈ E(G1).

Theorem 7. Let K = G�H = (V (K), E(K)), where G = (V (G), E(G)) and
H = (V (H), E(H)). Then for each (v, a) ∈ V (K),

F 2
K [(v, a)] =

[
F 2
G[v]× {a}

]
∪
[
{v} × F 2

H [a]
]
∪ [FG[v]× V (H)\{a}] ∪ [NG(v)× FG[a]] .

Proof. Let (v, a) ∈ V (K) = V (G�H) and (x, q) ∈ F 2
K [(v, a)]. Then (v, a) 6= (x, q) and

dK((v, a), (x, q)) 6= 2. Now, consider the following cases:
Case 1. Assume that x = v. Then q 6= a and dH(q, a) = dK((x, q), (x, a)) 6= 2 and so,

q ∈ F 2
H [a]. Hence, (x, q) ∈ {v} × F 2

H [a].
Case 2. Assume that x 6= v.
Subcase 1. Let q = a. Then dG(x, v) = dK((x, q), (v, q)) 6= 2 and thus, x ∈ F 2

G[v]. It
follows that (x, q) ∈ F 2

G[v]× {a}.
Subcase 2. Let q 6= a. Suppose that x ∈ NG(v). If q ∈ NH(a), then

dK((x, q), (v, a)) = dG(x, v) + dH(q, a) = 2,

a contradiction. Thus, q ∈ V (H)\NH [a]. Hence, (x, q) ∈ NG(v) × FG[a]. Suppose
x /∈ NG(v). Then x ∈ FG[v]. Hence, (x, q) ∈ FG[v]× V (H)\{a}. Therefore,

F 2
K [(v, a)] ⊆

[
F 2
G[v]× {a}

]
∪
[
{v} × F 2

H [a]
]
∪ [FG[v]× V (H)\{a}] ∪ [NG(v)× FG[a]] .

Next, let (v, p) ∈ {v} × F 2
H [a]. Then p 6= a and dH(a, p) 6= 2. Hence, (v, p) 6= (v, a) and

dK((v, p), (v, a)) = dH(a, p) 6= 2, that is, (v, p) ∈ F 2
K [(v, a)]. If (x, a) ∈ F 2

G[v] × {a}, then
x 6= v and dG(x, v) 6= 2. Hence, (x, a) 6= (v, a) and dK((v, a), (x, a)) = dG(x, v) 6= 2, that
is, (x, a) ∈ F 2

K [(v, a)]. Now, (y, b) ∈ NG(v)× FH [a] implies dG(y, v) = 1 and dH(b, a) ≥ 2.
It follows that (y, b) 6= (v, a) and

dK((y, b), (v, a)) = dG(y, v) + dH(b, a) ≥ 3.

Hence, (y, b) ∈ F 2
K [(v, a)]. Finally, (z, t) ∈ [FG[v]× V (H)\{a}] implies dG(z, v) ≥ 2 and

dH(t, a) ≥ 1. This means that (z, t) 6= (v, a) and

dK((z, t), (v, a)) = dG(z, v) + dH(t, a) ≥ 3.

Thus, (z, t) ∈ F 2
K [(v, a)]. Therefore,[

F 2
G[v]× {a}

]
∪
[
{v} × F 2

H [a]
]
∪ [FG[v]× V (H)\{a}] ∪ [NG(v)× FG[a]] ⊆ F 2

K [(v, a)].

This establishes the desired equality.



REFERENCES 505

Acknowledgements

This research is funded by the Philippine Department of Science and Technology-
Accelerated Science and Technology Human Resource Development Program (DOST-
ASTHRDP) and Mindanao State University-Iligan Institute of Technology.

References

[1] S. Canoy and J. Gimeno. Which Connected Graphs Induce the Indiscrete and the
Discrete Topologies? Journal of Research in Science and Engineering, 1:17–19, 2004.

[2] S. Canoy and R. Lemence. Another Look at the Topologies Induced by Graphs. Ma-
timyas Matematika, 21:1–7, 1998.

[3] S. Canoy and R. Lemence. Topologies Induced by Some Special Graphs. Journal of
Mathematics, 2:45–50, 1999.

[4] S. Canoy and C. G. Nianga. On A Finite Topological Space Induced by Hop Neigh-
borhoods of a Graph. Advances and Applications in Discrete Mathematics, submitted.

[5] S. Diesto and S. Gervacio. Finite Topological Graphs. Journal of Research and Devel-
opment, MSU-IIT, 1:76–81, 1983.

[6] R. Guerrero and S. Gervacio. Characterization of Graphs which Induce the Discrete
and Indiscrete Topological Spaces. Matimyas Matematika, Special Issue, 1:11–15, 1989.

[7] F. Harary. Graph Theory. Addison-Wesley Publishing Company, USA, 1969.

[8] S. Lipschutz. General Topology, Schaum’s Outline Series. McGraw Hill International
Publishing Co., 1987.