ISSN 2590-9770
The Art of Discrete and Applied Mathematics 6 (2023) #P2.13
https://doi.org/10.26493/2590-9770.1508.8b5
(Also available at http://adam-journal.eu)
Distance formula for direct-co-direct product in
the case of disconnected factors*
Aleksander Kelenc† , Iztok Peterin‡
University of Maribor, FERI, Koroška cesta 46, 2000 Maribor, Slovenia and
Institute of Mathematics, Physics and Mechanics, Jadranska 19, 1000 Ljubljana, Slovenia
Received 21 November 2021, accepted 25 September 2022, published online 4 January 2023
Abstract
Direct-co-direct product G⊛H of graphs G and H is a graph on the vertex set V (G)×
V (H). Two vertices (g, h) and (g′, h′) are adjacent if gg′ ∈ E(G) and hh′ ∈ E(H)
or gg′ /∈ E(G) and hh′ /∈ E(H). We show that if at most one factor of G ⊛ H is
connected, then the distance between two vertices of G ⊛ H is bounded by three unless
some small number of exceptions. All the exceptions are completely described which
yields the distance formula.
Keywords: Direct-co-direct product, distance, eccentricity, disconnected graphs.
Math. Subj. Class.: 05C12, 05C76
1 Introduction
Recently Wilfried Imrich complained (personal communication) that the modular product
is the only associative and commutative graph product (up to their complementary prod-
ucts) for which he was not successful in finding a polynomial time algorithm for prime
factorization with respect to the modular product. His best approach to that can be found
in [6], while polynomial algorithms for factoring the Cartesian product is in [8], for the
strong product in [5] and for the direct product in [7]. The reason for this could be hid-
den in the fact that modular products are often diameter two graphs, see [9]. This means
that any polynomial algorithm for a prime factorization of modular product would yield a
powerful tool how to connect (some) diameter two graphs with two or more smaller graphs
*The authors would like to thanks our mentor, colleague and dear friend Wilfried Imrich, who is also our
academical father, grandfather and grand grandfather at the same time. In particular we would like to thank for
all the shared enthusiasm on the world of graph products that are also the topic of this work.
†Corresponding author. Partially supported by the Slovenian Research Agency ARRS via grant J1–2452.
‡Partially supported by the Slovenian Research Agency ARRS via program P1–0297.
E-mail addresses: aleksander.kelenc@um.si (Aleksander Kelenc), iztok.peterin@um.si (Iztok Peterin)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Art Discrete Appl. Math. 6 (2023) #P2.13
usually of higher diameter. Namely, the connections between a product and its factors often
give rise to several connections between graph invariants on the products. Let us mention
here just the two most known: the Vizing’s conjecture, see [2], which is still open and the
Hedetniemi’s conjecture that was recently disproved in [13], but had also inspired a broad
palette of innovative results and new approaches.
The direct-co-direct product G ⊛ H of graphs G and H can be viewed as a subgraph
of modular product with important difference, that as a product the direct-co-direct product
is not associative. Much less is known about products that are not associative. Up to the
best of our knowledge, the first use of non-associative products is due to Watkins [14] to
construct certain automorphism groups of graphs. This was later generalized to directed
graphs by Grech et al. in [3]. In between we are aware of only one publication on direct-
co-direct product by Kozen [12] where it is shown that for two graphs G and H of order n,
the problem of finding a clique of order n in G⊛H is equivalent to isomorphism problem
between G and H . We expect that non-associative products hide several pleasant surprises
from many different aspects: structural, algorithmic and to derive connections between
products and their factors.
Recently, in [10], the distance formula was presented for the direct-co-direct product
for the case of connected factors. In this work we continue to study the distance in direct-
co-direct product where at least one factor is not connected. Also here one can observe
some similarities between direct-co-direct and modular product. The distance (when nei-
ther factor is complete) is again limited, usually by three, often even by two, but there are
some exceptions where the distance can be four or even five. For connected factors observe
[10] and the case where at least one factor is not connected is treated in the rest of this
paper.
2 Preliminaries
Let G be a finite, simple and undirected graph and v ∈ V (G). The set NG(v) is the
open neighborhood of v and contains all vertices adjacent to v in G. The closed neigh-
borhood NG[v] of v is NG(v) ∪ {v}. We also use the notation NG[g] for the complement
V (G) − NG[g] of NG[g]. The cardinality of NG(v) is the degree of v and is denoted by
δG(v). An isolated vertex of G has δG(v) = 0, a leaf of G has δG(v) = 1 and a uni-
versal vertex of G has δG(v) = |V (G)| − 1. The complement G of G is a graph with
V (G) = V (G) and two vertices are adjacent in G whenever they are not adjacent in G.
The subgraph of G induced by S ⊆ V (G) is denoted by G[S]. By G ∪ H we mean the
disjoint union of graphs G and H . As usual Kn is a complete graph on n vertices and Kp,q
is a complete bipartite graph with partitions of cardinality p and q.
By a product of two graphs G and H we mean a graph on a vertex set V (G)× V (H).
Different products have then different definitions of their edge set. Two vertices (g, h) and
(g′, h′) are adjacent in the direct product G×H if gg ∈ E(G) and hh ∈ E(H). All such
edges are then called the direct edges. The edge set of direct-co-direct product, or DcD
product for short, G⊛H can now be expressed as
E(G⊛H) = E(G×H) ∪ E(G×H). (2.1)
In other words, (g, h)(g′, h′) ∈ E(G⊛H) if gg ∈ E(G) and hh ∈ E(H) or gg′ ∈ E(G)
and hh′ ∈ E(H). Direct edges fulfill the first condition while the edges that correspond
to the second condition are called the co-direct edges, because we can see them as the
A. Kelenc et al.: Distance formula for direct-co-direct product in the case of disconnected factors 3
edges of direct product of complements of G and H , that is G × H . Notice by (2.1) that
Kn ⊛H ∼= Kn ×H .
DcD product is clearly commutative because of its symmetric definition. On the other
hand, it is not hard to see that DcD product is not associative, see Introduction section
of [10]. From definition it follows that
G⊛H ∼= G⊛H. (2.2)
Clearly, we have Kn ⊛H ∼= Kn ⊛H ∼= Kn ×H by (2.2) and (2.1).
2.1 Connectivity
The result about connectivity of DcD product was given already in [10] and it is as follows.
The proof strongly rely on connectivity of direct product due to Wiechsel in [15], see
also [4].
Theorem 2.1 ([10, Theorem 2]). Let G and H be two graphs on at least two vertices.
Direct-co-direct product G⊛H is not connected if and only if
• one factor has a universal vertex and the other an isolated vertex, or
• one factor is K2 and the other is bipartite, or
• one factor is K2 and the complement of the other is bipartite, or
• one factor is Kt and the other is not connected, or
• one factor is Kt and the complement of the other is not connected, or
• both factors are disjoint union of two complete graphs, or
• both factors are complete bipartite graphs.
We are interested in disconnected factors. As already mention, totally disconnected
graphs Kt can be treated in the same manner as complete graphs. Hence we are left only
with two possible choises from above theorem that needed to be avoid: first and for-last
item.
2.2 Distance
The distance dG(u, v) between vertices u and v in a graph G is the minimum number of
edges on a path between u and v; if there is no such path, then we have dG(u, v) = ∞. The
maximum distance between v and any vertex of G is the eccentricity eccG(v) of v in G and
the maximum eccentricity of a vertex in graph G is called the diameter diam(G) od G. By
a distance formula in a graph product we usually describe a rule that completely describe
the distance between two vertices (g, h) and (g′, h′) in a product. Such formulas are well
known for Cartesian, strong and lexicographic product, see [4]. Here we rely more on the
distance formula in direct product due to its connection with DcD product. This formula
is a bit more complicated and contains odd distance doG(u, v) and even distance d
e
G(u, v)
between two vertices u and v in a graph G. More detailed, doG(u, v) is the minimum
odd number of edges on a walk between u and v if it exists and ∞ otherwise. Similarly,
deG(u, v) is the minimum even number of edges on a walk between u and v if it exists
4 Art Discrete Appl. Math. 6 (2023) #P2.13
and ∞ otherwise. The following distance formula was proven for the direct product by
Kim [11]
dG×H((g, h), (g
′, h′)) = min{max{deG(g, g′), deH(h, h′)},max{doG(g, g′), doH(h, h′)}}
(2.3)
and an alternative approach can be found in [1]. By a direct use of this formula we can get
the distance formula for Kn ⊛H as well as for Kn ⊛H as observed already in [10]. We
state only the formula for Kn ⊛H because we are interested in connected DcD products
with at least one disconnected factor, see Theorem 2.1. Moreover, we divide this case to
n = 2 and to n ≥ 3. For n = 2 we need such a graph H , that H is connected and non-
bipartite to assure connectedness of K2⊛H by Theorem 2.1. We have K2⊛H ∼= K2×H
and by (2.3) we immediately obtain
dK2⊛H((g, h), (g
′, h′)) =
{
do
H
(h, h′) : g ̸= g′
de
H
(h, h′) : g = g′.
. (2.4)
For n ≥ 3 graph H must be such that H is connected to assure connectedness of Kn ⊛H
by Theorem 2.1. We have Kn ⊛H ∼= Kn ×H and by (2.3) we obtain
dKn⊛H((g, h), (g
′, h′)) =
{
min{do
H
(h, h′),max{2, de
H
(h, h′)}} : g ̸= g′
min{de
H
(h, h′),max{3, do
H
(h, h′)}} : g = g′.
(2.5)
Another useful result from [10] is the following that describe all the pairs of vertices
that are at distance two in G ⊛H . The idea of the proof is to check what happens if both
edges on a shortest path are direct edges, both are co-direct edges or one is a direct and the
other a co-direct edge.
Theorem 2.2 ([10, Theorem 9]). Let G and H be non-complete graphs such that G ⊛H
is connected. The distance dG⊛H((g, h), (g′, h′)) = 2 if and only if at least one of the
following possibilities holds for some g′′ ∈ V (G) and h′′ ∈ V (H)
(i) (path gg′′g′ is induced in G and hh′h′′ is C3 in H) or (path hh′′h′ is induced in H
and gg′g′′ is C3 in G);
(ii) (path gg′′g′ is induced in G and hh′h′′ is C3 in H) or (path hh′′h′ is induced in H
and gg′g′′ is C3 in G);
(iii) (g = g′ and gg′′ ∈ E(G) and hh′′h′ is a path in H) or (h = h′ and hh′′ ∈ E(H)
and gg′′g′ is a path in G);
(iv) (g = g′ and gg′′ ∈ E(G) and hh′′h′ is a path in H) or (h = h′ and hh′′ ∈ E(H)
and gg′′g′ is a path in G);
(v) (g′gg′′ is induced in G and hh′h′′ is induced in H) or (gg′g′′ is induced in G and
h′hh′′ is induced in H);
(vi) (g′gg′′ is induced in G and hh′h′′ is induced in H) or (gg′g′′ is induced in G and
h′hh′′ is induced in H).
A. Kelenc et al.: Distance formula for direct-co-direct product in the case of disconnected factors 5
3 Main result
We start with several conditions that describe all the situations when the distance exceeds
three in G⊛H . First three conditions are about two components in both factors G and H .
Condition 1. Let G and H be graphs with two components, {X,Y } = {G,H}, X =
X1∪X2 and Y ∼= K1∪Kt, t ≥ 2, and at most one of X1 and X2 is complete. Let x be the
universal vertex of X1, let x′ be the universal vertex of X2 and let y = y′ be the isolated
vertex of Y .
Notice that if both X1 and X2 are complete in above condition, then X ⊛ Y is not
connected by Theorem 2.1.
Condition 2. Let G and H be graphs with two components, {X,Y } = {G,H}, X =
X1 ∪Ks, where X1 ≇ Kr and Y ∼= K1 ∪Kt, t ≥ 2. Let x and x′ be the universal vertices
of X1 (they can be the same vertex), let y be the isolated vertex of Y and let y′ ∈ V (Kt).
Next condition is just a symmetric version of Condition 2 with respect to y and y′.
Condition 3. Let G and H be graphs with two components, {X,Y } = {G,H}, X =
X1 ∪Ks, where X1 ≇ Kr and Y ∼= Kt ∪K1, t ≥ 2. Let x and x′ be the universal verices
of X1 (they can be the same vertex), let y′ be the isolated vertex of Y and let y ∈ V (Kt).
We continue with a condition that we need when one factor has at least three compo-
nents and the other is connected.
Condition 4. Let G and H be two graphs such that one has at least two components and
the other is K1,t, t ≥ 2, {X,Y } = {G,H}, X = X1 ∪X2 ∪ · · · ∪Xr and Y ∼= K1,t. Let
y = y′ be a universal vertex of Y and let x and x′ be vertices of X1 such that dX(x, x′) = 3
or dX(x, x′) = 1 and such that for every x1 ∈ NX(x) it holds that NX(x′) ⊆ NX(x1).
All the following conditions are needed in the case where one factor is connected and
the other has two components.
Condition 5. Let G and H be two graphs such that one has two components and the other
is connected, {X,Y } = {G,H}, X = K2 ∪ Kt, t ≥ 1, and Y = K2,p, p ≥ 1. Let
K2 = xx
′ for X and {y, y′} is one of bipartite sets of Y .
Condition 6. Let G and H be two graphs such that one has two components and the other is
connected, {X,Y } = {G,H}, X = K2 ∪K1. Let x = x′ ∈ V (K2) and let y, y′ ∈ V (Y )
be such that eccY (y) = 3, dY (y, y′) = 3 and Y [NY [y]] and Y [NY [y]] are complete.
Condition 7. Let G and H be two graphs such that one has two components and the other
is connected, {X,Y } = {G,H}, X = Kt ∪ K1, t ≥ 2. Let x ∈ V (Kt), x′ is the
component K1 and let y, y′ ∈ V (Y ) be such that eccY (y) = 3, y′ is a universal vertex
of Y [NY [y]], y′ is adjacent to all vertices that are at distance two to y and every vertex at
distance three to y is a universal vertex of Y [NY [y]].
For the next condition we need a new notation. A vertex g1 ∈ NG(g) is a satellite of g
if NG[g1] ⊆ NG[g]. Set B′1 contains further all the satellite vertices of g.
6 Art Discrete Appl. Math. 6 (2023) #P2.13
Condition 8. Let G and H be two graphs such that one has two components and the other
is connected, {X,Y } = {G,H}, X = K1 ∪ Kp, p ≥ 2. Let x = x′ be component K1,
let y ∈ V (Y ) be a vertex with eccY (y) = 3 and let y′ ∈ V (Y ) be such that dY (y, y′) = 2
and y′ is adjacent to every vertex from V (Y ) − (B′1 ∪ {y, y′}) where B′1 contains all the
satellite vertices of y.
Condition 9. Let G and H be two graphs such that one has two components and the other
is connected, {X,Y } = {G,H}, X = K1 ∪ Kp, p ≥ 2. Let x be a component K1, let
x′ ∈ V (Kp) and let y ∈ V (Y ) be such that eccY (y) = 2, Y [NY [y]] is complete and let y′
be a satellite vertex of y such that NY [y′] = B′1 ∪ {y} and there exists all edges between
NY [y] and NY (y)−B′1 where B′1 contains all the satellite vertices of y.
Condition 10. Let G and H be two graphs such that one has two components and the other
is connected, {X,Y } = {G,H}, X = K1 ∪Kp, p ≥ 2. Let x = x′ be a component K1,
let y ∈ V (Y ) be a vertex with eccY (y) = 2 and let y′ ∈ V (Y ) be such that dY (y, y′) = 2
and y′ is adjacent to every vertex from V (Y ) − (B′1 ∪ {y, y′}) where B′1 contains all the
satellite vertices of y.
Condition 11. Let G and H be two graphs such that one has two components and the
other is connected, {X,Y } = {G,H}, X = K1 ∪Kp, p ≥ 2. Let x = x′ be a component
K1, let y ∈ V (Y ) be such that eccY (y) = 2 and let y′ be adjacent to every vertex of
V (Y ) − (B′1 ∪ {y′}) and (there exists a vertex from NY [y′] that is not adjacent to some
vertex from B′1 or Y [NY [y]] is not complete or there is an edge between NY [y
′] and
NY (y)−B′1) where B′1 contains all the satellite vertices of y.
The only situation where G or H is not connected and we have distance five between
two vertices of G⊛H is described by the following condition, see Theorem 4.5.
Condition 12. Let G and H be two graphs such that one has two components and the
other is connected, {X,Y } = {G,H}, X = K1 ∪Kp, p ≥ 2. Let x = x′ be a component
K1, let y ∈ V (Y ) be such that eccY (y) = 2 and let y′ be adjacent to every vertex of
V (Y )− (B′1∪{y′}) and every vertex from NY [y′] is adjacent to every vertex from B′1 and
Y [NY [y]] is complete and there is no edge between NY [y′] and NY (y) − B′1 where B′1
contains all the satellite vertices of y.
The main goal is to prove the distance formula for DcD product under the assumption
that at least one factor of G⊛H is not connected and that the product is connected according
to Theorem 2.1. The formula is as follows:
dG⊛H((g, h), (g
′, h′)) =

0 : g = g′ ∧ h = h′
1 : (g, h)(g′, h′) ∈ E(G⊛H)
2 : (g, h), (g′, h′) fulfills Theorem 2.2
3 : otherwise
4 : one of Conditions 1 – 11 holds
5 : Condition 12 holds.
(3.1)
The proof for this formula follows directly from the adjacency definition of G ⊛ H ,
from Theorem 2.2 and from Theorems 4.1 – 4.5 that are stated in the next section. In the
mentioned theorems we bound eccentricity of a vertex (g, h) by five in all different possible
A. Kelenc et al.: Distance formula for direct-co-direct product in the case of disconnected factors 7
cases with respect to the number of components in factors G and H . In particular, we fully
describe all the cases when the eccentricity is five by Condition 12 and when it is four by
Conditions 1 – 11.
We end with two simple corollaries about diameter of DcD product. The first one is a
direct consequence of Theorem 4.1 and the second one follows from situations described
in Conditions 1 – 12.
Corollary 3.1. If G and H are both graphs with at least three components, then diam(G⊛
H) = 2.
Corollary 3.2. Let G and H be graphs different than K1,t, K1 ∪Kt and K2 ∪Kt, t ≥ 2.
If at least one of G and H is not connected, then diam(G⊛H) ≤ 3.
4 Eccentricity of a vertex in DcD product
In this section we bound the eccentricity of a vertex (g, h) in a connected DcD product
G ⊛ H of graphs G and H , where at least one of G and H is disconnected. For this
we use the following notation. Suppose that graph G has r components. We write G =
G1 ∪G2 ∪ · · · ∪Gr, where Gi is a component of graph G for every i ∈ {1, 2, . . . , r}.
We have to go through all possible numbers of components of factors. Namely, we
study the eccentricity of vertices in DcD products where the numbers of components of
both factors are all integer pairs (a, b), where a ≥ 1 and b ≥ 1, except the pair (1, 1) which
has already been studied in [10]. First we describe the situation, where both factors G and
H have at least three components.
Theorem 4.1. If G and H have at least three components, then eccG⊛H((g, h)) = 2 for
any vertex (g, h) ∈ V (G⊛H).
Proof. Without loss of generality suppose that g ∈ V (G1) and h ∈ V (H1). For any vertex
(g′, h′), where g′ /∈ V (G1) and h′ /∈ V (H1) we have an edge between (g, h) and (g′, h′)
in DcD product G⊛H . Next, suppose that g′ ∈ V (G1) and h′ is an arbitrary vertex from
V (H). Let g′′ ∈ V (G2) be an arbitrary vertex. We can choose vertex h′′ such that it is not
in the same component as h and h′, since we have at least three components in H . It follows
that (g, h)(g′′, h′′)(g′, h′) is a path of length two in G⊛H and dG⊛H((g, h), (g′, h′)) ≤ 2.
One can see that dG⊛H((g, h), (g′, h′)) ≤ 2 also in the symmetric situation when h′ ∈
V (H1) and g′ is an arbitrary vertex from V (G), since we have at least three components
also in G. The equality follows because (g, h) is not adjacent to (g, h′) for h′ ̸= h.
Next, we study the situation, where one factor has two components and the other at
least three components. We can suppose that the second factor has two components, since
DcD product is commutative.
Theorem 4.2. Let G and H be graphs. If one of them has at least three components and the
other has two components, then eccG⊛H((g, h)) ≤ 3, for any vertex (g, h) ∈ V (G⊛H).
Proof. Without loss of generality suppose that G has at least three components and H
has two components. Let g ∈ V (G1) and h ∈ V (H1). For any vertex (g′, h′), where
g′ /∈ V (G1) and h′ ∈ V (H2) we have an edge between (g, h) and (g′, h′) in DcD product
G ⊛ H . Next, suppose that h′ ∈ V (H1) and g′ ∈ V (G) are arbitrary vertices. We
select h′′ ∈ V (H2) arbitrarily. We can choose vertex g′′ such that it is not in the same
8 Art Discrete Appl. Math. 6 (2023) #P2.13
component as g and g′, since we have at least three components in G. It follows that
(g, h)(g′′, h′′)(g′, h′) is a path of length two in G ⊛ H and dG⊛H((g, h), (g′, h′)) ≤ 2.
It remains to check the vertices (g′, h′), where g′ ∈ V (G1) and h′ ∈ V (H2). Let g2 ∈
V (G2) and g3 ∈ V (G3). There exists a path (g, h)(g2, h′)(g3, h)(g′, h′) in G ⊛ H and
dG⊛H((g, h), (g
′, h′)) ≤ 3. Therefore, eccG⊛H((g, h)) ≤ 3.
Now we study the eccentricity of vertices of DcD products where both factors G and H
have two components. Notice that we are not studying cases where one factor is isomorphic
to K2, since this was already covered by (2.4). The Conditions 1, 2 and 3 are essential to
describe all the vertices of eccentricity four in this case.
Theorem 4.3. If G and H are graphs with two components different than K2 such that
G ⊛ H is connected, then eccG⊛H((g, h)) ≤ 4. Moreover, we have eccG⊛H((g, h)) =
dG⊛H((g, h), (g
′, h′)) = 4 if and only if Conditions 1 or 2 or 3 are fulfilled.
Proof. Let G = G1 ∪ G2 and H = H1 ∪ H2. Without loss of generality suppose
that g ∈ V (G1) and h ∈ V (H1). For any vertex (g′, h′), where g′ ∈ V (G2) and
h′ ∈ V (H2) we have an edge between (g, h) and (g′, h′) in DcD product G ⊛ H . Next,
suppose that h′ ∈ V (H1) and g′ ∈ V (G1) are arbitrary vertices, where (g, h) ̸= (g′, h′).
There exists a path (g, h)(g′′, h′′)(g′, h′) such that g′′ ∈ V (G2) and h′′ ∈ V (H2) and
dG⊛H((g, h), (g
′, h′)) ≤ 2. Therefore, dG⊛H((g, h), (g′, h′)) ≤ 2 for any (g′, h′) ∈
(V (G1) × V (H1)) ∪ (V (G2) × V (H2)). Hence we deal in the remaining of the proof
with vertices from (V (G1)× V (H2))∪ (V (G2)× V (H1)). Suppose that vertex g is not a
universal vertex of G1 such that gg1 /∈ E(G1), g1 ∈ V (G1). For any vertex (g′, h′), where
g′ ∈ V (G2) and h′ ∈ V (H1), there exists a path (g, h)(g1, h2)(g′, h′) for h2 ∈ V (H2).
It follows that dG⊛H((g, h), (g′, h′)) ≤ 2. For any vertex (g′, h′), where g′ ∈ V (G1) and
h′ ∈ V (H2), there exists a walk (g, h)(g1, h′)(g2, h)(g′, h′) for g2 ∈ V (G2). It follows
that dG⊛H((g, h), (g′, h′)) ≤ 3. With similar construction we can bound the distance from
(g, h) to the vertices of (V (G1)× V (H2))∪ (V (G2)× V (H1)) in the case when vertex h
is not a universal vertex of H1. Therefore, we can assume that both g and h are universal
vertices in their components.
In the rest of the proof we split cases according to the fact whether some components
of factors are complete graphs or not. First we go through situations where at least two (out
of four) components are not complete graphs and then we analyse cases where exactly one
connected component is not a complete graph. Recall, from Theorem 2.1, that if all four
components are complete graphs, then the DcD product is not connected.
Suppose first that G1 and H1 are not complete graphs, so there are g1g′1 /∈ E(G1)
and h1h′1 /∈ E(H1). For each vertex (g′, h′) ∈ V (G1) × V (H2) there exists a path
(g, h)(g1, h1)(g2, h
′
1)(g
′, h′) for g2 ∈ V (G2) and dG⊛H((g, h), (g′, h′)) ≤ 3. Similarly
for (g′, h′) ∈ V (G2) × V (H1) there exists a path (g, h)(g1, h1)(g′1, h2)(g′, h′) for h2 ∈
V (H2) and dG⊛H((g, h), (g′, h′)) ≤ 3.
Next suppose that G1 and H2 are not complete graphs, therefore, there exist non-edges
g1g
′
1 /∈ E(G1) and h2h′2 /∈ E(H2). For each vertex (g′, h′) ∈ V (G2)×V (H1) there exists
a path (g, h)(g′, h2)(g, h′2)(g
′, h′) and dG⊛H((g, h), (g′, h′)) ≤ 3. Let (g′, h′) be an arbi-
trary vertex from V (G1)×V (H2). If h′ ∈ V (H2) is not a universal vertex of H2, then there
is a non-edge h′h′′ /∈ E(H2). It follows that there exists a path (g, h)(g2, h′′)(g′, h′) for
g2 ∈ V (G2) and dG⊛H((g, h), (g′, h′)) = 2. Otherwise, h′ ∈ V (H2) is a universal vertex
of H2. If g′ ̸= g, then there exists a path (g, h)(g2, h2)(g, h′2)(g′, h′) for g2 ∈ V (G2) and
A. Kelenc et al.: Distance formula for direct-co-direct product in the case of disconnected factors 9
dG⊛H((g, h), (g
′, h′)) ≤ 3. If g′ = g, then there exists a path (g, h)(g2, h2)(g1, h′2)(g′, h′)
for g2 ∈ V (G2) and again dG⊛H((g, h), (g′, h′)) ≤ 3. Notice that the case where G2 and
H1 are not complete graphs is symmetric to the case where G1 and H2 are not complete
graphs, so we can derive the same conclusions.
Now suppose that G2 and H2 are not complete graphs, therefore, there exist non-edges
g2g
′
2 /∈ E(G2) and h2h′2 /∈ E(H2). For each vertex (g′, h′) ∈ V (G2)×V (H1) there exists
a path (g, h)(g2, h2)(g, h′2)(g
′, h′) and it holds that dG⊛H((g, h), (g′, h′)) ≤ 3. Symmet-
rically we consider the case when (g′, h′) ∈ V (G1)× V (H2).
The last case where at least two components are not complete graphs is the case
where G1 and G2 are not complete graphs. Notice that the case where H1 and H2 are
not complete graphs is symmetrical. Therefore, there exist non-edges g1g′1 /∈ E(G1)
and g2g′2 /∈ E(G2). For each vertex (g′, h′) ∈ V (G1) × V (H2) there exists a path
(g, h)(g2, h
′)(g′2, h)(g
′, h′) and dG⊛H((g, h), (g′, h′)) ≤ 3. Let (g′, h′) be an arbitrary
vertex from V (G2) × V (H1). If g′ ∈ V (G2) is not a universal vertex of G2, then there
is a non-edge g′g′′ /∈ E(G2). It follows that there exists a path (g, h)(g′′, h2)(g′, h′), for
h2 ∈ V (H2), and dG⊛H((g, h), (g′, h′)) = 2. Otherwise, g′ ∈ V (G2) is a universal vertex
of G2. Suppose that there are at least two vertices h and h1 in H1. If h′ ̸= h, then there
exists a path (g, h)(g2, h2)(g′2, h)(g
′, h′) for h2 ∈ V (H2) and dG⊛H((g, h), (g′, h′)) ≤ 3.
If h′ = h, then there exists a path (g, h)(g2, h2)(g′2, h1)(g
′, h′) for h2 ∈ V (H2) and
again dG⊛H((g, h), (g′, h′)) ≤ 3. Suppose now that there is only one vertex in H1,
namely H1 ∼= K1. If H2 is not isomorphic to a complete graph, then there exists a
non-edge h2h′2 /∈ E(H2) and there is a path (g, h)(g2, h2)(g, h′2)(g′, h′). It follows that
dG⊛H((g, h), (g
′, h′)) ≤ 3. Otherwise, H2 ∼= Kt, t ≥ 2 and Condition 1 is fulfilled for
the pair of vertices (g, h) and (g′, h′). With the path (g, h)(g2, h2)(g′2, h)(g, h2)(g
′, h′) for
h2 ∈ V (H2) we get dG⊛H((g, h), (g′, h′)) ≤ 4.
It remains to study the cases where exactly one component is not a complete graph.
Suppose first that only G2 is not a complete graph. Therefore, there exists a non-edge
g2g
′
2 /∈ E(G2). We can make the same construction of the paths and we get the same
conclusions as in the previous case where G1 and G2 were not complete graphs, since
there were no usage of vertices g1 and g′1 in the proof. The only difference is that there is
no possibility that H2 is not isomorphic to a complete graph. Notice that also Condition 1
is fulfilled since it requires that one connected component has to be non-isomorphic to a
complete graph. The case where only H2 is not a complete graph is symmetric.
Suppose that only G1 is not a complete graph. There exists a non-edge g1g′1 /∈ E(G1).
Suppose that |V (H1)| ≥ 2 and |V (H2)| ≥ 2. For each vertex (g′, h′) ∈ V (G2)× V (H1)
there exists a path (g, h)(g1, h1)(g′1, h2)(g
′, h′) for h1 ∈ NH1(h) and h2 ∈ V (H2).
It follows that dG⊛H((g, h), (g′, h′)) ≤ 3. Let (g′, h′) be an arbitrary vertex from
V (G1) × V (H2). If g′ is not a universal vertex of G1, then there is a non-edge
g′g′′ /∈ E(G1). It follows that there exists a path (g, h)(g′′, h1)(g′, h′) for h1 ∈ NH1(h)
and dG⊛H((g, h), (g′, h′)) ≤ 2. Otherwise, g′ is a universal vertex of G1. There ex-
ists a path (g, h)(g1, h1)(g′1, h2)(g
′, h′) for h1 ∈ NH1(h) and h2 ∈ NH2(h′). Again
dG⊛H((g, h), (g
′, h′)) ≤ 3. Suppose now that H1 ∼= K1. It follows that H2 ∼= Kt,
t ≥ 2. For (g, h) and (g′, h′) ∈ V (G2)×V (H1) the Condition 1 is fulfilled. With the path
(g, h)(g′, h2)(g1, h)(g
′
1, h2)(g
′, h′) for h2 ∈ V (H2) we get that dG⊛H((g, h), (g′, h′)) ≤
4. Let (g′, h′) be an arbitrary vertex from V (G1) × V (H2). If g′ is not a universal ver-
tex of G1, then there is a non-edge g′g′′ /∈ E(G1). It follows that there exists a path
(g, h)(g2, h
′)(g′′, h)(g′, h′) for g2 ∈ V (G2) and we have dG⊛H((g, h), (g′, h′)) ≤ 3. Oth-
10 Art Discrete Appl. Math. 6 (2023) #P2.13
erwise, g′ is a universal vertex of G1 and the Condition 2 is fulfilled for (g, h) and (g′, h′).
With the path (g, h)(g2, h′)(g1, h)(g′1, h2)(g
′, h′) for g2 ∈ V (G2) and h2 ∈ NH2(h′) we
get that dG⊛H((g, h), (g′, h′)) ≤ 4. Finally suppose that H2 ∼= K1 = h2. It follows
that H1 ∼= Kt, t ≥ 2. For each vertex (g′, h′) ∈ V (G2) × V (H1) there exists a path
(g, h)(g1, h1)(g
′
1, h2)(g
′, h′) for h1 ∈ NH1(h). It follows that dG⊛H((g, h), (g′, h′)) ≤ 3.
Let (g′, h′) be an arbitrary vertex from V (G1) × V (H2). If g′ is not a universal ver-
tex of G1, then there is a non-edge g′g′′ /∈ E(G1). It follows that there exists a path
(g, h)(g′′, h1)(g
′, h′) for h1 ∈ NH1(h) and dG⊛H((g, h), (g′, h′)) ≤ 2. Otherwise, g′ is
a universal vertex of G1 and the Condition 3 is fulfilled for (g, h) and (g′, h′). With the
path (g, h)(g1, h1)(g′1, h
′)(g2, h)(g
′, h′) for h1 ∈ NH1(h) and g2 ∈ V (G2) we get that
dG⊛H((g, h), (g
′, h′)) ≤ 4. The case where only H1 is not a complete graph is symmetric.
For the equivalence notice from this proof until now, that if Conditions 1 or 2 or 3
are not fulfilled, then eccG⊛H((g, h)) ≤ 3 ̸= 4, which proves one implication of the
equivalence. For the other implication, suppose that Conditions 1 or 2 or 3 are fulfilled
for (g, h) and (g′, h′). By the symmetry we may assume that H ∼= K1 ∪ Kt, t ≥ 2.
Suppose first that Condition 1 holds. We will show that dG⊛H((g, h), (g′, h′)) ≥ 4. The
neighborhood of (g, h) in DcD product G⊛H is V (G2)× V (H2), since H1 ∼= K1 and g
is a universal vertex of G1. Similarly, the neighborhood of (g′, h′) in DcD product G⊛H
is V (G1) × V (H2), since H1 ∼= K1 and g′ is a universal vertex of G2. There are no
edges between vertex sets V (G1)× V (H2) and V (G2)× V (H2), since H2 ∼= Kt. Hence
dG⊛H((g, h), (g
′, h′)) ≥ 4 and it follows that eccG⊛H((g, h)) = dG⊛H((g, h), (g′, h′)) =
4. Next, suppose that Condition 2 holds. Again, we will show that dG⊛H((g, h), (g′, h′)) ≥
4. The neighborhood of (g, h) in DcD product G⊛H is V (G2)×V (H2), since H1 ∼= K1
and g is a universal vertex of G1. The neighborhood of (g′, h′) in DcD product G ⊛H is
a subset of (V (G1) × V (H2)) ∪ (V (G2) × V (H1)), since H2 ∼= Kt and g′ is a universal
vertex of G1. There are no edges between sets V (G2)× V (H2) and (V (G1)× V (H2)) ∪
(V (G2) × V (H1)), since G2 ∼= Ks and H2 ∼= Kt. Hence dG⊛H((g, h), (g′, h′)) ≥ 4
and it follows that eccG⊛H((g, h)) = dG⊛H((g, h), (g′, h′)) = 4. Finally, suppose that
Condition 3 holds. We will show that dG⊛H((g, h), (g′, h′)) ≥ 4. The neighborhood of
(g, h) in DcD product G⊛H is a subset of (V (G1)×V (H1))∪ (V (G2)×V (H2)), since
H1 ∼= Kt and g is a universal vertex of G1. The neighborhood of (g′, h′) in DcD product
G⊛H is V (G2)×V (H1), since H2 ∼= K1 and g′ is a universal vertex of G1. There are no
edges between vertex sets (V (G1)× V (H1)) ∪ (V (G2)× V (H2)) and V (G2)× V (H1),
since G2 ∼= Ks and H1 ∼= Kt. Hence dG⊛H((g, h), (g′, h′)) ≥ 4 and eccG⊛H((g, h)) =
dG⊛H((g, h), (g
′, h′)) = 4 follows.
Next we study the eccentricity of the vertices of DcD products where one factor is
connected and the other has at least three components. We are not studying cases where
one factor is isomorphic to Kn, n ≥ 3, since this is already covered by (2.5). In this case
Condition 4 describes the only situation where the distance exceeds three.
Theorem 4.4. Let G and H be graphs such that G⊛H is connected. If one of them has at
least three components but is not isomorphic to Kn, n ≥ 3, and the other is connected, then
eccG⊛H((g, h)) ≤ 4. Moreover, we have eccG⊛H((g, h)) = dG⊛H((g, h), (g′, h′)) = 4 if
and only if Condition 4 is fulfilled.
A. Kelenc et al.: Distance formula for direct-co-direct product in the case of disconnected factors 11
Proof. Without loss of generality suppose that H is connected, G = G1 ∪G2 ∪ · · · ∪Gk,
k ≥ 3, and g ∈ V (G1). In the first part of the proof we split two main cases regarding the
neighborhood of the vertex h.
Case 1. Vertex h ∈ V (H) is not a universal vertex.
For any vertex (g′, h′), where g′ ∈ V (G) − V (G1) and h′ ∈ NH [h] we have an edge
between (g, h) and (g′, h′) in DcD product G ⊛ H . Next, suppose that h′ = h and g′ is
an arbitrary vertex from V (G) different than g. We select h′′ ∈ NH [h] arbitrarily. We can
choose vertex g′′ such that it is not in the same connected component as g and g′, since
we have at least three components in G. It follows that (g, h)(g′′, h′′)(g′, h′) is a path
of length two in G ⊛ H and dG⊛H((g, h), (g′, h′)) = 2. For any vertex (g′, h′), where
g′ ∈ V (G1) and h′ ∈ NH [h] there exists a path (g, h)(g′′, h′)(g′′′, h)(g′, h′), for arbitrary
vertices g′′ ∈ V (G2) and g′′′ ∈ V (G3). Hence, dG⊛H((g, h), (g′, h′)) ≤ 3.
It remains to check the vertices (g′, h′) where h′ ∈ NH(h) and g′ is an arbitrary vertex
from V (G). If h′ is not adjacent with at least one vertex h′′ from the set NH [h], then there
exists a path (g, h)(g′′, h′′)(g′, h′), where g′′ is a vertex from different component than g
and g′. Otherwise, h′ is adjacent with all the vertices from NH [h]. If g′ is not an isolated
vertex in graph G, then there exists g′′ ∈ V (G), such that g′g′′ ∈ E(G). If g′ is addition-
ally not from V (G1), then there exists a path (g, h)(g′′, h′′)(g′, h′), for an arbitrary vertex
h′′ ∈ NH [h]. Otherwise, g′ ∈ V (G1) and there exists a walk (g, h)(g2, h′′)(g′′, h)(g′, h′),
where g2 ∈ V (G) − V (G1) and h′′ ∈ NH [h]. So let g′ be an isolated vertex. In this
case h′ is not a universal vertex by the fact that G ⊛ H is a connected graph. Therefore,
there exists h′′ ∈ NH(h) such that h′h′′ /∈ E(H). Recall also that G ≇ Kn and there
exist g′′ and g′′′ such that g′′g′′′ ∈ E(G). Suppose that g′ = g. If h′′h′′′ ∈ E(H),
for some h′′′ ∈ NH [h], then there exists a path (g, h)(g′′′, h′′′)(g0, h′′)(g′, h′) where
g0 is from different component than g′. Otherwise, h′′ is not adjacent to h′′′ for ev-
ery vertex h′′′ ∈ NH [h] and there exists a path (g, h)(gx, h′′′)(g′′, h′′)(g′, h′), where
gx ∈ V (G) is neither from connected component that contains g′′ nor from G1. Sup-
pose that g′ ̸= g. If h′′h′′′ /∈ E(H), for some h′′′ ∈ NH [h], then there exists a
path (g, h)(g′, h′′′)(g′′, h′′)(g′, h′). Otherwise, h′′ is adjacent to every h′′′ ∈ NH [h]. If
g′′′ /∈ NG[g], then there exists a path (g, h)(g′′′, h′′′)(g′′, h′′)(g′, h′). If g′′′ ∈ NG(g),
then there exists a path (g, h)(g′′′, h′′)(g′, h′). If g′′′ = g, then there exists a path
(g, h)(g′′, h′′)(g′, h′). Therefore, for all vertices (g′, h′), where h′ ∈ NH(h) and g′ is
an arbitrary vertex from V (G), it holds that dG⊛H((g, h), (g′, h′)) ≤ 3.
Case 2. Vertex h is a universal vertex.
In this case none of the components of G is an isolated vertex by Theorem 2.1, since
graph G ⊛ H is connected. Let g′ ∈ V (G) − V (G1). If h′ is not a universal ver-
tex in graph H , then there exists a path (g, h)(g1, h1)(g′, h′), where g1 ∈ NG(g) and
h1h
′ /∈ E(H). If h′ is a universal vertex in H (it can also be h), then there exists a
path (g, h)(g1, h1)(g′′, h2)(g′, h′), where g1 ∈ NG(g), h1h2 /∈ E(H) and g′′ ∈ NG(g′).
Notice that such h1 and h2 exist, since H is not a complete graph by Theorem 2.1 as
G ⊛ H is connected. Next, let g′ ∈ V (G1). If h′ is not a universal vertex in H , then
there exists a walk (g, h)(g1, h′)(g2, h1)(g′, h′), where g1 ∈ NG(g), g2 ∈ V (G2) and
h1h
′ /∈ E(H). If h′ is a universal vertex in H different than h, then there can ap-
pear five different options with respect to g′. First, if g′ = g, then there exists a path
(g, h)(g1, h1)(g
′, h′), where g1 ∈ NG(g) and h1 an arbitrary vertex different that h and
h′. Second, if g′ ∈ NG(g), then (g, h) and (g′, h′) are adjacent. Third, if dG(g, g′) = 2,
then there exists a path (g, h)(g1, h1)(g′, h′), where g1 ∈ NG(g) ∩ NG(g′) and h1 an
12 Art Discrete Appl. Math. 6 (2023) #P2.13
arbitrary vertex different that h and h′. Fourth, if dG(g, g′) = 3, then there exists a
path (g, h)(g1, h′)(g2, h)(g′, h′), where g1 ∈ NG(g) and g2 ∈ NG(g′), g1g2 ∈ E(G),
are two mid-vertices from some shortest path between g and g′. Fifth, if dG(g, g′) ≥ 4,
then there exists a path (g, h)(g1, h1)(g2, h2)(g′, h′), where g1 ∈ NG(g), h1h2 /∈ E(H)
and g2 ∈ NG(g′) (notice that g1g2 /∈ E(G)). Therefore, for all vertices (g′, h′) ∈
V (G ⊛ H) − (V (G1)× {h}) it holds that dG⊛H((g, h), (g′, h′)) ≤ 3. It remains to
check the vertices (g′, h′), where g′ ∈ V (G1) and h′ = h. If there exists an edge
hxhy ∈ E(H), where hx ̸= h and hy ̸= h (with this H ≇ K1,t, t ≥ 2), then there
can appear four different options with respect to g′. First, if g′ ∈ NG(g), then there
exists a path (g, h)(g′, hx)(g, hy)(g′, h′). Second, if dG(g, g′) = 2, then there exists a
path (g, h)(g1, hx)(g′, h′), where g1 ∈ NG(g) ∩ NG(g′). Third, if dG(g, g′) = 3, then
there exists a path (g, h)(g1, hx)(g2, hy)(g′, h′), where g1 ∈ NG(g) and g2 ∈ NG(g′),
g1g2 ∈ E(G), are two mid-vertices from some shortest path between g and g′. Fourth, if
dG(g, g
′) ≥ 4, then there exists a path (g, h)(g1, h1)(g2, h2)(g′, h′), where g1 ∈ NG(g),
h1h2 /∈ E(H) (recall that H ≇ Kp as G ⊛ H is connected) and g2 ∈ NG(g′). Again,
for all vertices (g′, h′) it holds that dG⊛H((g, h), (g′, h′)) ≤ 3. We are left with the case
that H ∼= K1,t, t ≥ 2. If dG(g, g′) = 2 or dG(g, g′) ≥ 4, then we can construct the same
paths than before, since they are not dependent on the edge hxhy . Let g′ ∈ V (G1), such
that dG(g, g′) = 3 or dG(g, g′) = 1. If there exists a vertex g1 ∈ NG(g) such that g1g′′ /∈
E(G), for some g′′ ∈ NG(g′), then there exists a path (g, h)(g1, h1)(g′′, h2)(g′, h′), where
h1 and h2 are different leaves of H , and dG⊛H((g, h), (g′, h′)) ≤ 3. Otherwise, for ev-
ery g1 ∈ NG(g) it holds that NG(g′) ⊆ NG(g1) and the Condition 4 is fulfilled. There
exists a path (g, h)(g1, h1)(g2, h2)(g′′, h1)(g′, h′), where h1 and h2 are different leaves
of the star graph H , g1 ∈ NG(g), g2 ∈ V (G2) and g′′ ∈ NG(g′). It follows that
dG⊛H((g, h), (g
′, h′)) ≤ 4 and Case 2 is completed.
For the equivalence notice from this proof until now, that if Condition 4 is not fulfilled,
then eccG⊛H((g, h)) ≤ 3 ̸= 4, which proves one implication of the equivalence. For the
other implication, suppose that Condition 4 is fulfilled for (g, h) and (g′, h′). By the sym-
metry we may assume that H ∼= K1,t, t ≥ 2. We will show that dG⊛H((g, h), (g′, h′)) ≥ 4.
The neighborhood of (g, h) in DcD product G⊛H is NG(g)× (V (H)− {h}), since h is
a universal vertex in H . Similarly, the neighborhood of (g′, h′) in DcD product G ⊛H is
NG(g
′)× (V (H)− {h}), since h′ is a universal vertex in H . There are no edges between
sets NG(g)× (V (H)− {h}) and NG(g′)× (V (H)− {h}), since all vertices g1 ∈ NG(g)
are adjacent to all neighbors g′′ of the vertex g′ in the graph G and there are no edges be-
tween vertices from (V (H)−{h}) in H . Hence dG⊛H((g, h), (g′, h′)) ≥ 4 and it follows
that eccG⊛H((g, h)) = dG⊛H((g, h), (g′, h′)) = 4.
By a careful reading of Case 2 from the above proof, one can observe that we did not
use three or more components of G when constructing the desired paths in G⊛H . A fact
that will come handy in the proof of the next theorem.
Theorem 4.5. Let G and H be graphs not isomorphic to K2 nor to K2 and such that
G ⊛H is connected. If one of them has two components and the other is connected, then
eccG⊛H((g, h)) ≤ 5. Moreover, we have eccG⊛H((g, h)) = dG⊛H((g, h), (g′, h′)) =
5 if and only if Condition 12 holds. Furthermore, we have eccG⊛H((g, h)) =
dG⊛H((g, h), (g
′, h′)) = 4 if and only if Condition 4 or 5 or 6 or 7 or 8 or 9 or 10 or 11
holds.
A. Kelenc et al.: Distance formula for direct-co-direct product in the case of disconnected factors 13
Proof. We may assume that G has two components G1 and G2 and that H is connected.
Let g ∈ V (G) and h ∈ V (H) be arbitrary. By symmetry we may further assume that g ∈
V (G1). We split the proof into three parts with respect weather G1 or G2 are isomorphic
to K1 or not. Notice that the case G1 ∼= K1 and G2 ∼= K1 yields a contradiction with the
assumption.
Case 1. G1 ≇ K1 and G2 ≇ K1.
This is the only case when H can have a universal vertex, say that h is such. As it is
mentioned in a comment before this theorem, we can use the same proof as in Case 2
of Theorem 4.4 including Condition 4. Hence we may assume that h is not universal
and with this NH [h] is not an empty set. Vertices from A1 = NG(g) × NH(h), from
A2 = NG1 [g] × NH [h] and from A3 = V (G2) × NH [h] are adjacent to (g, h). Notice,
that A2 can be empty when g is a universal vertex of G1. So, assume first that g is not
a universal vertex of G1. Vertices from A4 = V (G2) × {h} are adjacent to all vertices
of A2 by co-direct edges and we have dG⊛H((g, h), (a, h)) = 2 for every a ∈ V (G2).
Every vertex a from V (G2) has a neighbor a′ in G2 because G2 ≇ K1. But then we have
a direct edge (a, b)(a′, h) for any b ∈ NH(h). Hence, we have dG⊛H((g, h), (a, b)) ≤ 3
for any (a, b) ∈ V (G2) × NH(h) and we are done with vertices from V (G2) × V (H).
Further every vertex (c, b′) ∈ NG[g] × NH [h] is adjacent to every vertex of A4, which
gives dG⊛H((g, h), (c, b′)) ≤ 3. Vertices from A5 = (V (G1) − {g}) × {h} are adjacent
to all vertices of A3 by co-direct edges and we have dG⊛H((g, h), (c′, h)) = 2 for any
(c′, h) ∈ A5. Every vertex c′′ ∈ NG[g] has a neighbor c′ ∈ V (G1) − {g}, say that c′ is a
neighbor of c′′ on a shortest path between g and c′′. But then (c′′, b)(c′, h) is a direct edge
for any b ∈ NH(h) where (c′, h) ∈ A5. This means that dG⊛H((g, h), (c′′, b)) ≤ 3 for any
(c′′, b) ∈ NG[g]×NH(h). Finally, a vertex (g, b), b ∈ NH(h), is adjacent to every vertex
from NG(g) × {h} ⊆ A5 by a direct edge. Again we have dG⊛H((g, h), (g, b)) ≤ 3 for
any (g, b) ∈ {g} ×NH(h) and we are done when g is not universal in G1.
Let now g be a universal vertex of G1 and with this A2 = ∅. Every vertex from A3 is
adjacent to every vertex (g1, h) ∈ NG1(g)× {h} and we have dG⊛H((g, h), (g1, h)) = 2.
Further, (g1, h) ∈ NG1(g)× {h} is adjacent to every vertex from (g, h1) ∈ {g} ×NH(h)
and dG⊛H((g, h), (g, h1)) ≤ 3. In what follows we need the following notation. Let
NH(h) = B
′
1 ∪ B′′1 where B′1 contains all satellite vertices of h and B′′1 = NH(h) − B′1.
Notice that vertices from B′1 have no neighbors in NH [h] and can be empty set while
B′′1 ̸= ∅ since h is not universal in H . Also let B2 = {x ∈ V (H) : dH(h, x) = 2}
and B3 = {x ∈ V (H) : dH(h, x) ≥ 3}. Let h1 ∈ B′′1 be a common neighbor of
h2 ∈ B2 and h. For g′ ∈ V (G2) we have dG⊛H((g, h), (g′, h1)) = 2 by the path
(g, h)(g2, h2)(g
′, h1) where g′g2 ∈ E(G2) and we are done with V (G2) × B′′1 . Fur-
ther, we have dG⊛H((g, h), (g′, h)) ≤ 3 by the path (g, h)(g′, h2)(g2, h1)(g′, h) where
again g′g2 ∈ E(G2) and we are done with V (G2) × {h}. For (g1, h3) ∈ V (G1) × B3
a path (g, h)(g2, h2)(g3, h1)(g1, h3) yields dG⊛H((g, h), (g1, h3)) ≤ 3 where g2g3 ∈
E(G2). Let h2 ∈ B2 and let h1 be a common neighbor of h and h2. A path P =
(g, h)(g1, h1)(g, h2), g1 ∈ V (G1) shows that dG⊛H((g, h), (g, h2)) = 2 and we are done
with {g}×B2. We can extend P to a vertex (g2, h′) ∈ V (G2)×B′1 by a co-direct edge since
vertices from B′1 have no neighbors in B2. Hence, dG⊛H((g, h), (g1, h
′)) ≤ 3 and this con-
cludes V (G2) × B′1. We are left with the vertices from NG1(g) × B2. If g1 ∈ NG1(g)
has a neighbor g4 ∈ NG1(g), then we have a path (g, h)(g4, h1)(g1, h2) where hh1h2 is a
shortest path in H and dG⊛H((g, h), (g1, h2)) = 2 follows for (g1, h2) ∈ NG1(g) × B2.
So, we may assume that g is the only neighbor of g1 ∈ NG1(g). If |V (G1)| > 2,
14 Art Discrete Appl. Math. 6 (2023) #P2.13
then we have a path (g, h)(g2, h2)(g4, h)(g1, h2) for h2 ∈ B2, g2 ∈ V (G2) and g4 ∈
V (G1) − {g, g1}. Therefore, dG⊛H((g, h), (g1, h2)) ≤ 3 for (g1, h2) ∈ NG1(g) × B2.
So, let finally |V (G1)| = 2 and with this G1 ∼= K2 = gg1. If there exists two non-
adjacent vertices g3, g4 ∈ V (G2), then (g, h)(g3, h2)(g4, h)(g1, h2) is a path and we have
dG⊛H((g, h), (g1, h2)) ≤ 3. So, we may further assume that G2 ∼= Kt for some t ≥ 2. If
there exists h3 ∈ B3, then a path (g, h)(g2, h3)(g, h1)(g1, h2) where g2 ∈ V (G) and h1 is
a common neighbor of h and h2 ∈ B2 assures that dG⊛H((g, h), (g1, h2)) ≤ 3. So, we may
assume that B3 = ∅ and with this eccH(h) = 2. Further, if there exist h′2 ∈ B2 − {h2},
then (g, h)(g1, h1)(g, h′2)(g1, h2) is a path when h2h
′
2 ∈ E(H) where h1 is a common
neighbor of h and h′2. Thus, dG⊛H((g, h), (g1, h2)) ≤ 3 again. If h2h′2 /∈ E(H),
then the path (g, h)(g2, h′2)(g1, h2), for g2 ∈ V (G2), forces dG⊛H((g, h), (g1, h2)) = 2.
So, let B2 = {h2} and every vertex from B′′1 is adjacent to h2. If some h1 ∈ B′′1 is
adjacent to h′1 ∈ NH(h) − {h1}, then (g, h)(g1, h′1)(g, h1)(g1, h2) is a path and we
have dG⊛H((g, h), (g1, h2)) ≤ 3 again. So, we are left with a situation where there
are no edges between vertices from B′1 and B
′′
1 and no edges in H[B
′′
1 ]. If there exist
h′1 ∈ B′1, then h1h′1 /∈ E(H) for h1 ∈ B′′1 and (g, h)(g1, h1)(g2, h′1)(g1, h2) is a path
for g2 ∈ V (G2). This means that dG⊛H((g, h), (g1, h2)) ≤ 3. We end with assump-
tion that B′1 = ∅. But then H ∼= K2,p for some p ≥ 1 and Condition 5 is fulfilled for
(x, y) = (g, h) and (x′, y′) = (g1, h2). We have dG⊛H((g, h), (g1, h2)) ≤ 4 by the path
(g, h)(g2, h2)(g1, h)(g, h1)(g1, h2) where g2 ∈ V (G2) and h1 ∈ B′′1 .
Case 2. G1 ≇ K1 and G2 ∼= K1.
Let G2 = a. The proof of this case is in the beginning very similar as the first paragraph
of the previous case with two exceptions. Firstly, h is not a universal vertex now by Theo-
rem 2.1 and we can ignore the first part of first paragraph of Case 1. Secondly, when g is
not a universal vertex of G1 is the sentence: ”Every vertex a from V (G2) has a neighbor
a′ in G2 because G2 ≇ K1”. Now such an a′ does not exists and we need to take care of
all vertices from V (G2) × NH(h). Since there are no universal vertices in H there exists
b′ for every b ∈ NH(h) such that b′ is not adjacent to b. Now (a, b) is adjacent to (c, b′) by
a co-direct edge, where c ∈ NG(g) when b′ ∈ NH(h) or c ∈ NG[g] when b′ ∈ NH [h]. In
first option (c, b) belongs to A1 and in the second option it belongs to A2 (as defined in the
previous case). Hence, dG⊛H((g, h), (a, b)) = 2 and we are done if g is not universal in
G1.
There are more differences when g is a universal vertex of G1 and we write all
the details. Sets A1, A3, B′1, B
′′
1 , B2 and B3 have the same meaning as in the Case
1. Every vertex from A3 is adjacent to every vertex (g1, h) ∈ NG1(g) × {h} and we
have dG⊛H((g, h), (g1, h)) = 2. Further, (g1, h) ∈ NG1(g) × {h} is adjacent to ev-
ery vertex from (g, h1) ∈ {g} × NH(h) and dG⊛H((g, h), (g, h1)) ≤ 3. If g1, g2 ∈
V (G1) are non-adjacent, then (g, h)(a, h2)(g2, h)(g1, h2) is a path for h2 ∈ NH [h]
and dG⊛H((g, h), (g1, h2)) ≤ 3 follows. In particular, if h2 ∈ B3 we have a path
(g, h)(g2, h1)(g1, h2) for h1 ∈ NH(h) and we have dG⊛H((g, h), (g1, h2)) = 2. Last path
can be extended to any vertex (a, h1) for h1 ∈ B′′1 and we have dG⊛H((g, h), (a, h1)) ≤ 3
for every (a, h1) ∈ {a} × B′′1 when G1 is not complete and B3 ̸= ∅. If B3 = ∅,
then every vertex h1 ∈ B′′1 is non-adjacent to some h′1 because H has no universal
vertices. If h′1 ∈ NH(h), then the path (g, h)(g1, h′1)(a, h1) for g1 ∈ NG(g) gives
dG⊛H((g, h), (a, h1)) = 2. If h′1 ∈ NH [h], then we have dG⊛H((g, h), (a, h1)) ≤ 3
by the path (g, h)(g1, h′′1)(g, h
′
1)(a, h1) for g1 ∈ NG(g) and h′′1 is a common neighbor of
h and h′1. Hence, vertices from {a} × B′′1 remains open only when G1 is complete and
A. Kelenc et al.: Distance formula for direct-co-direct product in the case of disconnected factors 15
B3 ̸= ∅. Let g′ be a universal vertex of G1 and let g1 be a neighbor of g′. Notice that g′
can be equal to g. For h2 ∈ B2 we have a path P = (g, h)(g1, h1)(g′, h2) for a common
neighbor h1 of h and h2 which gives dG⊛H((g, h), (g′, h2)) = 2 for every universal vertex
g′ of G1 when |V (G1)| > 2 and only for g when G1 ∼= K2. Path P can be extended to
(g, h)(g1, h1)(g
′, h2)(a, h
′) for h′ ∈ {h} ∪ B′1 and we have dG⊛H((g, h), (a, h′)) ≤ 3.
For h3 ∈ B3 with a neighbor h2 ∈ B2 we have a path (g, h)(g′, h1)(g1, h2)(g′, h3)
where h1 is a common neighbor of h and h2. Notice that if G1 ∼= K2, then g1 = g
and vertex (g, h3) is still open. Hence, dG⊛H((g, h), (g′, h3)) ≤ 3 for every vertex h3 at
distance three from h and every universal vertex g′ of G1, with the exception of g when
G1 ∼= K2. If dH(h, h4) ≥ 4, then we have a path (g, h)(a, h2)(g′, h4) where h2 ∈ B2.
This gives dG⊛H((g, h), (g′, h4)) = 2 for every universal vertex g′ of G1 and h4 ∈ B3
with dH(h, h4) ≥ 4.
At this stage we still need to check the vertices from {a} × B′′1 when B3 ̸= ∅ and
G1 ∼= Kt for some t ≥ 2 and in addition when G1 ∼= K2 = gg′ we need to take
care also for (g, h3) and (g′, h2) where dH(h, h3) = 3 and h2 ∈ B2. Suppose first
that there exist h4 ∈ B3 with dH(h, h4) ≥ 4. The path (g, h)(a, h4)(g′, h2) shows that
dG⊛H((g, h), (g
′, h2)) = 2 for every h2 ∈ B2. Last path can be extended to (g, h3) and
we have dG⊛H((g, h), (g, h3)) ≤ 3 for every h3 ∈ B3 with dH(h, h3) = 3 since h3 has a
neighbor in B2. In addition we have a path (g, h)(a, h2)(g, h4)(a, h1) for every h1 ∈ B′′1
where h2 ∈ B2 and dG⊛H((g, h), (a, h1)) ≤ 3 follows. Therefore, we may assume in the
rest of this case that all vertices from B3 are at distance three to h.
First we concentrate on vertices from {g′} × B2 when G1 ∼= K2 = gg′. If there
exist h3 ∈ B3, then we have a path (g, h)(a, h3)(g, h1)(g′, h2) where h1 ∈ B′′1 is a
neighbor of h2 ∈ B2 and dG⊛H((g, h), (g′, h2)) ≤ 3 follows. So, we may assume
that B3 = ∅. Let h2, h′2 ∈ B2 be different vertices. If they are non-adjacent, then
the path (g, h)(a, h′2)(g
′, h2) yields dG⊛H((g, h), (g′, h2)) = 2. If h2h′2 ∈ E(H),
then the path (g, h)(g′, h1)(g, h′2)(g
′, h2), where h1 is a common neighbor of h and
h′2, shows that dG⊛H((g, h), (g
′, h2)) ≤ 3. It remains that B2 = {h2}. Since
G ⊛ H is connected, H contains no universal vertices by Theorem 2.1. If h1 ∈ B′1
is not adjacent to h′1 ∈ NH(h), then we have dG⊛H((g, h), (g′, h2)) ≤ 3 by the path
(g, h)(g′, h′1)(a, h1)(g
′, h2) where h1h2 /∈ E(H) as h1 ∈ B′1. Hence, next h1 ∈ B′1 is
adjacent to all the vertices in NH(h) and with this also to a neighbor h′2 ∈ B′′1 of h2.
This means that dG⊛H((g, h), (g′, h2)) ≤ 3 by the path (g, h)(g′, h1)(g, h′2)(g′, h2). Fi-
nally, we may assume that B′1 = ∅. If there exists h1h′1 ∈ E(H[B′′1 ]), then the path
(g, h)(g′, h1)(g, h
′
1)(g
′, h2) shows that dG⊛H((g, h), (g′, h2)) ≤ 3. If H[B′′1 ] is without
edges, then H ∼= K2,p, p ≥ 1, and Condition 5 holds. We have dG⊛H((g, h), (g′, h2)) ≤ 4
by the path (g, h)(a, h2)(g′, h)(g, h1)(g′, h2) for h1 ∈ B′′1 .
Next we deal with an arbitrary vertex (g, h3) from {g} × B3 when G1 ∼= K2 =
gg′. If there exist two non-adjacent vertices h1, h′1 from NH(h), then we have the
path (g, h)(g′, h1)(a, h′1)(g, h3) and dG⊛H((g, h), (g, h3)) ≤ 3 holds. So, we may as-
sume that H[NH [h]] is a complete subgraph. If h3 is non-adjacent with some h′3 ∈
NH [h]−{h3}, then dG⊛H((g, h), (g, h3)) = 2 follows from the path (g, h)(a, h′3)(g, h3).
Therefore, we suppose that h3 is a universal vertex of H[NH [h]]. If h′3, h
′′
3 are
non-adjacent vertices of NH [h], then the path (g, h)(a, h′3)(g
′, h′′3)(g, h3) ensures that
dG⊛H((g, h), (g, h3)) ≤ 3. Hence, we can also assume that H[NH [h]] is a complete
subgraph of H . With this Condition 6 holds and we have dG⊛H((g, h), (g, h3)) ≤ 4 by the
path (g, h)(a, h3)(g, h1)(g′, h2)(g, h3) for h2 ∈ B2 and his neighbor h1 ∈ B′′1 .
16 Art Discrete Appl. Math. 6 (2023) #P2.13
We end with vertices from {a} × B′′1 when B3 ̸= ∅ G1 ∼= Kt for some t ≥ 2. Let
(a, h1) ∈ {a} × B′′1 and let g1 be a neighbor of g in G1. If h1 is non-adjacent to some
h′1 ∈ NH(h)−{h1}, then dG⊛H((g, h), (a, h1)) = 2 by the path (g, h)(g1, h′1)(a, h1). So,
we may assume that h1 is a universal vertex of H[NH [h]]. If h1 is non-adjacent to some
h2 ∈ B2, then for a common neighbor h′1 of h and h2 the path (g, h)(g1, h′1)(g, h2)(a, h1)
gives dG⊛H((g, h), (a, h1)) ≤ 3. Hence, we may suppose that h1 is adjacent to all vertices
of B2. (Notice that B3 ̸= ∅ because otherwise h1 is a universal vertex of H which is not
possible.) If there exists h3 ∈ B3 that is not a universal vertex of H[NH [h]], that is h3
is non-adjacent to h2 ∈ NH [h] − {h3}, then we have a path (g, h)(a, h2)(g, h3)(a, h1)
and dG⊛H((g, h), (a, h1)) ≤ 3 follows. Finally, if every vertex from B3 is a universal
vertex in NH [h], then Condition 7 is fulfilled and we have dG⊛H((g, h), (a, h1)) ≤ 4 by
the path (g, h)(g1, h1)(g, h2)(g1, h3)(a, h1) where hh1h2h3 is a shortest path between h
and h3 ∈ B3 in the graph H .
Case 3. G1 ∼= K1 and G2 ≇ K1.
If there exists a universal vertex of H , then G⊛H is not connected by Theorem 2.1. Hence
H is without universal vertices and in particular eccH(h) ≥ 2. We partition V (H) into sets
B1 = NH(h), B2 = {x ∈ V (H) : dH(h, x) = 2}, B3 = {x ∈ V (H) : dH(h, x) = 3},
B4 = {x ∈ V (H) : dH(h, x) ≥ 4} and {h}. Further we partition B1 into B′1 that
contains all vertices that have no neighbor in B2, that is B′1 contains all satellite vertices
of h, and B′′1 = B1 − B′1. Clearly, B′1 can be empty, but B′′1 is non-empty because
eccH(h) ≥ 2. For any vertex h4 ∈ B4 with dH(h4, h) = 4 (if it exists) let hh1h2h3h4
be a shortest h, h4-path in H . Clearly that hi ∈ Bi for i ∈ {1, 2, 3, 4} (if it exists for
i ∈ {3, 4}). Notice that NG⊛H((g, h)) = V (G2) × (B2 ∪ B3 ∪ B4). Let g1g2 ∈ E(G2)
which exists since G2 ≇ K1. Every vertex (g1, h1) ∈ V (G2) × B′′1 is at distance two to
(g, h) since (g2, h2)(g1, h1) is a direct edge. Hence dG⊛H((g, h), (g1, h1)) = 2 for any
(g1, h1) ∈ V (G2) × B′′1 . In addition there is a path (g, h)(g1, h2)(g2, h1)(g1, h) which
means that dG⊛H((g, h), (g1, h)) ≤ 3 for any (g1, h) ∈ V (G2) × {h}. Also every vertex
(g, h0), h0 ∈ B′1 is adjacent to (g1, h2) by a co-direct edge and dG⊛H((g, h), (g, h0)) = 2
for any (g, h0) ∈ {g} ×B′1. A path (g, h)(g2, h2)(g1, h1)(g, h∗) for any h∗ ∈ B3 ∪B4 (if
it exists) implies that dG⊛H((g, h), (g, h∗)) ≤ 3 for any (g, h∗) ∈ {g}× (B3 ∪B4). So, in
what follows we only need to consider vertices from V (G2)×B′1 and {g} × (B′′1 ∪B2).
To end this case we need further to distinguish the options when G2 is complete or
not. Suppose first that G2 ≇ Kp and let g3 and g4 be non-adjacent vertices of G2. There
exist a path (g, h)(g3, h2)(g4, h)(g, h2) and for any vertex (g, h2) ∈ {g} × B2 we have
dG⊛H((g, h), (g, h2)) ≤ 3. Let next h0 ∈ B′1. A path (g, h)(g3, h2)(g4, h0) assures that
dG⊛H((g, h), (g4, h0)) ≤ 2 for any (g4, h0) ∈ V (G2) × B′1 where g4 is not a universal
vertex of G2. If g5 is a universal vertex of G2, then we have dG⊛H((g, h), (g5, h0)) ≤ 3
by the path (g, h)(g3, h2)(g4, h)(g5, h0) where the last edge is a direct one since g5 is
universal and h0 is adjacent to h. To end with G2 ≇ Kp let h1 ∈ B′′1 . As mentioned
before, H is without universal vertices and also h1 is not universal. If B3 ̸= ∅, then
dG⊛H((g, h), (g, h1)) = 2 by the path (g, h)(g1, h+)(g, h1) for any h+ ∈ B3. If B3 = ∅,
then h1 is not adjacent to some h′2 ∈ B2 or to some h′1 ∈ B1, since it is not universal
vertex in graph H . For the first option we have a path (g, h)(g1, h′2)(g, h1) and for the
second option there exists a path (g, h)(g1, h′2)(g2, h
′
1)(g, h1) when h
′
1 ∈ B′′1 and h′2 ∈ B2
is a neighbor of h′1 or a path (g, h)(g3, h2)(g4, h
′
1)(g, h1) when h
′
1 ∈ B′1. In all cases we
have dG⊛H((g, h), (g, h1)) ≤ 3 and we are done when G2 ≇ Kp.
A. Kelenc et al.: Distance formula for direct-co-direct product in the case of disconnected factors 17
We continue with G2 ∼= Kp, p ≥ 2. If there exists h4 ∈ B4, then we have
a path (g, h)(g1, h4)(g, h∗) for any g1 ∈ V (G2) and h∗ ∈ B′′1 ∪ B2, which means
that dG⊛H((g, h), (g, h∗)) = 2 and we are done with vertices from {g} × (B′′1 ∪ B2).
Similar there exists a path (g, h)(g1, h2)(g, h4)(g1, h0) that consist only of co-direct
edges and where g1 ∈ V (G2) and h0 ∈ B′1 are arbitrary and h2 ∈ B2. Hence,
dG⊛H((g, h), (g1, h0)) ≤ 3 for any (g1, h0) ∈ V (G2)×B′1.
Next we may assume that B4 = ∅ and with this 2 ≤ eccH(h) ≤ 3 because
h is not universal in H . Let first eccH(h) = 3 and there exists h3 ∈ B3. For
(g, h1) ∈ {g} × B′′1 we have a path (g, h)(g1, h3)(g, h1) for g1 ∈ V (G2) and we have
dG⊛H((g, h), (g, h1)) = 2 for any (g, h1) ∈ {g} × B′′1 . Let now (g, h2) ∈ {g} × B2. If
h2 is not adjacent to some h0 ∈ B2 ∪ B3, h0 ̸= h2, then a path (g, h)(g1, h0)(g, h2)
where g1 ∈ V (G2) implies dG⊛H((g, h), (g, h2)) = 2. Furthermore, last path can
be extended to (g, h)(g1, h0)(g, h2)(g′, h′) where (g′, h′) ∈ V (G2) × B′1 and we have
dG⊛H((g, h), (g
′, h′)) ≤ 3 for any (g′, h′) ∈ V (G2) × B′1 when H[B2 ∪ B3] is not
a complete graph. Therefore we may assume that h2 is adjacent to all vertices from
(B2 ∪ B3) − {h2}. Moreover, if h2 is not adjacent to h′1 ∈ B′′1 , then we have a path
(g, h)(g1, h
′
2)(g2, h
′
1)(g, h2) where g1g2 ∈ E(G2), h′2 ∈ B2 and h′1h′2 ∈ E(H) ex-
ists because h′1 ∈ B′′1 . This means that dG⊛H((g, h), (g, h2)) ≤ 3. Finally, let h2 be
adjacent to every vertex from (B′′1 ∪ B2 ∪ B3) − {h2}. Notice that for g′ = g and
h′ = h2 Condition 8 is fulfilled and we have dG⊛H((g, h), (g′, h′)) ≤ 4 by the path
(g, h)(g1, h2)(g2, h1)(g1, h)(g
′, h′) where g1g2 ∈ E(G2) and h1 is a common neighbor of
h and h2 in H . We still need to take care of vertices in V (G2) × B′1 when H[B2 ∪ B3]
is a complete graph. Let (g′, h′) be arbitrary vertex from V (G2) × B′1. If h′ is not
adjacent to h′′ ∈ B1 − {h′}, then we have a path (g, h)(g1, h3)(g, h′′)(g′, h′) where
g1 ∈ V (G2) and h3 ∈ B3 and clearly dG⊛H((g, h), (g′, h′)) ≤ 3. So, we may assume also
that h′ is adjacent to every other vertex from B1 or in other words NH [h′] = NH [h].
We have dG⊛H((g, h), (g′, h′)) ≤ 3 by the path (g, h)(g′, h2)(g1, h1)(g′, h′) where
g1 ∈ V (G2) − {g′} and hh1h2 is a shortest path in H (notice that h1 is adjacent also
to h′ as NH [h′] = NH [h]).
We end this case with eccH(h) = 2 and with this B3 = ∅. If h2, h′2 ∈ B2 are not adja-
cent, then a path (g, h)(g1, h′2)(g, h2) where g1 ∈ V (G2) yields dG⊛H((g, h), (g, h2)) =
2. Last path can be extended to (g, h)(g1, h′2)(g, h2)(g
′, h′) for any (g′, h′) ∈ V (G2)×B′1
and we have dG⊛H((g, h), (g′, h′)) ≤ 3. Hence we are done with V (G2) × B′1 when
H[B2] is not complete. So let H[B2] be complete. Suppose that h′ is adjacent to some
h′1 ∈ B′′1 . We have dG⊛H((g, h), (g′, h′)) ≤ 3 by the path (g, h)(g′, h′2)(g1, h′1)(g′, h′)
where g′g1 ∈ E(G2) and h′2 ∈ B2 is a neighbor of h′1. Therefore, we can assume that h′ is
not adjacent to any vertex from B′′1 . Further suppose that h
′
1 ∈ B′′1 is not adjacent to some
h2 ∈ B2. A path (g, h)(g1, h2)(g, h′1)(g′, h′) shows that dG⊛H((g, h), (g′, h′)) ≤ 3 again.
Assume now that h′ is not adjacent to h′1 ∈ B′1−{h′}. We have dG⊛H((g, h), (g′, h′)) ≤ 3
by the path (g, h)(g′, h2)(g, h′1)(g
′, h′) where h2 ∈ B2. We are left with h′ is a satellite
of h that is adjacent to all the satellites of h, that is NH [h′] = B′1 ∪ {h}, H[B2] is a com-
plete subgraph and there exist all edges between B′′1 and B2. But then Condition 9 holds
for (g, h) and (g′, h′) and we have a path (g, h)(g1, h2)(g′, h1)(g1, h)(g′, h′) where g1 ∈
V (G2) − {g′} and hh1h2 is a shortest path in H . Therefore, dG⊛H((g, h), (g′, h′)) ≤ 4
and we are done with vertices from V (G2) × B′1. To end with vertices from {g} × B2
recall that we need to consider only those (g, h2) where h2 is adjacent to all vertices
from B2 − {h2}. If such a vertex h2 is not adjacent to h′1 ∈ B′′1 , then we have a
18 Art Discrete Appl. Math. 6 (2023) #P2.13
path (g, h)(g1, h′2)(g2, h
′
1)(g, h2) where g1g2 ∈ E(G2) and h′2 ∈ B2 is a neighbor of
h′1. This path forces dG⊛H((g, h), (g, h2)) ≤ 3. Hence, we may assume further that
NH [h
′] = B′′1 ∪ B2 for some h′ ∈ B2. But then Condition 10 is fulfilled for g′ = g and
we have dG⊛H((g, h), (g′, h′)) ≤ 4 by the path (g, h)(g1, h′)(g2, h′′)(g1, h)(g, h′) where
h′′ ∈ NH(h) ∩NH(h′) and g1g2 ∈ E(G2).
We finish with the vertices from {g} × B′′1 . Let (g′, h′) be an arbitrary vertex from
{g} × B′′1 . If h′ is not adjacent to some h2 ∈ B2, then dG⊛H((g, h), (g′, h′)) = 2 by
the path (g, h)(g1, h2)(g′, h′) for g1 ∈ V (G2). Similar, if h′ is not adjacent to some
h1 ∈ B′′1 −{h′}, then dG⊛H((g, h), (g′, h′)) ≤ 3 by the path (g, h)(g1, h2)(g2, h1)(g′, h′)
where g1g2 ∈ E(G2) and h2 ∈ B2 is a neighbor of h1. Therefore we may as-
sume that h′ is adjacent to all vertices from (B2 ∪ B′′1 ) − {h′}. If this happens,
notice that there exists h0 ∈ B′1 that is non-adjacent to h′ because H has no uni-
versal vertices by Theorem 2.1. In particular, h0 ∈ NH [h′] ⊆ B′1. Hence the
only edges with end-vertex (g′, h′) are now edges (gi, h0)(g′, h′) for gi ∈ V (G2).
If h0 is not adjacent to some h′0 ∈ B′1, then Condition 11 holds and we have
dG⊛H((g, h), (g
′, h′)) ≤ 4 by the path (g, h)(g1, h2)(g, h′0)(g1, h0)(g′, h′) where g1 ∈
V (G2) and h2 ∈ B2. Similar, if H[NH [h]] is not complete, that is h2, h′2 ∈ B2 are
not adjacent, then Condition 11 holds again and we have dG⊛H((g, h), (g′, h′)) ≤ 4 by
the path (g, h)(g1, h2)(g, h′2)(g1, h0)(g
′, h′) where g1 ∈ V (G2). Suppose now that there
exists an edge between between NH [h′] and B′′1 = NH(h) − B′1, say h3h4 ∈ E(H)
is such where h3 ∈ B′′1 and h4 ∈ NH [h′]. Again Condition 11 if fulfilled and we
have dG⊛H((g, h), (g′, h′)) ≤ 4 by the path (g, h)(g1, h2)(g2, h3)(g1, h4)(g′, h′) where
g1g2 ∈ E(G2) and h2 ∈ B2 is a neighbor of h3. Further, if Condition 12 holds, then we
have dG⊛H((g, h), (g′, h′)) ≤ 5 by the path (g, h)(g2, h2)(g1, h1)(g2, h)(g1, h0)(g′, h′)
where g1g2 ∈ E(G2) and hh1h2 is a shortest path in H . With this Case 3 is concluded.
For the first equivalence, notice that if Condition 12 does not hold, then
dG⊛H((g, h), (g
′, h′)) ≤ 4 by the proof so far, which gives one implication. For the sec-
ond implication assume that Condition 12 holds for G = X,H = Y, (g, h) = (x, y) and
(g′, h′) = (x′, y′). Clearly NG⊛H((g, h)) = V (G2) × B2 = D and NG⊛H((g′, h′)) =
V (G2)×NH [h′] = D′ ⊆ V (G2)×B′1. Clearly there are no edges between vertices of D
and vertices of D′ because G2 is complete and there are no edges between B′1 and B2 in H .
Vertices from D have their neighbors in {g}×B′1 and in V (G2)×B′′1 . In particular, there
is no edge between D and {g} × B2 because H[B2] = H[NH [h]] is a complete subgraph
of H . Also any vertex from D′ has no neighbor in V (G2) × B′′1 because there is no edge
between NH [h′] and B′′1 = NH(h) − B′1 and because G2 is complete. Finally, there are
no edges between any vertex from {g} × B′1 and D′ because every vertex from NY [y′]
is adjacent to every vertex from B′1. All together we have dG⊛H((g, h), (g
′, h′)) ≥ 5 and
equality follows which settles the first equivalence.
For the second equivalence, notice that the proof until now shows that when Condition 4
does not hold and Condition 5 does not hold and Condition 6 does not hold and Condition 7
does not hold and Condition 8 does not hold and Condition 9 does not hold and Condi-
tion 10 does not hold and Condition 11 does not hold, then dG⊛H((g, h), (g′, h′)) ≤ 3 or
dG⊛H((g, h), (g
′, h′)) = 5 and we are done with one implication. For the second implica-
tion assume first that Condition 4 holds. We can use the same arguments as in the proof of
Theorem 4.4.
A. Kelenc et al.: Distance formula for direct-co-direct product in the case of disconnected factors 19
Suppose now that Condition 5 holds for G = X,H = Y, (g, h) = (x, y) and (g′, h′) =
(x′, y′). We know already that dG⊛H((g, h), (g′, h′)) ≤ 4. Clearly NG⊛H((g, h)) =
(V (G2)×{h′})∪ ({g′}×NH(h)) = D and NG⊛H((g′, h′)) = (V (G2)×{h})∪ ({g}×
B′′1 ) = D
′. There are no edges between vertices from V (G2) × {h′} and D′ because G2
is complete or because h′ is adjacent to all vertices from B′′1 . Also, there are no edges
between vertices from {g′}×NH(h) and D′ because all vertices of B′′1 are adjacent to h or
because there are no edges in H[B′′1 ]. Hence, dG⊛H((g, h), (g
′, h′)) ≥ 4 and the equality
follows.
If Condition 6 holds for G = X,H = Y, (g, h) = (x, y) and (g′, h′) = (x′, y′), then
we have dG⊛H((g, h), (g′, h′)) ≤ 4 by the proof until now. For K2 = gg1 and K1 = a we
have NG⊛H((g, h)) = ({g1} × NH(h)) ∪ ({a} × NH [h]) = D and NG⊛H((g′, h′)) =
({a} × NH [h]) ∪ ({g1} × (NH [h] − {h′})) = D′. Vertices from D′ are not adjacent to
{g1} ×NH(h) because NH [h] is complete or because they have the same first coordinate
g1. Similar, vertices from D′ are not adjacent to {a} ×NH [h] because they have the same
first coordinate a or because NH [h] is complete. Therefore, dG⊛H((g, h), (g′, h′)) ≥ 4
and the equality follows.
Let now Condition 7 be true for G = X,H = Y, (g, h) = (x, y) and (g′, h′) = (x′, y′).
As usual dG⊛H((g, h), (g′, h′)) ≤ 4 by the proof until now. We have NG⊛H((g, h)) =
(NG1(g) ×NH(h)) ∪ ({g′} ×NH [h]) = D and NG⊛H((g′, h′)) = V (G1) × B3 = D′.
Vertices from D′ are not adjacent to NG1(g)×NH(h) because G1 is complete and vertices
of B3 are not adjacent with vertices from NH(h). Similar, vertices from D′ are not adjacent
to {g′} × NH [h] because every vertex from B3 is a universal vertex of H[NH [h]] and g′
is not adjacent to vertices of G1. Again dG⊛H((g, h), (g′, h′)) ≥ 4 and equality follows.
Next we assume that Condition 8 holds for G = X,H = Y, (g, h) = (x, y)
and (g′, h′) = (x′, y′). We know already that dG⊛H((g, h), (g′, h′)) ≤ 4. Clearly
NG⊛H((g, h)) = V (G2)× (B2 ∪ B3) = D and NG⊛H((g′, h′)) = V (G2)×NH(h′) =
D′ ⊆ V (G2)× ({h} ∪B′1). It is easy to see that there is no edge between a vertex from D
and a vertex from D′ because G2 is complete and there is no edge between B2 ∪ B3 and
{h} ∪B′1 in H . Hence, dG⊛H((g, h), (g′, h′)) ≥ 4 and equality follows.
Next we assume that Condition 9 holds for G = X,H = Y, (g, h) = (x, y)
and (g′, h′) = (x′, y′). We know already that dG⊛H((g, h), (g′, h′)) ≤ 4. Clearly
NG⊛H((g, h)) = V (G2) × B2 = D and NG⊛H((g′, h′)) = ((V (G2) − {g′}) ×
NH(h
′)) ∪ ({g} × (B′′1 ∪ B2)). There is no edge between D and a vertex in {g} × B2
because H[B2] = H[NH [h]] is complete. Similar, there is no edge between D and a
vertex in {g} × B′′1 because there are all possible edges between B2 = NH(h) and
B′′1 = NH [h] − B′1 in H . Finally, there are no edges between vertices from D and from
(V (G2)−{g′})×NH(h′) because G2 is complete and there are no edges between B2 and
{h} ∪B′1 in H . Therefore, dG⊛H((g, h), (g′, h′)) ≥ 4 and equality follows.
Next we assume that Condition 10 holds for G = X,H = Y, (g, h) = (x, y)
and (g′, h′) = (x′, y′). We know already that dG⊛H((g, h), (g′, h′)) ≤ 4. Clearly
NG⊛H((g, h)) = V (G2)× B2 = D and NG⊛H((g′, h′)) = V (G2)× (B′1 ∪ {h}) = D′.
There is no edge between D and a vertex in D′ because G2 is complete and there are no
edges between B2 and B′1 ∪ {h} in H . Therefore, dG⊛H((g, h), (g′, h′)) ≥ 4 and equality
follows.
We end when Condition 11 holds for G = X,H = Y, (g, h) = (x, y) and (g′, h′) =
(x′, y′). We know already that dG⊛H((g, h), (g′, h′)) ≤ 4. Clearly NG⊛H((g, h)) =
V (G2) × B2 = D and NG⊛H((g′, h′)) = V (G2) × NH [h′] = D′ ⊆ V (G2) × B′1.
20 Art Discrete Appl. Math. 6 (2023) #P2.13
There are no edges between vertices of D and vertices of D′ because G2 is complete
and there are no edges between vertices of B2 and vertices of B′1 in H . Therefore,
dG⊛H((g, h), (g
′, h′)) ≥ 4 and equality follows and the proof is completed.
ORCID iDs
Aleksander Kelenc https://orcid.org/0000-0003-1633-9845
Iztok Peterin https://orcid.org/0000-0002-1990-6967
References
[1] G. Abay-Asmerom and R. Hammack, Centers of tensor products of graphs, Ars Comb. 74
(2005), 201–211.
[2] B. Brešar, P. Dorbec, W. Goddard, B. L. Hartnell, M. A. Henning, S. Klavžar and D. F. Rall,
Vizing’s conjecture: a survey and recent results, J. Graph Theory 69 (2012), 46–76, doi:10.
1002/jgt.20565, https://doi.org/10.1002/jgt.20565.
[3] M. Grech, W. Imrich, A. D. Krystek and L. u. J. Wojakowski, Direct product of automorphism
groups of digraphs, Ars Math. Contemp. 17 (2019), 89–101, doi:10.26493/1855-3974.1498.
77b, https://doi.org/10.26493/1855-3974.1498.77b.
[4] 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, with a foreword by Peter Winkler.
[5] R. H. Hammack and W. Imrich, On Cartesian skeletons of graphs, Ars Math. Contemp.
2 (2009), 191–205, doi:10.26493/1855-3974.114.4bb, https://doi.org/10.26493/
1855-3974.114.4bb.
[6] W. Imrich, Assoziative Produkte von Graphen, Österreich. Akad. Wiss. Math.-Natur. Kl. S.-B.
II 180 (1972), 203–239.
[7] W. Imrich, Factoring cardinal product graphs in polynomial time, volume 192, pp.
119–144, 1998, doi:10.1016/S0012-365X(98)00069-7, https://doi.org/10.1016/
S0012-365X(98)00069-7.
[8] W. Imrich and I. Peterin, Recognizing Cartesian products in linear time, Discrete Mathematics
307 (2007), 472–483, doi:10.1016/j.disc.2005.09.038, algebraic and Topological Methods in
Graph Theory, https://doi.org/10.1016/j.disc.2005.09.038.
[9] C. Kang, A. Kelenc, I. Peterin and E. Yi, On distance and strong metric dimension of the
modular product, in preparation.
[10] A. Kelenc and I. Peterin, On some metric properties of direct-co-direct product, 2021, sub-
mited.
[11] S.-R. Kim, Centers of a tensor composite graph, in: Proceedings of the Twenty-second South-
eastern Conference on Combinatorics, Graph Theory, and Computing (Baton Rouge, LA,
1991), volume 81, 1991 pp. 193–203.
[12] D. Kozen, A clique problem equivalent to graph isomorphism, SIGACT News 10 (1978), 50–52,
doi:10.1145/990524.990529, https://doi.org/10.1145/990524.990529.
[13] Y. Shitov, Counterexamples to Hedetniemi’s conjecture, Ann. of Math. (2) 190 (2019), 663–
667, doi:10.4007/annals.2019.190.2.6, https://doi.org/10.4007/annals.2019.
190.2.6.
A. Kelenc et al.: Distance formula for direct-co-direct product in the case of disconnected factors 21
[14] M. E. Watkins, On the action of non-Abelian groups on graphs, J. Comb. Theory Ser. B
11 (1971), 95–104, doi:10.1016/0095-8956(71)90019-0, https://doi.org/10.1016/
0095-8956(71)90019-0.
[15] P. M. Weichsel, The Kronecker product of graphs, Proc. Am. Math. Soc. 13 (1962), 47–52,
doi:10.2307/2033769, https://doi.org/10.2307/2033769.