ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 20 (2021) 275–288
https://doi.org/10.26493/1855-3974.2229.5f1
(Also available at http://amc-journal.eu)
Boundary-type sets of strong product
of directed graphs*
Bijo S. Anand
Department of Mathematics, Sree Narayana College, Punalur, Kollam, India-691305
Manoj Changat
Department of Futures Studies, University of Kerala, Trivandrum, India-695581
Prasanth G. Narasimha-Shenoi † , Mary Shalet Thottungal Joseph ‡
Department of Mathematics, Government College Chittur, Palakkad, India-678104
Received 26 January 2020, accepted 8 March 2021, published online 18 November 2021
Abstract
Let D = (V,E) be a strongly connected digraph and let u and v be two vertices in
D. The maximum distance md(u, v) is defined as md(u, v) = max{d⃗(u, v), d⃗(v, u)},
where d⃗(u, v) denotes the length of a shortest directed u-v path in D. This is a metric. The
boundary, contour, eccentricity and periphery sets of a strongly connected digraph D with
respect to this metric have been defined. The boundary-type sets of the strong product of
two digraphs is investigated in this article.
Keywords: Maximum distance, boundary-type sets, strongly connected digraph, strong product.
Math. Subj. Class. (2020): 05C12, 05C20, 05C76
*The authors thank the anonymous referees for their valuable suggestions, which helped improve this article.
†Supported by Science and Engineering Research Board, a statutory body of Government of India under
their Extra Mural Research Funding No. EMR/2015/002183 and MATRICS Scheme No. MTR/2018/000012.
Supported by Kerala State Council for Science Technology and Environment of Government of Kerala under
their SARD project grant Council(P) No. 436/2014/KSCSTE.
‡Corresponding author. Supported by Science and Engineering Research Board, a statutory body of Gov-
ernment of India under their Extra Mural Research Funding No. EMR/2015/002183. Supported by Kerala State
Council for Science Technology and Environment of Government of Kerala under their SARD project grant Coun-
cil(P) No. 436/2014/KSCSTE.
E-mail addresses: bijos_anand@yahoo.com (Bijo S. Anand), mchangat@keralauniversity.ac.in (Manoj
Changat), prasanthgns@gmail.com (Prasanth G. Narasimha-Shenoi), mary_shallet@yahoo.co.in (Mary Shalet
Thottungal Joseph)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
276 Ars Math. Contemp. 20 (2021) 275–288
1 Introduction
Directed graphs or in short digraphs have immense applications in almost all areas of sci-
ence and even in sociology. A directed network is a network in which each edge has a
direction, pointing from one vertex to another. They can be represented as directed graphs.
Road traffic networks are the most frequently met examples of one-way networks. A
two-way street is one in which vehicles are allowed to travel in both directions. The advan-
tages of a one-way street network over a two-way street pattern are discussed in [14]. But
when one-way traffic is introduced in a two-way network, the distance between places in
one of the directions may increase. So the problem of designing a network is to minimize
the distance between places and the cost of construction.
The one-way problem was first studied by Robbins [13]. It finds applications in various
fields like computer science, biology, etc. In [2], directed graphs are used to analyze the
local properties of internet connectivity. Neurons are connected in intricate communication
networks established during development to convey sensory information from peripheral
receptors of sensory neurons to the central nervous system and to convey commands from
the central nervous system to effector organs [12].
The boundary-type sets of a graph, the boundary, contour, eccentricity, and periph-
ery sets of a graph were studied in [5] and [7]. It is very difficult to identify the various
boundary-type sets in large networks. So we try to decompose the network into smaller
networks and identify the boundary-type sets. The four standard graph products, namely
Cartesian, direct, strong, and lexicographic products can be extended to digraphs as well.
Marc Hellmuth and Tilen Marc developed a polynomial-time algorithm for determining the
prime factor decomposition of strong product of digraphs [11].
The directed distance defined in digraphs is generally not a metric. As we are concerned
with the problem of designing the network to minimize the distance between places at a
minimum cost, we consider the distance maximum distance or in short, m-distance which
is a metric that was introduced by Chartrand and Tian in [8]. It gives the maximum of the
directed distances in either direction and is denoted by md(u, v). So minimizing md(u, v)
results in minimizing the distance between the nodes in both directions. An undirected
graph G can be identified as a symmetric digraph, that is, one for which (u, v) ∈ E(G) if
and only if (v, u) ∈ E(G), and the metric md is the usual distance metric in undirected
graphs.
The boundary-type sets of the Cartesian product of two digraphs were studied in [6]. In
this paper, a similar study is conducted for the strong product of digraphs.
2 Preliminaries
A directed graph or a digraph D consists of a non-empty finite set V (D) of elements called
vertices and a finite set E(D) of ordered pairs of distinct vertices called arcs or edges [1].
We call V (D) the vertex set and E(D) the edge set of D. We write D = (V,E) to denote
the digraph D with vertex set V and edge set E. For an edge (u, v), the first vertex u of
the ordered pair is the tail of the edge and the second vertex v is the head; together they
are the endpoints. This definition of a digraph does not allow loops (edges whose head and
tail coincide) or parallel edges (pairs of edges with the same tail and the same head). The
underlying graph UD of a digraph D is the simple graph with the vertex set V (D) and the
unordered pair (x, y) ∈ E(UD) if and only if either (x, y) ∈ E(D) or (y, x) ∈ E(D).
The following concepts are taken from [1].
B. S. Anand et al.: Boundary-type sets of strong product of directed graphs 277
For a vertex v in a digraph D = (V,E), the neighborhoods are defined as follows:
N+D (v) = {w ∈ V : (v, w) ∈ E}, N
−
D (v) = {u ∈ V : (u, v) ∈ E}.
The sets N+D (v), N
−
D (v), and ND(v) = N
+
D (v)∪N
−
D (v) are called the out-neighborhood,
in-neighborhood, and neighborhood of v. These neighborhoods are called open neighbor-
hoods of v. Similarly, we can define closed neighborhoods of v (neighbors including v).
The closed neighborhood of v is denoted by ND[v]. That is, ND[v] = ND(v) ∪ {v}.
A directed path is a directed graph with V (P ) ̸= ∅ with distinct vertices u1, u2, . . . , uk
and edges e1, e2, . . . , ek−1 such that ei is an edge directed from ui to ui+1 for 1 ≤ i ≤
k − 1. In this article, a path will always mean a ‘directed path’. A digraph is strongly
connected or strong if, for each ordered pair (u, v) of vertices, there is a path from u to v.
A digraph is weakly connected if its underlying graph is connected. A strong component of
a digraph D is a maximal induced subdigraph of D which is strong. If D1, D2, . . . , Dt are
the strong components of D, then V (D1) ∪ V (D2) ∪ · · · ∪ V (Dt) = V (D) and V (Di) ∩
V (Dj) = ∅ for every i ̸= j.
The length of a path is the number of edges in the path. The directed distance d⃗(u, v)
between two vertices u, v ∈ V (D) is the length of the shortest directed path from u to
v, or infinity if no such path exists. Note that this distance is not a metric, as generally
d⃗(u, v) ̸= d⃗(v, u).
So in [8], Chartrand and Tian introduced two other distances between the vertices u and
v in a strong digraph, namely the maximum distance md(u, v) = max{d⃗(u, v), d⃗(v, u)}
and the sum distance sd(u, v) = d⃗(u, v)+d⃗(v, u), both of which are metrics. In this article,
we deal with the maximum distance, md .
Remark 2.1. md(u, v) is denoted by d(u, v) hereafter.
The m-eccentricity of a vertex v, the m-radius and the m-diameter of a digraph D
are also defined in [8]. Consistent with our notation d(u, v) for maximum distance be-
tween the vertices u and v, we denote them respectively as ecc(v), rad(D), and diam(D).
Thus, ecc(v) = maxu∈V (D) d(v, u), rad(D) = minv∈V (D) ecc(v), and diam(D) =
maxv∈V (D) ecc(v), where ecc(v) denotes m-eccentricity of v.
If a digraph D is strongly connected, then the maximum distance between every pair
of vertices is finite, and hence the m-eccentricity of every vertex in D is finite. Otherwise,
D has more than one strong component, and the maximum distance between two vertices
lying in different strong components of D is infinity. So if D is not strongly connected,
then the m-eccentricity of every vertex in D is infinity.
2.1 Definitions of boundary-type sets
We define the boundary-type sets of a digraph D with respect to the metric maximum
distance. Most of the following definitions are analogous to the definitions in [7]. Let D
be a strong digraph and u, v ∈ V (D). The vertex v is said to be a boundary vertex of u if
no neighbor of v is further away from u than v. Hereafter, we denote ND(v) and ND[v] by
N(v) and N [v], respectively.
A vertex v is called a boundary vertex of D if it is the boundary vertex of some vertex
u ∈ V (D).
Definition 2.2. The boundary ∂(D) of D is the set of all of its boundary vertices
∂(D) = {v ∈ V (D) : ∃u ∈ V (D) such that ∀w ∈ N(v), d(u,w) ≤ d(u, v)}.
278 Ars Math. Contemp. 20 (2021) 275–288
Given u, v ∈ V (D), the vertex v is called an eccentric vertex of u if no vertex in V (D)
is further away from u than v; that is, if d(u, v) = ecc(u). A vertex v is called an eccentric
vertex of digraph D if it is the eccentric vertex of some vertex u ∈ V (D).
Definition 2.3. The eccentricity Ecc(D) of a digraph D is the set of all of its eccentric
vertices
Ecc(D) = {v ∈ V (D) : ∃u ∈ V (D) such that ecc(u) = d(u, v)}.
In a similar way, we can define the eccentricity of any proper subset W of the vertex
set V (D):
Ecc(W ) = {v ∈ V (D) : ∃u ∈ W such that ecc(u) = d(u, v)}.
A vertex v ∈ V (D) is called a peripheral vertex of D if no vertex in V (D) has an
eccentricity greater than ecc(v); that is, if the eccentricity of v is equal to the diameter
diam(D) of D.
Definition 2.4. The periphery Per(D) of a digraph D is the set of all of its peripheral
vertices
Per(D) = {v ∈ V (D) : ecc(u) ≤ ecc(v),∀u ∈ V (D)}
= {v ∈ V (D) : ecc(v) = diam(D)}.
A vertex v ∈ V (D) is called a contour vertex of digraph D if no neighbor vertex of v
has an eccentricity greater than ecc(v). The following definition is from [5].
Definition 2.5. The contour Ct(D) of a digraph D is the set of all of its contour vertices
Ct(D) = {v ∈ V (D) : ecc(u) ≤ ecc(v),∀u ∈ N(v)}.
As in the case of undirected graphs [3] we have,
1. Per(D) ⊆ Ct(D) ∩ Ecc(D),
2. Ecc(D) ∪ Ct(D) ⊆ ∂(D).
This is because a peripheral vertex is a vertex having the maximum eccentricity in the
digraph D and so every peripheral vertex in D is a contour vertex in D as well as the
eccentric vertex of a diametrical vertex in D.
If v is an eccentric vertex of a vertex u, then v is a boundary vertex of u. Also if v
is a contour vertex, then ecc(u) ≤ ecc(v) for all u ∈ N(v). So there exists some vertex
w ∈ V (D) such that d(w, u) ≤ d(w, v) for all u ∈ N(v), and hence v is a boundary vertex
of w.
The open neighborhood N(v) can be replaced by the closed neighborhood N [v] in the
definitions of the boundary and the contour sets. This does not affect the definitions and
is necessary for proving the relationship between the boundary and the contour sets of the
strong product of two digraphs and its factors.
B. S. Anand et al.: Boundary-type sets of strong product of directed graphs 279
3 Strong product of directed graphs
The strong product D1 ⊠ D2 of two digraphs D1 and D2 with vertex sets V (D1) =
{u1, u2, . . . , um} and V (D2) = {v1, v2, . . . , vn} is the digraph having the vertex set
V (D1) × V (D2) and with arc set E(D1 ⊠ D2) defined as follows. A vertex (ui, vr) is
adjacent to (uj , vs) in D1 ⊠D2 if either
1. (ui, uj) ∈ E(D1), vr = vs, or
2. ui = uj , (vr, vs) ∈ E(D2), or
3. (ui, uj) ∈ E(D1), (vr, vs) ∈ E(D2).
The strong product of digraphs is commutative [10]. The distance between two vertices
(g, h) and (g′, h′) in the strong product G ⊠ H of two graphs G and H is given in [9] as
follows:
dG⊠H((g, h), (g
′, h′)) = max{dG(g, g′), dH(h, h′)}.
So in the case of two digraphs D1 and D2, it follows that the directed distance
d⃗D1⊠D2((ui, vr), (uj , vs)) = max{d⃗D1(ui, uj), d⃗D2(vr, vs)}.
Lemma 3.1. Let D1 and D2 be two strongly connected digraphs. Then
dD1⊠D2((ui, vr), (uj , vs)) = max{dD1(ui, uj), dD2(vr, vs)},
eccD1⊠D2(ui, vr) = max{eccD1(ui), eccD2(vr)}.
Proof.
dD1⊠D2((ui, vr), (uj , vs))
= max{d⃗D1⊠D2((ui, vr), (uj , vs)), d⃗D1⊠D2((uj , vs), (ui, vr))}
= max{max{d⃗D1(ui, uj), d⃗D2(vr, vs)},max{d⃗D1(uj , ui), d⃗D2(vs, vr)}}
= max{max{d⃗D1(ui, uj), d⃗D2(vr, vs), d⃗D1(uj , ui), d⃗D2(vs, vr)}}
= max{max{d⃗D1(ui, uj), d⃗D1(uj , ui)},max{d⃗D2(vr, vs), d⃗D2(vs, vr)}}
= max{dD1(ui, uj), dD2(vr, vs)}.
Hence it follows that
eccD1⊠D2(ui, vr)
= max{dD1⊠D2((ui, vr), (uj , vs)) : (uj , vs) ∈ V (D1 ⊠D2)}
= max{max{dD1(ui, uj), dD2(vr, vs)} : uj ∈ V (D1), vs ∈ V (D2)}
= max{max{dD1(ui, uj) : uj ∈ V (D1)},max{dD2(vr, vs) : vs ∈ V (D2)}}
= max{eccD1(ui), eccD2(vr)}.
Corollary 3.2. Let D1 and D2 be two strongly connected digraphs. Then
rad(D1 ⊠D2) = max{rad(D1), rad(D2)},
diam(D1 ⊠D2) = max{diam(D1),diam(D2)}.
280 Ars Math. Contemp. 20 (2021) 275–288
Proof.
rad(D1 ⊠D2) = min
(ui,vr)∈V (D1⊠D2)
ecc(ui, vr)
= min
ui∈V (D1)
vr∈V (D2)
max{eccD1(ui), eccD2(vr)}
= max{ min
ui∈V (D1)
ecc(ui), min
vr∈V (D2)
ecc(vr)}
= max{rad(D1), rad(D2)},
diam(D1 ⊠D2) = max
(ui,vr)∈V (D1⊠D2)
ecc(ui, vr)
= max
ui∈V (D1)
vr∈V (D2)
max{eccD1(ui), eccD2(vr)}
= max{ max
ui∈V (D1)
ecc(ui), max
vr∈V (D2)
ecc(vr)}
= max{diam(D1),diam(D2)}.
The strong product of two directed graphs is strongly connected if and only if both
the digraphs are strongly connected [9]. Also if G and H are two undirected graphs,
NG⊠H [(g, h)] = NG[g]×NH [h] [9]. Since the neigbors of a vertex in a directed graph are
exactly its neighbors in the underlying graph, it follows that
ND1⊠D2 [(ui, vr)] = NG⊠H [(ui, vr)] = NG[ui]×NH [vr] = ND1 [ui]×ND2 [vr],
where G and H are the underlying graphs of D1 and D2, respectively. In [4], Cáceres
et al. presented a description of the boundary-type sets of two undirected graphs and the
description of the boundary is as follows.
For two graphs G and H , ∂(G ⊠H) = (∂(G) × V (H)) ∪ (V (G) × ∂(H)). But this
result does not hold in the case of directed graphs.
Consider the strong product, D1 ⊠ D2 of the digraphs D1 and D2 in Figure 1. The
eccentricity of each vertex is displayed near the vertex in red color.
Per(D1) = Ecc(D1) = Ct(D1) = {u1, u4},
Per(D2) = Ecc(D2) = Ct(D2) = {v1, v2}, and
Per(D1 ⊠D2) = Ecc(D1 ⊠D2) = Ct(D1 ⊠D2)
= {(u1, v1), (u4, v1), (u1, v2), (u4, v2)}.
∂(D1) = {u1, u4},
∂(D2) = {v1, v2}, and
∂(D1 ⊠D2) = {(u1, v1), (u4, v1), (u1, v2), (u4, v2)}.
The reason for (u2, v1), (u2, v2), (u3, v1), (u3, v2) /∈ ∂(D1 ⊠ D2) is explained after the
proof of Theorem 3.3.
Now we present the results concerning the boundary-type sets of the strong product of
two strongly connected digraphs. In all these results, D1 and D2 can be interchanged due
to the commutativity of strong product of digraphs.
B. S. Anand et al.: Boundary-type sets of strong product of directed graphs 281
v2
1
v1
1
D2
(u1, v1)
3
(u2, v1)
2
(u3, v1)
2
(u4, v1)
3
(u1, v2)
3
(u2, v2)
2
(u3, v2)
2
(u4, v2)
3
u1
3
u2
2
u3
2
u4
3
D1
Figure 1: D1 ⊠D2.
We have, ∂(D1 ⊠D2) ⊆ [∂(D1)× V (D2)] ∪ [V (D1)× ∂(D2)].
To this end, let (ui, vr) ∈ ∂(D1 ⊠ D2). Then there exists a vertex (uj , vs) ∈
V (D1 ⊠ D2) such that d((uj , vs), (ui, vr)) ≥ d((uj , vs), (uk, vq)) for every (uk, vq) ∈
N [(ui, vr)]. This implies, max{d(uj , ui), d(vs, vr)} ≥ max{d(uj , uk), d(vs, vq)} for
every uk ∈ N [ui] and for every vq ∈ N [vr]. Hence d(uj , ui) ≥ d(uj , uk) for ev-
ery uk ∈ N [ui], or d(vs, vr) ≥ d(vs, vq) for every vq ∈ N [vr]. Thus, ui ∈ ∂(D1) or
vr ∈ ∂(D2) or both. That is, if (ui, vr) ∈ ∂(D1 ⊠D2), then at least one of the vertices ui
and vr must be a boundary vertex in the corresponding factor graph.
Theorem 3.3. Let D1 and D2 be two strongly connected digraphs. Then ∂(D1 ⊠D2) =
A1 ∪A2 ∪A3, where
A1 = ∂(D1)× ∂(D2),
A2 = {(ui, vr) ∈ V (D1 ⊠D2) : ui ∈ ∂(D1), vr /∈ ∂(D2), and
∃vt ∈ V (D2) such that d(vt, vq) ≤ ecc(ui),∀vq ∈ N [vr]},
A3 = {(ui, vr) ∈ V (D1 ⊠D2) : ui /∈ ∂(D1), vr ∈ ∂(D2), and
∃uℓ ∈ V (D1) such that d(uℓ, uk) ≤ ecc(vr),∀uk ∈ N [ui]}.
Proof. Suppose that (ui, vr) ∈ ∂(D1 ⊠D2).
282 Ars Math. Contemp. 20 (2021) 275–288
Then there exists a vertex (uj , vs) ∈ V (D1 ⊠ D2) such that d((uj , vs), (ui, vr)) ≥
d((uj , vs), (uk, vq)) for all vertices (uk, vq) ∈ N [(ui, vr)]. Since d((uj , vs), (ui, vr)) =
max{d(uj , ui), d(vs, vr)} and d((uj , vs), (uk, vq)) = max{d(uj , uk), d(vs, vq)}, we get
max{d(uj , ui), d(vs, vr)} ≥ max{d(uj , uk), d(vs, vq)} for all uk ∈ N [ui], vq ∈ N [vr].
We distinguish four cases:
1. max{d(uj , ui), d(vs, vr)} = d(uj , ui) and d(vs, vr) ≥ d(vs, vq) for all vq ∈ N [vr];
2. max{d(uj , ui), d(vs, vr)} = d(uj , ui) and d(vs, vr) ≥ d(vs, vq) does not hold for all
vq ∈ N [vr];
3. max{d(uj , ui), d(vs, vr)} = d(vs, vr) and d(uj , ui) ≥ d(uj , uk) for all uk ∈ N [ui];
4. max{d(uj , ui), d(vs, vr)} = d(vs, vr) and d(uj , ui) ≥ d(uj , uk) does not hold for
all uk ∈ N [ui].
In cases 1 and 3, d(uj , ui) ≥ d(uj , uk) for all uk ∈ N [ui] and d(vs, vr) ≥ d(vs, vq)
for all vq ∈ N [vr]. So ui ∈ ∂(D1), vr ∈ ∂(D2), and hence (ui, vr) ∈ A1.
In case 2, ui ∈ ∂(D1) and vr is not a boundary vertex of vs in D2. If there exists any
vertex vt such that vr is a boundary vertex of vt, then we get (ui, vr) ∈ A1. Otherwise,
since vr /∈ ∂(D2), for every vertex vt ∈ V (D2), there exists some vertex vq ∈ N [vr] such
that d(vt, vr) < d(vt, vq). Hence if (ui, vr) is a boundary vertex of a vertex (uℓ, vt) in
D1 ⊠D2, then d((uℓ, vt), (ui, vr)) = max{d(uℓ, ui), d(vt, vr)} = d(uℓ, ui) > d(vt, vr),
for otherwise d(uℓ, ui) ≤ d(vt, vr) and so we get d((uℓ, vt), (ui, vr)) = d(vt, vr) <
d(vt, vq) = d((uℓ, vt), (ui, vq)), where (ui, vq) ∈ N [(ui, vr)].
Let (uk, vq) ∈ N [(ui, vr)]. Then d((uℓ, vt), (uk, vq)) = max{d(uℓ, uk), d(vt, vq)}. If
(ui, vr) is a boundary vertex of (uℓ, vt), then max{d(uℓ, ui), d(vt, vr)} ≥ max{d(uℓ, uk),
d(vt, vq)}. So the necessary condition for the vertex (ui, vr) such that ui ∈ ∂(D1) and vr /∈
∂(D2) to be a boundary vertex of the vertex (uℓ, vt) in D1 ⊠D2 is d(uℓ, ui) ≥ d(vt, vq)
for all vq ∈ N [vr]. Since ecc(ui) ≥ d(uℓ, ui) for all uℓ ∈ V (D1), the necessary condition
becomes ecc(ui) ≥ d(vt, vq) for all vq ∈ N [vr]. Thus, (ui, vr) ∈ A2.
Thus in case 2, (ui, vr) ∈ A1 ∪A2.
In case 4, vr ∈ ∂(D2) and ui is not a boundary vertex of uj in D1. As in case 2, it
follows that (ui, vr) ∈ A1 ∪A3.
Thus in all cases, we get ∂(D1 ⊠D2) ⊆ A1 ∪A2 ∪A3.
Conversely, suppose that (ui, vr) ∈ A1 ∪ A2 ∪ A3. First let (ui, vr) ∈ A1. Then
ui ∈ ∂(D1) and vr ∈ ∂(D2). So there exists vertices uj ∈ V (D1), vs ∈ V (D2) such
that d(uj , ui) ≥ d(uj , uk) for every uk ∈ N [ui], and d(vs, vr) ≥ d(vs, vq) for every
vq ∈ N [vr]. Hence in D1 ⊠ D2, d((uj , vs), (ui, vr)) = max{d(uj , ui), d(vs, vr)} ≥
max{d(uj , uk), d(vs, vq)} = d((uj , vs), (uk, vq)) for all vertices (uk, vq) ∈ N [(ui, vr)].
Thus, A1 ⊆ ∂(D1 ⊠D2).
Now let (ui, vr) ∈ A2. Then ui ∈ ∂(D1), vr /∈ ∂(D2) and there exists some vertex
vt ∈ V (D2) such that d(vt, vq) ≤ ecc(ui), for all vq ∈ N [vr]. Since ui ∈ ∂(D1), there
exists at least one vertex uj ∈ V (D1) such that d(uj , ui) ≥ d(uj , uk) for every uk ∈
N [ui]. Of these vertices, let ub be a vertex such that d(ub, ui) = ecc(ui). Hence in
D1 ⊠D2,
d((ub, vt), (ui, vr)) = max{d(ub, ui), d(vt, vr)}
≥ max{d(ub, uk), d(vt, vq)} = d((ub, vt), (uk, vq))
B. S. Anand et al.: Boundary-type sets of strong product of directed graphs 283
for all (uk, vq) ∈ N [(ui, vr)], since d(vt, vq) ≤ ecc(ui) = d(ub, ui) for all vq ∈ N [vr].
Thus, (ui, vr) is a boundary vertex of (ub, vt) in D1 ⊠D2 and hence A2 ⊆ ∂(D1 ⊠D2).
By analogous arguments and since the strong product of digraphs is commutative, it
follows that A3 ⊆ ∂(D1 ⊠D2).
Hence A1 ∪A2 ∪A3 ⊆ ∂(D1 ⊠D2).
Now consider Figure 1. ecc(v1) = ecc(v2) = 1. N [u2] = N [u3] = {u1, u2, u3, u4},
d(u1, u4) = 3, d(u1, u2) = d(u1, u3) = d(u2, u4) = d(u3, u4) = 2, and d(u2, u3) = 1.
u2 /∈ ∂(D1) and hence (u2, v1), (u2, v2) /∈ ∂(D1 ⊠ D2), since there is no vertex uℓ ∈
V (D1) such that d(uℓ, uk)) ≤ 1 for all uk ∈ N [u2]. For similar reasons, (u3, v1),
(u3, v2) /∈ ∂(D1 ⊠D2).
Consider the strong product of two connected undirected graphs. In the case of an
undirected graph, the maximum distance between two vertices is the usual distance between
the vertices. Also, since we deal with the distance between any two distinct vertices, it
doesn’t matter whether the undirected graphs are simple or not; that is, whether they contain
loops or parallel edges. So we state the result for any two connected nontrivial (not equal
to K1) undirected graphs.
Remark 3.4. The description for the boundary set of the strong product of two graphs
(undirected graphs) G and H presented in [4] holds only for the product of two nontrivial
graphs G and H . To this end, let H = K1 = ({v}, ∅). We have, ∂(K1) = {v} (since
all vertices of a complete graph are boundary vertices of the graph), and hence ∂(G) =̂
∂(G⊠K1) = (∂(G)× {v}) ∪ (V (G)× {v}) =̂ V (G), which is not true in general.
Corollary 3.5. Let D1 and D2 be two nontrivial connected undirected graphs. Then
∂(D1 ⊠D2) = [∂(D1)× V (D2)] ∪ [V (D1)× ∂(D2)].
Proof. By Theorem 3.3, if D1 and D2 are two strongly connected digraphs, ∂(D1⊠D2) =
A1∪A2∪A3. Since D1 and D2 are given to be two nontrivial undirected graphs, ecc(ui) ≥
1 for all ui ∈ V (D1), ecc(vr) ≥ 1 for all vr ∈ V (D2), d(ui, uk) = 1 for all uk ∈ N(ui),
and d(vr, vq) = 1 for all vq ∈ N(vr). Thus,
A1 = ∂(D1)× ∂(D2),
A2 = {(ui, vr) ∈ V (D1 ⊠D2) : ui ∈ ∂(D1), vr /∈ ∂(D2), and
∃vt ∈ V (D2) such that d(vt, vq) ≤ ecc(ui),∀vq ∈ N(vr)}
= ∂(D1)× V (D2),
A3 = {(ui, vr) ∈ V (D1 ⊠D2) : ui /∈ ∂(D1), vr ∈ ∂(D2), and
∃uℓ ∈ V (D1) such that d(uℓ, uk) ≤ ecc(vr),∀uk ∈ N(ui)}
= V (D1)× ∂(D2).
Therefore, ∂(D1⊠D2) = A1∪A2∪A3 = [∂(D1)×V (D2)]∪ [V (D1)×∂(D2)].
Theorem 3.6. Let D1 and D2 be two strongly connected digraphs.
1. If diam(D1) < diam(D2), then Per(D1 ⊠D2) = V (D1)× Per(D2).
2. If diam(D1) = diam(D2), then Per(D1 ⊠D2) = [Per(D1)× V (D2)] ∪
[V (D1)× Per(D2)].
284 Ars Math. Contemp. 20 (2021) 275–288
Proof.
1. Let diam(D2) = n. Let vr ∈ Per(D2).
Then for all ui ∈ V (D1), ecc(ui, vr) = max{ecc(ui), ecc(vr)} = n. Hence
(ui, vr) ∈ Per(D1 ⊠ D2). Also if vr /∈ Per(D2), then since ecc(ui, vr) < n,
(ui, vr) /∈ Per(D1⊠D2). Hence it follows that Per(D1⊠D2) = V (D1)×Per(D2).
2. Let diam(D1) = diam(D2) = n. If ui ∈ Per(D1), then for all vr ∈ V (D2),
(ui, vr) ∈ Per(D1 ⊠D2), since ecc(ui, vr) = max{ecc(ui), ecc(vr)} = n. Hence
(ui, vr) ∈ Per(D1 ⊠ D2). Similarly, if vr ∈ Per(D2), then for all ui ∈ V (D1),
(ui, vr) ∈ Per(D1 ⊠ D2). Hence it follows that [Per(D1) × V (D2)] ∪ [V (D1) ×
Per(D2)] ⊆ Per(D1 ⊠D2).
Conversely, if (ui, vr) ∈ Per(D1 ⊠ D2), then ecc(ui, vr) = max{diam(D1),
diam(D2)} = n. Thus, at least one of ecc(ui) and ecc(vr) must be necessarily
equal to n. Hence ui ∈ Per(D1) or vr ∈ Per(D2), and therefore, Per(D1 ⊠D2) ⊆
[Per(D1)× V (D2)] ∪ [V (D1)× Per(D2)].
Theorem 3.7. Let D1 and D2 be two strongly connected digraphs.
1. If rad(D1) = rad(D2), then
Ecc(D1 ⊠D2) = [Ecc(D1)× V (D2)] ∪ [V (D1)× Ecc(D2)].
2. If rad(D1) < rad(D2), then
Ecc(D1 ⊠D2) =
[ ⋃
ecc(ui)≥rad(D2)
Ecc(ui)× V (D2)
]
∪ [V (D1)× Ecc(D2)] .
Proof.
1. First we will prove that Ecc(D1 ⊠ D2) ⊆ [Ecc(D1) × V (D2)] ∪ [V (D1) ×
Ecc(D2)]. Let (ui, vr) ∈ Ecc(D1 ⊠ D2). Then there exists a vertex (uj , vs) such
that ecc(uj , vs) = d((uj , vs), (ui, vr)) = max{d(uj , ui), d(vs, vr)}. Since ecc(uj , vs) =
max{ecc(uj), ecc(vs)}, and ecc(uj) ≥ d(uj , ui) and ecc(vs) ≥ d(vs, vr), at least one of
ecc(uj) = d(uj , ui) and ecc(vs) = d(vs, vr) must hold. So necessarily ui is an eccentric
vertex of uj , or vr is an eccentric vertex of vs.
Hence (ui, vr) ∈ [Ecc(D1)× V (D2)] ∪ [V (D1)× Ecc(D2)].
Let rad(D1) = rad(D2) = n. Let ui ∈ Ecc(D1). Then there exists a vertex uj ∈
V (D1) such that ecc(uj) = d(uj , ui). Consider the vertex (ui, vr) ∈ V (D1 ⊠D2), where
vr is an arbitrary vertex in D2. Since rad(D2) = n, there exists a vertex vs ∈ V (D2) such
that ecc(vs) = n. Hence d(vs, vr) ≤ n and so ecc(uj , vs) = max{ecc(uj), ecc(vs)} =
max{ecc(uj), n} = ecc(uj). Thus, d((uj , vs), (ui, vr)) = max{d(uj , ui), d(vs, vr)} =
ecc(uj) = ecc(uj , vs). So (ui, vr) is an eccentric vertex of (uj , vs). Thus if ui ∈ Ecc(D1),
then (ui, vr) ∈ Ecc(D1 ⊠ D2) for all vr ∈ V (D2). Similarly, we can prove that if vq ∈
Ecc(D2), then (uk, vq) ∈ Ecc(D1 ⊠D2) for all uk ∈ V (D1).
Hence [Ecc(D1)× V (D2)]∪ [V (D1)×Ecc(D2)] ⊆ Ecc(D1 ⊠D2), and so the result
holds.
B. S. Anand et al.: Boundary-type sets of strong product of directed graphs 285
2. Let rad(D1) < rad(D2) = n. Let ui ∈ V (D1), vr ∈ V (D2). Here two cases arise:
Case 1. vr ∈ Ecc(D2).
Then there exists a vertex vs ∈ V (D2) such that ecc(vs) = d(vs, vr). Let up ∈
V (D1) be such that ecc(up) = rad(D1). Then since rad(D2) > ecc(up), ecc(up, vs) =
max{ecc(up), ecc(vs)} = ecc(vs). Also, d((up, vs), (ui, vr)) = max{d(up, ui),
d(vs, vr)} = ecc(vs). Thus, (ui, vr) is an eccentric vertex of (up, vs). So in this case,
V (D1)× Ecc(D2) ⊆ Ecc(D1 ⊠D2).
Case 2. vr /∈ Ecc(D2).
Let vq ∈ V (D2) be such that ecc(vq) = rad(D2). Let
⋃
ecc(ui)≥rad(D2) Ecc(ui) = A.
Let uk ∈ A. Then there exists a vertex up ∈ V (D1) such that ecc(up) ≥ rad(D2)
and ecc(up) = d(up, uk). Then d((up, vq), (uk, vr)) = max{d(up, uk), d(vq, vr)} =
d(up, uk) = ecc(up) = ecc(up, vq) and hence (uk, vr) is an eccentric vertex of (up, vq).
Hence in this case,
⋃
ecc(ui)≥rad(D2) Ecc(ui)× V (D2) ⊆ Ecc(D1 ⊠D2).
Thus,
[⋃
ecc(ui)≥rad(D2) Ecc(ui)× V (D2)
]
∪ [V (D1)× Ecc(D2)] ⊆ Ecc(D1 ⊠D2).
Conversely, let (uk, vr) ∈ Ecc(D1 ⊠ D2). Then there exists a vertex (uj , vs) ∈
V (D1⊠D2) such that ecc(uj , vs) = d((uj , vs), (uk, vr)) = max{d(uj , uk), d(vs, vr)} =
max{ecc(uj), ecc(vs)}. If vr ∈ Ecc(D2), we get (uk, vr) ∈ V (D1)× Ecc(D2).
Hence suppose that (uk, vr) ∈ Ecc(D1 ⊠ D2) and vr /∈ Ecc(D2). Then for all vs ∈
V (D2), ecc(vs) > d(vs, vr). Thus, ecc(uj , vs) = ecc(uj) = d(uj , uk). If possible,
suppose that uk /∈ A =
⋃
ecc(ui)≥rad(D2) Ecc(ui). Thus, there is no vertex uj in D1 such
that ecc(uj) = d(uj , uk) and ecc(uj) ≥ rad(D2). Hence if uk is an eccentric vertex of uj
in D1, then d(uj , uk) < rad(D2). We have, rad(D1⊠D2) = max{rad(D1), rad(D2)} =
rad(D2). Thus, (uk, vr) cannot be the eccentric vertex of any vertex (uj , vs) ∈ D1 ⊠D2,
since d((uj , vs), (uk, vr)) = max{d(uj , uk), (vs, vr)} ≠ ecc(uj , vs) in this case. This is
a contradiction, and hence uk ∈ A. Hence (uk, vr) ∈
⋃
ecc(ui)≥rad(D2) Ecc(ui)× V (D2).
Hence Ecc(D1⊠D2) ⊆
[⋃
ecc(ui)≥rad(D2) Ecc(ui)×V (D2)
]
∪ [V (D1)×Ecc(D2)].
Theorem 3.8. Let D1 and D2 be two strongly connected digraphs. Then Ct(D1 ⊠D2) =
A1 ∪A2 ∪A3, where
A1 = [Ct(D1)× Ct(D2)],
A2 = {(ui, vr) ∈ V (D1 ⊠D2) : ui ∈ Ct(D1), vr /∈ Ct(D2), and
ecc(vq) ≤ ecc(ui) for all vq ∈ N [vr]},
A3 = {(ui, vr) ∈ V (D1 ⊠D2) : ui /∈ Ct(D1), vr ∈ Ct(D2), and
ecc(uk) ≤ ecc(vr) for all uk ∈ N [ui]}.
Proof. (ui, vr) ∈ Ct(D1 ⊠D2) if and only if ecc(ui, vr) ≥ ecc(uk, vq) for all (uk, vq) ∈
N [(ui, vr)]; if and only if max{ecc(ui), ecc(vr)} ≥ max{ecc(uk), ecc(vq)} for all uk ∈
N [ui] and vq ∈ N [vr]; if and only if one of the following three cases holds.
1. max{ecc(ui), ecc(vr)} = ecc(ui) = ecc(vr). Then, ecc(ui) ≥ ecc(uk) and
ecc(vr) ≥ ecc(vq) for all uk ∈ N [ui] and vq ∈ N [vr].
2. max{ecc(ui), ecc(vr)} = ecc(ui) > ecc(vr). Then, ecc(ui) ≥ ecc(uk) for all
uk ∈ N [ui] and ecc(vr) < ecc(ui), ecc(vq) ≤ ecc(ui) for all vq ∈ N(vr).
286 Ars Math. Contemp. 20 (2021) 275–288
3. max{ecc(ui), ecc(vr)} = ecc(vr) > ecc(ui). Then, ecc(vr) ≥ ecc(vq) for all
vq ∈ N [vr] and ecc(ui) < ecc(vr), ecc(uk) ≤ ecc(vr) for all uk ∈ N(ui).
In case 1, (ui, vr) ∈ Ct(D1 ⊠D2).
In case 2, (ui, vr) ∈ {(ui, vr) ∈ V (D1 ⊠ D2) : ui ∈ Ct(D1), vr /∈ Ct(D2), and
ecc(vq) ≤ ecc(ui) for all vq ∈ N [vr]}.
In case 3, (ui, vr) ∈ {(ui, vr) ∈ V (D1 ⊠ D2) : ui /∈ Ct(D1), vr ∈ Ct(D2), and
ecc(uk) ≤ ecc(vr) for all uk ∈ N [ui]}.
Thus we get, Ct(D1 ⊠D2) = A1 ∪A2 ∪A3.
Consider the contour set of the strong product of two connected undirected graphs. As
in the case of the boundary set, the result holds even when the undirected graphs are not
simple.
Corollary 3.9. Let D1 and D2 be two connected undirected graphs. Then
Ct(D1 ⊠D2) = {(ui, vr) ∈ V (D1 ⊠D2) : ui ∈ Ct(D1), vr /∈ Ct(D2), and
ecc(vr) < ecc(ui)}
∪ {(ui, vr) ∈ V (D1 ⊠D2) : ui /∈ Ct(D1), vr ∈ Ct(D2), and
ecc(ui) < ecc(vr)}
∪ [Ct(D1)× Ct(D2)].
Proof. By Theorem 3.8, when D1 and D2 are two strongly connected digraphs, Ct(D1 ⊠
D2) = A1 ∪A2 ∪A3. Since D1 and D2 are given to be undirected graphs, eccentricity of
two adjacent vertices differ by atmost one. Hence
A1 = Ct(D1)× Ct(D2),
A2 = {(ui, vr) ∈ V (D1 ⊠D2) : ui ∈ Ct(D1), vr /∈ Ct(D2), and
ecc(vq) ≤ ecc(ui) for all vq ∈ N [vr]}
= {(ui, vr) ∈ V (D1 ⊠D2) : ui ∈ Ct(D1), vr /∈ Ct(D2), and
ecc(vr) + 1 ≤ ecc(ui)}
= {(ui, vr) ∈ V (D1 ⊠D2) : ui ∈ Ct(D1), vr /∈ Ct(D2), and ecc(vr) < ecc(ui)},
A3 = {(ui, vr) ∈ V (D1 ⊠D2) : ui /∈ Ct(D1), vr ∈ Ct(D2), and ecc(ui) < ecc(vr)},
since maxuk∈N [ui] ecc(uk) = ecc(ui) + 1. Hence it follows that
Ct(D1 ⊠D2) = {(ui, vr) ∈ V (D1 ⊠D2) : ui ∈ Ct(D1), vr /∈ Ct(D2), and
ecc(vr) < ecc(ui)}
∪ {(ui, vr) ∈ V (D1 ⊠D2) : ui /∈ Ct(D1), vr ∈ Ct(D2), and
ecc(ui) < ecc(vr)}
∪ [Ct(D1)× Ct(D2)].
We have examined the boundary-type sets of the strong product of two strongly con-
nected digraphs D1 and D2. Now suppose that at least one of D1 and D2, say D1, is not
strongly connected. Then the eccentricity of every vertex in D1 is infinity, and hence the
B. S. Anand et al.: Boundary-type sets of strong product of directed graphs 287
eccentricity of every vertex in D1 ⊠ D2 is infinity. Thus, we have ∂(D1) = Per(D1) =
Ecc(D1) = Ct(D1) = V (D1), and ∂(D1 ⊠D2) = Per(D1 ⊠D2) = Ecc(D1 ⊠D2) =
Ct(D1 ⊠ D2) = V (D1) × V (D2). Since rad(D1) = diam(D1) = ∞, the expression
for Per(D1 ⊠D2) in Theorem 3.6, and the expression for Ecc(D1 ⊠D2) in Theorem 3.7
gives V (D1) × V (D2). Since ecc(ui) = ∞ for all ui ∈ V (D1), the expression for
∂(D1 ⊠ D2) in Theorem 3.3, and the expression for Ct(D1 ⊠ D2) in Theorem 3.8 also
gives V (D1)× V (D2). Similar is the case when D2 and both D1 and D2 are not strongly
connected.
Thus, the results derived for the boundary-type sets of the strong product of two strongly
connected digraphs D1 and D2 hold also when the digraphs D1 and D2 are not even weakly
connected. So the results for the boundary-type sets of the strong product of two connected
undirected graphs hold for any two arbitrary undirected graphs.
4 Conclusion
In this article, the relationship between the boundary-type sets of the strong product of two
digraphs, and that of its factors is derived. As ‘maximum distance’ is the generalization
of the usual distance in an undirected graph, these results hold for undirected graphs also.
The results for the periphery and eccentricity sets of the strong product of two undirected
graphs turn out to be the same as the results in [4]. The results for the boundary and contour
sets in the undirected case, as described in [4], are also derived as special cases.
ORCID iDs
Bijo S. Anand https://orcid.org/0000-0002-7221-904X
Manoj Changat https://orcid.org/0000-0001-7257-6031
Prasanth G. Narasimha-Shenoi https://orcid.org/0000-0002-5850-5410
Mary Shalet Thottungal Joseph https://orcid.org/0000-0001-6350-7106
References
[1] J. Bang-Jensen and G. Gutin (eds.), Classes of Directed Graphs, Springer Monographs in Math-
ematics, Springer, Cham, 2018, doi:10.1007/978-3-319-71840-8.
[2] A. Broido and K. C. Claffy, Internet topology: Connectivity of IP graphs, in: S. Fahmy and
K. Park (eds.), Scalability and Traffic Control in IP Networks, SPIE, volume 4526 of Con-
ference Proceedings of SPIE, 2001 pp. 172–187, doi:10.1117/12.434393, proceedings of the
International Symposium on the Convergence of IT and Communications (ITCom 2001) held
in Denver, Colorado, United States, August 20 – 24, 2001.
[3] J. Cáceres, C. Hernando, M. Mora, I. M. Pelayo, M. L. Puertas and C. Seara, On geodetic sets
formed by boundary vertices, Discrete Math. 306 (2006), 188–198, doi:10.1016/j.disc.2005.
12.012.
[4] J. Cáceres, M. del C. Hernando Martín, M. Mora Giné, I. M. Pelayo Melero and M. L.
Puertas González, Boundary-type sets and product operators in graphs, in: VII Jornadas
de Matemática Discreta y Algorítmica, Castro Urdiales, 2010 pp. 187–194, http://hdl.
handle.net/2117/8383.
[5] J. Cáceres, A. Márquez, O. R. Oellermann and M. Luz Puertas, Rebuilding convex sets in
graphs, Discrete Math. 297 (2005), 26–37, doi:10.1016/j.disc.2005.03.020.
288 Ars Math. Contemp. 20 (2021) 275–288
[6] M. Changat, P. G. Narasimha-Shenoi, M. S. Thottungal Joseph and R. Kumar, Boundary ver-
tices of Cartesian product of directed graphs, Int. J. Appl. Comput. Math. 5 (2019), Article
No. 19, doi:10.1007/s40819-019-0604-4.
[7] G. Chartrand, D. Erwin, G. L. Johns and P. Zhang, Boundary vertices in graphs, Discrete Math.
263 (2003), 25–34, doi:10.1016/s0012-365x(02)00567-8.
[8] G. Chartrand and S. Tian, Distance in digraphs, Computers Math. Applic. 34 (1997), 15–23,
doi:10.1016/s0898-1221(97)00216-2.
[9] R. Hammack, W. Imrich and S. Klavžar, Handbook of Product Graphs, Discrete Mathematics
and its Applications (Boca Raton), CRC Press, Boca Raton, FL, 2nd edition, 2011, doi:10.
1201/b10959.
[10] R. H. Hammack, Digraphs products, in: J. Bang-Jensen and G. Gutin (eds.), Classes of Directed
Graphs, Springer, Cham, pp. 467–515, 2018, doi:10.1007/978-3-319-71840-8_10.
[11] M. Hellmuth and T. Marc, On the Cartesian skeleton and the factorization of the strong product
of digraphs, Theoret. Comput. Sci. 565 (2015), 16–29, doi:10.1016/j.tcs.2014.10.045.
[12] M. W. Massing, G. A. Robinson, C. E. Marx, O. Alzate and R. D. Madison, Applications of
proteomics to nerve regeneration research, in: O. Alzate (ed.), Neuroproteomics, CRC Press,
Boca Raton, FL, Frontiers in Neuroscience, pp. 289–313, 2009.
[13] H. E. Robbins, Questions, discussions, and notes: A theorem on graphs, with an application to
a problem of traffic control, Amer. Math. Monthly 46 (1939), 281–283, doi:10.2307/2303897.
[14] J. J. Stemley, One-way streets provide superior safety and convenience, ITE Journal 68 (1998),
47–50.