Ac
ce
pt
ed
 m
an
us
cr
ip
tISSN 2590-9770
The Art of Discrete and Applied Mathematics
https://doi.org/10.26493/2590-9770.1623.7f0
(Also available at http://adam-journal.eu)
The core of a vertex-transitive complementary
prism of a lexicographic product
Marko Orel*
University of Primorska, FAMNIT, Glagoljaška 8, Koper, Slovenia and
University of Primorska, IAM, Muzejski trg 2, Koper, Slovenia and
IMFM, Jadranska 19, Ljubljana, Slovenia
Received 20 February 2023, accepted 13 March 2023
Abstract
The complementary prism of a graph Γ is the graph ΓΓ̄, which is formed from the
union of Γ and its complement Γ̄ by adding an edge between each pair of identical ver-
tices in Γ and Γ̄. Vertex-transitive self-complementary graphs provide vertex-transitive
complementary prisms. It was recently proved by the author that ΓΓ̄ is a core, i.e. all its
endomorphisms are automorphisms, whenever Γ is vertex-transitive, self-complementary,
and either Γ is a core or its core is a complete graph. In this paper the same conclusion is
obtained for some other classes of vertex-transitive self-complementary graphs that can be
decomposed as a lexicographic product Γ = Γ1[Γ2]. In the process some new results about
the homomorphisms of a lexicographic product are obtained.
Keywords: Graph homomorphism, core, complementary prism, self-complementary graph, vertex-
transitive graph, lexicographic product.
Math. Subj. Class.: 05C60, 05C76
1 Introduction
Given a graph it is often difficult to decide if it is a core or not. In the case of some graphs
with high degree of symmetry and nice combinatorial properties, the decision is equivalent
to some of the longstanding open problems in finite geometry [4, 25]. A well known core
is the Petersen graph, which has many generalizations. One such family is given by the
Kneser graphs. Another is constructed from the invertible hermitian matrices over the field
*The author thanks all referees for their helpful comments that improved the presentation of the paper. This
work is supported in part by the Slovenian Research Agency (research program P1-0285 and research projects
N1-0140, N1-0208, N1-0210, J1-4084, and N1-0296).
E-mail address: marko.orel@upr.si (Marko Orel)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
Ac
ce
pt
ed
 m
an
us
cr
ip
t
2 Art Discrete Appl. Math.
with four elements [24]. Both of these two families consist of cores if we exclude Kneser
graphs with trivial parameters (see [10, Theorem 7.9.1] and [24, Theorem 7]). Generalized
Petersen graphs G(n, k) that are cores were very recently studied in [8]. The complemen-
tary prism ΓΓ̄, which was introduced in [14], is also a generalization of the Petersen graph.
In fact, the Petersen graph is isomorphic to C5C5, where C5 is the 5-cycle. Recall that C5
is strongly regular vertex-transitive self-complementary graph. In [22] it was shown that
ΓΓ̄ is a core whenever Γ is strongly regular and self-complementary (see also the arXiv
version [26, Theorem 5.7]). The same conclusion was obtained in [23] (see also [26, The-
orem 5.10]) for all vertex-transitive self-complementary graphs Γ, provided that Γ is core-
complete, i.e. Γ is either a core or it has an endomorphism that maps Γ onto a maximum
clique. In general, the existence of a vertex-transitive self-complementary graph Γ, such
that ΓΓ̄ is not a core, was stated as an open problem ([23], [26, Open Problem 5.12]).
Here, it should be emphasized that despite the possible orders of vertex-transitive self-
complementary graphs are fully determined [21], the graphs themselves are poorly under-
stood. In particular, the first non-Cayley vertex-transitive self-complementary graph was
constructed only in 2001 [19]. Moreover, graphs with high degree of symmetry or nice
combinatorial properties are often core-complete [4, 11, 28]. In this paper the focus is on
the only vertex-transitive self-complementary graphs, the author is aware of, which are not
core-complete (see Remarks 4.2, 4.6 and Example 4.9). They are in the form of a lexico-
graphic product Γ = Γ1[Γ2] for specially chosen graphs Γ1 and Γ2. It turns out that also
in these cases the complementary prism ΓΓ̄ is a core (see Corollaries 4.3 and 4.7), which
means that the problem stated in [23] remains open.
The rest of the paper is organized as follows. In Section 2 we recall the necessary
definitions and auxiliary lemmas, together with a result from [22] (and [26]) that we rely
on in the proofs. Several results about the homomorphisms of a lexicographic product are
recalled and developed in Section 3. The main results are presented in Section 4.
2 Preliminaries
All graphs in this paper are finite and simple. The vertex set and the edge set of a graph Γ
are denoted by V (Γ) and E(Γ), respectively. A subset of pairwise adjacent vertices in
V (Γ) is a clique, while a set of pairwise nonadjacent vertices in V (Γ) is an independent
set. If a clique or an independent set has the largest possible order, then it is referred
to as the maximum clique or maximum independent set, respectively. The corresponding
orders are the clique number ω(Γ) and the independence number α(Γ) of Γ, respectively.
In particular, α(Γ) = ω(Γ̄), where Γ̄ is the complement of Γ. If {u, v} ∈ E(Γ), then
we write u ∼Γ v or simply u ∼ v if it is clear from the context which graph is meant.
The set NΓ(u) = {v ∈ V (Γ) : u ∼ v} is the neighborhood of u ∈ V (Γ), and the set
NΓ[u] = NΓ(u) ∪ {u} is the closed neighborhood of u ∈ V (Γ).
A graph homomorphism between graphs Γ1,Γ2 is a map φ : V (Γ1) → V (Γ2) such
that φ(NΓ1(u)) ⊆ NΓ2
(
φ(u)
)
for all u ∈ V (Γ1). In other words, φ(u) ∼Γ2 φ(v) when-
ever u ∼Γ1 v. If in addition φ is bijective and φ(u) ∼Γ2 φ(v) if and only if u ∼Γ1 v,
for all u, v ∈ V (Γ1), then φ is a graph isomorphism and graphs Γ1,Γ2 are isomorphic,
which we denote by Γ1 ∼= Γ2. The sets of all graph homomorphisms/isomorphisms from
Γ1 to Γ2 are denoted by Hom(Γ1,Γ2) and Iso(Γ1,Γ2), respectively. Similarly, we use
End(Γ) = Hom(Γ,Γ) and Aut(Γ) = Iso(Γ,Γ) to denote the sets of all graph endomor-
phisms and automorphisms, respectively. The elements in the set Aut(Γ) = Iso(Γ, Γ̄) are
Ac
ce
pt
ed
 m
an
us
cr
ip
t
M. Orel: The core of a vertex-transitive complementary prism of a lexicographic product 3
antimorphisms (or complementing permutations) of Γ. If Aut(Γ) is nonempty, then Γ is a
self-complementary graph. Observe that Aut(Γ̄) = Aut(Γ). A graph Γ is vertex-transitive
if for each pair of vertices u, v ∈ V (Γ) there exists an automorphism φ ∈ Aut(Γ) such
that u = φ(v). If NΓ(u) has constant number of elements for each u ∈ V (Γ), then Γ
is a regular graph. If this number equals k, then we say that Γ is k-regular. Clearly,
each vertex-transitive graph is regular. A k-regular graph on n vertices is strongly regu-
lar with parameters (n, k, λ, µ) if |NΓ(u) ∩ NΓ(v)| = λ whenever {u, v} ∈ E(Γ) and
|NΓ(u) ∩ NΓ(v)| = µ whenever {u, v} /∈ E(Γ), for all distinct vertices u, v ∈ V (Γ).
We use Kn to denote the complete graph on n vertices. The chromatic number χ(Γ) of a
graph Γ is the minimal value n such that the set Hom(Γ,Kn) is nonempty. It is well known
that χ(Γ) ≥ ω(Γ) and χ(Γ) ≥ nα(Γ) , where n = |V (Γ)| (cf. [1]). From our definition of
the chromatic number we immediately deduce the following claim (cf. [13, 12]).
Lemma 2.1. If Hom(Γ1,Γ2) is nonempty for graphs Γ1,Γ2, then χ(Γ1) ≤ χ(Γ2).
Lemma 2.2 for vertex-transitive graphs and strongly regular graphs can be found in [9,
Corollaries 2.1.2, 2.1.3] and [9, Theorem 3.8.4 and Corollary 3.8.6], respectively, where it
is stated in a more general settings.
Lemma 2.2. If a graph Γ is vertex-transitive or strongly regular, then α(Γ)ω(Γ) ≤ |V (Γ)|.
If the equality holds, then |C ∩ I| = 1 for each maximum clique C and each maximum
independent set I .
In Corollary 2.3, the claim for vertex-transitive graphs follows directly from the proof
of [10, Theorem 6.13.2]. We provide a short proof that works also for strongly regular
graphs.
Corollary 2.3. If a graph Γ is vertex-transitive or strongly regular, and φ ∈ Hom(Γ,
Kω(Γ)), then α(Γ)ω(Γ) = |V (Γ)| and |φ−1(v)| = α(Γ) for each vertex v in Kω(Γ).
Proof. By Lemma 2.1, χ(Γ) ≤ χ(Kω(Γ)) = ω(Γ). Hence, ω(Γ) = χ(Γ) ≥ |V (Γ)|α(Γ) .
By Lemma 2.2, it follows that α(Γ)ω(Γ) = |V (Γ)|. Since the preimages φ−1(v), with
v ∈ V (Kω(Γ)), are independent sets in Γ that partition V (Γ), we have
|V (Γ)| =
∑
v∈V (Kω(Γ))
|φ−1(v)| ≤ α(Γ)ω(Γ) = |V (Γ)|.
Consequently, |φ−1(v)| = α(Γ) for all v.
It is obvious that each regular self-complementary graph on n vertices is (n−12 )-regular.
Consequently, the hand-shaking lemma implies that n = 4m + 1 for some nonnegative
integer m, and Lemma 2.4 follows from the results in [27] or [30] (see also [7, p. 12]
and [23]).
Lemma 2.4. If Γ is a regular self-complementary graph and σ ∈ Aut(Γ), then there exists
a unique vertex v ∈ V (Γ) such that σ(v) = v.
A graph Γ is a core if End(Γ) = Aut(Γ). Given a graph Γ, we use core(Γ) to denote any
subgraph in Γ that is a core and such that the set Hom
(
Γ, core(Γ)
)
is nonempty. The graph
core(Γ) is referred to as the core of Γ. It is always an induced subgraph and unique up to
Ac
ce
pt
ed
 m
an
us
cr
ip
t
4 Art Discrete Appl. Math.
isomorphism [10, Lemma 6.2.2]. Clearly, a graph Γ is a core if and only if Γ = core(Γ).
On the other hand, core(Γ) is a complete graph if and only if χ(Γ) = ω(Γ). It is well
known that there always exists a retraction ψ : Γ → core(Γ), i.e. a graph homomorphism
that fixes each vertex in core(Γ). In fact, if φ ∈ Hom
(
Γ, core(Γ)
)
is arbitrary, then the
restriction φ|V (core(Γ)) is invertible and the composition (φ|V (core(Γ)))−1 ◦φ is the required
retraction.
Let Γ be a graph with the vertex set V (Γ) = {v1, . . . , vn}. The complementary prism
of Γ is the graph ΓΓ̄, which is constructed from the disjoint union of Γ and its comple-
ment Γ̄ if we add an edge between each vertex in Γ and its copy in Γ̄. More precisely, the
vertex set V (ΓΓ̄) equals W1 ∪W2, where
W1 =W1(ΓΓ̄) = {(v1, 1), . . . , (vn, 1)} and W2 =W2(ΓΓ̄) = {(v1, 2), . . . , (vn, 2)},
while the edge set E(ΓΓ̄) is the union of the sets{
{(u, 1), (v, 1)} : {u, v} ∈ E(Γ)
}
,{
{(u, 2), (v, 2)} : {u, v} ∈ E(Γ̄)
}
,{
{(u, 1), (u, 2)} : u ∈ V (Γ)
}
.
Obviously, ΓΓ̄ is regular if and only if Γ is
(
n−1
2
)
-regular (cf. [5, Theorem 3.6]). For a
general graph Γ the core of its complementary prism ΓΓ̄ was recently studied in [22] (see
also the arXiv version [26]). In particular, the following result was proved for a regular
graph ΓΓ̄.
Lemma 2.5 ([26, Corollary 5.4]). Let Γ be any graph on n vertices that is
(
n−1
2
)
-regular.
If core(ΓΓ̄) is any core of ΓΓ̄, then one of the following three possibilities is true.
(i) ΓΓ̄ is a core.
(ii) All vertices of core(ΓΓ̄) are contained in W1, in which case
core(ΓΓ̄) ∼= core(Γ).
(iii) All vertices of core(ΓΓ̄) are contained in W2, in which case
core(ΓΓ̄) ∼= core(Γ̄).
3 Homomorphisms of the lexicographic product
In this section we recall and develop some properties of the homomorphisms of the lexi-
cographic product of graphs. The lexicographic product of graphs Γ1 and Γ2 is the graph
Γ1[Γ2] with the vertex set V (Γ1)× V (Γ2), where (u1, u2) ∼ (v1, v2) if and only if either
u1 ∼Γ1 v1 or u1 = v1 and u2 ∼Γ2 v2. Here we follow the notation in [12]. The same
product appears in the literature also as Γ1 ◦ Γ2 (see [2, 3, 13, 29, 31, 32]) and as Γ1 ≀ Γ2
in which case it is referred to as the wreath product [6, 20]. Observe that Γ1[Γ2] = Γ1[Γ2].
In particular, Γ1[Γ2] is self-complementary whenever Γ1 and Γ2 are self-complementary.
The converse is also true. Namely, if Γ1[Γ2] is self-complementary, then Γ1[Γ2] ∼= Γ1[Γ2]
and [13, Theorem 10.8] implies that Γ1 ∼= Γ1 and Γ2 ∼= Γ2. Similarly, Γ1[Γ2] is vertex-
transitive if and only if Γ1 and Γ2 are vertex-transitive [13, Theorem 10.14]. Analogous
claim for regularity can be proved straightforward.
Ac
ce
pt
ed
 m
an
us
cr
ip
t
M. Orel: The core of a vertex-transitive complementary prism of a lexicographic product 5
If graphs Γi and Γ′i are isomorphic for i = 1, 2, then we define
Iso(Γ1,Γ′1) ≀ Iso(Γ2,Γ′2) (3.1)
as the set of all maps (φ, β) : Γ1[Γ2] → Γ′1[Γ′2] that are of the form
(φ, β)(v1, v2) :=
(
φ(v1), β(v1)(v2)
)
(3.2)
for all v1 ∈ V (Γ1), v2 ∈ V (Γ2), where φ ∈ Iso(Γ1,Γ′1) and β : V (Γ1) → Iso(Γ2,Γ′2) is a
map. Clearly, the map (3.2) is an isomorphism and (3.1) is a subset in Iso(Γ1[Γ2],Γ′1[Γ
′
2]).
If Γ′i = Γi for i = 1, 2 or Γ
′
i = Γi for i = 1, 2, then we write Aut(Γ1) ≀ Aut(Γ2) or
Aut(Γ1) ≀Aut(Γ2) instead of (3.1), respectively. Here we emphasize that Aut(Γ1) ≀Aut(Γ2)
is known as the wreath product of groups Aut(Γ1) and Aut(Γ2) (see [6, Section 4.2]).
Given a graph Γ letRΓ = {(u, v) ∈ V (Γ)×V (Γ) : NΓ(u) = NΓ(v)}, SΓ = {(u, v) ∈
V (Γ) × V (Γ) : NΓ[u] = NΓ[v]}, and △Γ = {(u, u) ∈ V (Γ) × V (Γ) : u ∈ V (Γ)}.
Sabidussi [29] proved the following result (see also [13, Theorem 10.13]).
Lemma 3.1. For any graphs Γ1,Γ2 we have Aut
(
Γ1[Γ2]
)
= Aut(Γ1) ≀ Aut(Γ2) if and only
if the following two assertions hold:
(i) If RΓ1 ̸= △Γ1 , then Γ2 is connected.
(ii) If SΓ1 ̸= △Γ1 , then Γ2 is connected.
Corollary 3.2 follows easily from Lemma 3.1. A short proof is provided for the reader’s
convenience (for more elaborate results of this kind see [15]).
Corollary 3.2. Suppose that Γi ∼= Γ′i for i = 1, 2. If Γ2 and Γ2 are both connected, then
Iso
(
Γ1[Γ2],Γ
′
1[Γ
′
2]
)
= Iso(Γ1,Γ′1) ≀ Iso(Γ2,Γ′2).
Proof. Let Φ ∈ Iso
(
Γ1[Γ2],Γ
′
1[Γ
′
2]
)
. Pick any ψ1 ∈ Iso(Γ1,Γ′1), ψ2 ∈ Iso(Γ2,Γ′2), and
define Ψ ∈ Iso
(
Γ1[Γ2],Γ
′
1[Γ
′
2]
)
by Ψ(v1, v2) = (ψ1(v1), ψ2(v2)) for all v1 ∈ V (Γ1) and
v2 ∈ V (Γ2). Then Ψ−1 ◦ Φ ∈ Aut
(
Γ1[Γ2]
)
. By Lemma 3.1, Ψ−1 ◦ Φ = (φ, β) for some
φ ∈ Aut(Γ1) and a map β : V (Γ1) → Aut(Γ2). Consequently, Φ = (ψ1 ◦ φ, γ), where
γ : V (Γ1) → Iso(Γ2,Γ′2) is defined by γ(v1) = ψ2 ◦ β(v1). Hence, Φ ∈ Iso(Γ1,Γ′1) ≀
Iso(Γ2,Γ′2).
Since self-complementary graphs are connected (cf. [7]), we deduce the following.
Corollary 3.3. Let Γ1 and Γ2 be self-complementary graphs. Then
(i) Aut
(
Γ1[Γ2]
)
= Aut(Γ1) ≀ Aut(Γ2),
(ii) Aut
(
Γ1[Γ2]
)
= Aut(Γ1) ≀ Aut(Γ2).
Similarly as above, for given graphs Γ1,Γ′1,Γ2,Γ
′
2 with nonempty sets Hom(Γ1,Γ
′
1)
and Hom(Γ2,Γ′2), we define
Hom(Γ1,Γ′1) ≀ Hom(Γ2,Γ′2) (3.3)
as the set of all homomorphisms (φ, β) : Γ1[Γ2] → Γ′1[Γ′2] that are of the form (3.2), where
φ ∈ Hom(Γ1,Γ′1) and β : V (Γ1) → Hom(Γ2,Γ′2) is a map. If Γ′i = Γi for i = 1, 2, we
write End(Γ1) ≀ End(Γ2) instead of (3.3) (cf. [16, 17, 18]).
It is obvious that Γ1 and Γ2 are cores whenever Γ1[Γ2] is a core (see [18, Proposi-
tion 3.10]). The converse is not true in general. The following result is proved in [18,
Theorem 3.11].
Ac
ce
pt
ed
 m
an
us
cr
ip
t
6 Art Discrete Appl. Math.
Lemma 3.4. Let n be a positive integer and Γ2 a graph. Then Kn[Γ2] is a core if and only
if Γ2 is a core.
Lemma 3.5 is proved in [17, Theorem 14].
Lemma 3.5. Let Γ1 and Γ2 be graphs, where Γ1 is a core, and let core(Γ1[Γ2]) be any core
of Γ1[Γ2]. Then End
(
Γ1[Γ2]
)
= End(Γ1) ≀ End(Γ2) if and only if the following assertions
are true:
(i) core(Γ1[Γ2]) = Γ1[core(Γ2)], where core(Γ2) is some core of Γ2.
(ii) SΓ1 = △Γ1 or core(Γ2) is connected.
Corollary 3.6. Let Γ1 and Γ2 be graphs, where Γ1[core(Γ2)] is a core. If Γ1 is self-
complementary, then End
(
Γ1[Γ2]
)
= End(Γ1) ≀ End(Γ2).
Proof. Obviously there exist a homomorphism from Γ1[Γ2] onto Γ1[core(Γ2)]. Hence,
(i) from Lemma 3.5 is satisfied. Since Γ1[core(Γ2)] is a core, the same is true for Γ1.
Consequently, to end the proof it suffices to prove that SΓ1 = △Γ1 . Suppose on the contrary
that there are distinct u, v ∈ V (Γ1) such that NΓ1 [u] = NΓ1 [v]. Clearly, u and v are
adjacent in Γ1. Consequently, NΓ1(u) = NΓ1(v) and u, v are nonadjacent in Γ1. The map
φ on V (Γ1) that maps u to v and fixes all other vertices is a nonbijective endomorphism
of Γ1. Since Γ1 is a core by self-complementarity, we get a contradiction.
Lemma 3.7. Let Γ1,Γ2 be graphs, where Γ1 is vertex-transitive, while Γ2,Γ2 are both
connected. If core(Γ1) is any core of Γ1 and core(Γ1)[Γ2] is a core, then
Hom
(
Γ1[Γ2], core(Γ1)[Γ2]
)
= Hom
(
Γ1, core(Γ1)
)
≀ Hom(Γ2,Γ2).
Proof. Let Φ ∈ Hom
(
Γ1[Γ2], core(Γ1)[Γ2]
)
and v1 ∈ V (Γ1). Since Γ1 is vertex-transitive,
there exists a subgraph Γ in Γ1, which is isomorphic to core(Γ1) and such that v1 ∈
V (Γ). The restriction Φ|V (Γ[Γ2]) is a homomorphism from Γ[Γ2] to core(Γ1)[Γ2]. Since
core(Γ1)[Γ2] is a core, we deduce that Φ|V (Γ[Γ2]) is an isomorphism. By Corollary 3.2,
Φ|V (Γ[Γ2]) = (φ, β) for some φ ∈ Iso(Γ, core(Γ1)) and a map β : V (Γ) → Iso(Γ2,Γ2) =
Aut(Γ2). Since v1 ∈ V (Γ1) is arbitrary, we deduce in particular that
Φ(v1, v2) = (ψ(v1), βv1(v2))
for all v1 ∈ V (Γ1) and v2 ∈ V (Γ2), where ψ : V (Γ1) → V
(
core(Γ1)
)
is some map and
βv1 ∈ Aut(Γ2).
We claim that ψ is a graph homomorphism. Let v1 ∼Γ1 v′1. Then
(ψ(v1), βv1(v2)) = Φ(v1, v2) ∼ Φ(v′1, v′2) = (ψ(v′1), βv′1(v
′
2)) (3.4)
for all v2, v′2 ∈ V (Γ2). Since βv1 , βv′1 are automorphisms, we can find v2, v
′
2 such that
βv1(v2) = βv′1(v
′
2). It follows from (3.4) that ψ(v1) ∼Γ1 ψ(v′1) and ψ is a graph ho-
momorphism. Hence, Φ = (ψ, β̂), where the map β̂ : V (Γ1) → Aut(Γ2) is defined by
β̂(v1) := βv1 . Therefore, Φ ∈ Hom
(
Γ1, core(Γ1)
)
≀ Hom(Γ2,Γ2).
We remark that since core(Γ1)[Γ2] is a core in Lemma 3.7, then Γ2 is also a core.
Consequently, Hom(Γ2,Γ2) = Aut(Γ2).
Ac
ce
pt
ed
 m
an
us
cr
ip
t
M. Orel: The core of a vertex-transitive complementary prism of a lexicographic product 7
4 Main results
In [26, Corollary 3.8] it was recently proved that the complementary prism ΓΓ̄ is vertex-
transitive if and only if Γ is vertex-transitive and self-complementary. In [23] it was proved
that a vertex-transitive complementary prism ΓΓ̄ is a core whenever Γ is a core or its
core is complete. In Corollaries 4.3 and 4.7 we consider the only vertex-transitive self-
complementary graphs the author is aware of, which are neither cores nor their cores are
complete. We prove that ΓΓ̄ is a core also for such graphs. Theorems 4.1 and 4.4 gener-
alize Corollaries 4.3 and 4.7. They simultaneously generalize also a result from [23] (see
Remark 4.8).
Theorem 4.1. Let Γ1,Γ2 be self-complementary graphs, where Γ1 is vertex-transitive and
Γ2 is regular. If core(Γ1) is complete, Γ2 is a core, and Γ = Γ1[Γ2], then ΓΓ̄ is a core.
Proof. Recall from the beginning of Section 3 that the lexicographic product Γ is regular
and self-complementary. Consequently, only the possibilities (i), (ii), (iii) in Lemma 2.5
may occur. Suppose that (iii) is correct, that is, V (core(ΓΓ̄)) ⊆ W2 and core(ΓΓ̄) ∼=
core(Γ̄). Let ϕ : Γ1 → Km be any homomorphism onto a complete core of Γ1. Then the
map Γ̄ = Γ1[Γ2] → Km[Γ2], defined by (v1, v2) 7→ (ϕ(v1), v2) for all v1 ∈ V (Γ1), v2 ∈
V (Γ2), is a graph homomorphism. By Lemma 3.4 it follows that
core(ΓΓ̄) ∼= core(Γ̄) = Km[Γ2].
Let ψ : core(ΓΓ̄) → Km[Γ2] be any isomorphism and let Φ: ΓΓ̄ → core(ΓΓ̄) be any ho-
momorphism. The map ψ1, defined by ψ1(v) = (v, 1) for all v ∈ V (Γ), is the canonical
isomorphism between Γ and the subgraph in ΓΓ̄, which is induced by the set W1. Simi-
larly, ψ2(v) = (v, 2), where v ∈ V (Γ), is the canonical isomorphism between Γ̄ and the
subgraph induced by W2. Then f2 := ψ ◦ (Φ|W2) ◦ ψ2 ∈ Hom(Γ1[Γ2],Km[Γ2]). Sim-
ilarly, if σ : Γ → Γ̄ is any antimorphism and f1 := ψ ◦ (Φ|W1) ◦ ψ1, then f1 ◦ σ−1 ∈
Hom(Γ1[Γ2],Km[Γ2]). By Lemma 3.7 and Corollary 3.3 we deduce that
f2 = (φ2, β2) and f1 = (φ1, β1) ◦ (σ1, γ),
where
φ1, φ2 ∈ Hom(Γ1,Km),
β1, β2 : V (Γ1) → Hom(Γ2,Γ2) = Aut(Γ2),
σ1 ∈ Aut(Γ1),
γ : V (Γ1) → Aut(Γ2).
That is,
f2(v1, v2) =
(
φ2(v1), β2(v1)(v2)
)
, (4.1)
f1(v1, v2) =
(
(φ1 ◦ σ1)(v1),
(
β1(σ1(v1)) ◦ γ(v1)
)
(v2)
)
(4.2)
for all v1 ∈ V (Γ1), v2 ∈ V (Γ2). Pick any v ∈ V (Km). By Corollary 2.3, φ−12 (v)
is an independent set in Γ1 of order α(Γ1), (φ1 ◦ σ1)−1(v) is a clique in Γ1 of order
α(Γ1) = ω(Γ1), and α(Γ1)ω(Γ1) = |V (Γ1)|. By Lemma 2.2, there exists
v1 ∈ φ−12 (v) ∩ (φ1 ◦ σ1)−1(v).
Ac
ce
pt
ed
 m
an
us
cr
ip
t
8 Art Discrete Appl. Math.
Since
(
β1(σ1(v1)) ◦ γ(v1)
)−1 ◦ β2(v1) ∈ Aut(Γ2) = Aut(Γ2), Lemma 2.4 yields a vertex
v2 ∈ V (Γ2) such that (
β1(σ1(v1)) ◦ γ(v1)
)
(v2) = β2(v1)(v2).
Consequently, f1(v1, v2) = f2(v1, v2) by (4.1)-(4.2). Therefore
Φ
(
(v1, v2), 1
)
= (ψ−1 ◦ f1 ◦ ψ−11 )
(
(v1, v2), 1
)
= (ψ−1 ◦ f2 ◦ ψ−12 )
(
(v1, v2), 2
)
= Φ
(
(v1, v2), 2
)
,
which is a contradiction, since {
(
(v1, v2), 1
)
,
(
(v1, v2), 2
)
} is an edge in ΓΓ̄.
In the same way we see that (ii) in Lemma 2.5 is not possible, so (i) is true.
Remark 4.2. It follows from Lemma 3.4 that the core of Γ in Theorem 4.1 is isomorphic
to core(Γ1)[Γ2]. Hence, Γ is neither a core nor its core is complete whenever Γ1 and Γ2
have more than one vertex.
Recall from Section 3 that Γ1[Γ2] is vertex-transitive and self-complementary if and
only if Γ1 and Γ2 both have these properties. Consequently, Corollary 4.3 follows directly
from Theorem 4.1.
Corollary 4.3. Let Γ = Γ1[Γ2] be vertex-transitive and self-complementary. If core(Γ1) is
complete and Γ2 is a core, then ΓΓ̄ is a core.
If we swap the assumptions regarding Γ1 and Γ2 in Theorem 4.1, then we are able to
deduce the same conclusion under the additional condition that Γ1[core(Γ2)] is a core.
Theorem 4.4. Let Γ1,Γ2 be self-complementary graphs, where Γ1 is regular and Γ2 is
vertex-transitive. If core(Γ2) is complete, Γ1[core(Γ2)] is a core, and Γ = Γ1[Γ2], then ΓΓ̄
is a core.
Remark 4.5. The claim and the proof of Theorem 4.4 remains valid if we replace vertex-
transitivity of Γ2 by strong regularity. However, at this point in time the author is not
aware of any strongly regular self-complementary graph that is not vertex-transitive (cf. [7,
page 88]).
Since Theorems 4.1 and 4.4 have similar proofs, we sketch only the main differences.
Sketch of the proof. Denote core(Γ2) =: Km. Similarly as in the proof of Theorem 4.1 we
deduce that the condition (iii) in Lemma 2.5 would yield
core(ΓΓ̄) ∼= core(Γ̄) = Γ1[Km].
Here, the only difference is the application of Lemma 3.4, which is replaced by the as-
sumption that Γ1[Km] is a core. Let ψ : core(ΓΓ̄) → Γ1[Km] be any isomorphism,
and define Φ, ψ1, ψ2, f1, f2, σ as in the proof of Theorem 4.1. Then f2, f1 ◦ σ−1 ∈
Hom(Γ1[Γ2],Γ1[Km]). Hence, these maps may be interpreted as members of End(Γ1[Γ2]),
which equals End(Γ1) ≀ End(Γ2) by Corollary 3.6. Note that since Γ1[core(Γ2)] is a core,
Ac
ce
pt
ed
 m
an
us
cr
ip
t
M. Orel: The core of a vertex-transitive complementary prism of a lexicographic product 9
the graph Γ1 ∼= Γ1 is a core as well. Therefore f2 = (φ2, β2) and f1 = (φ1, β1) ◦ (σ1, γ),
where
φ1, φ2 ∈ End(Γ1) = Aut(Γ1),
β1, β2 : V (Γ1) → End(Γ2),
σ1 ∈ Aut(Γ1),
γ : V (Γ1) → Aut(Γ2),
and the image of βi(v1) is in V (Km) for all v1 ∈ V (Γ1) and i = 1, 2. Clearly, (4.1)–(4.2)
is still true. Since φ−12 ◦ φ1 ◦ σ1 ∈ Aut(Γ1), Lemma 2.4 yields a vertex v1 ∈ V (Γ1) such
that
(φ1 ◦ σ1)(v1) = φ2(v1).
Let v ∈ V (Km) be any vertex. By Corollary 2.3, (β2(v1))−1(v) is an independent set in
Γ2 of order α(Γ2),
(
β1(σ1(v1)) ◦ γ(v1)
)−1
(v) is a clique in Γ2 of order α(Γ2) = ω(Γ2),
and α(Γ2)ω(Γ2) = |V (Γ2)|. By Lemma 2.2 there exists
v2 ∈ (β2(v1))−1(v) ∩
(
β1(σ1(v1)) ◦ γ(v1)
)−1
(v).
Consequently, (4.1)–(4.2) imply that f1(v1, v2) = f2(v1, v2) and we deduce the same
contradiction as in the proof of Theorem 4.1.
Remark 4.6. It follows from the assumptions that the core of Γ in Theorem 4.4 is isomor-
phic to Γ1[core(Γ2)]. Hence, Γ is neither a core nor its core is complete whenever Γ1 and
Γ2 have more than one vertex.
The following claim is deduced analogously as Corollary 4.3.
Corollary 4.7. Let Γ = Γ1[Γ2] be vertex-transitive and self-complementary. If core(Γ2) is
complete and Γ1[core(Γ2)] is a core, then ΓΓ̄ is a core.
Remark 4.8. In [23, Proposition 3.1] it was proved that ΓΓ̄ is a core whenever Γ is regular,
self-complementary, and a core. Theorems 4.1 and 4.4 both generalize this result. In fact,
K1 is vertex-transitive and self-complementary. Hence, we can consider K1[Γ2] ∼= Γ2 in
Theorem 4.1 and Γ1[K1] ∼= Γ1 in Theorem 4.4.
Example 4.9. Let q be a power of a prime such that q ≡ 1 (mod 4). The Paley graph P (q)
has the finite field Fq as its vertex set, and two of its elements form an edge if and only if
their difference is a nonzero square element in Fq . It is well known that each Paley graph
is vertex-transitive and self-complementary (cf. [9, page 105]). Moreover, P (q) is a core
if q is not a square, while its core is complete if q is a square [4, Proposition 3.3]. Hence,
Γ1 = P (q1) and Γ2 = P (q2) satisfy the assumptions in Corollary 4.3 whenever q1 is a
square and q2 is not. In the reversed order, graphs Γ1 = P (q2) and Γ2 = P (q1) satisfy
the assumptions in Corollary 4.7 at least for q2 = 5. In fact, P (5) is the 5-cycle C5 and
Γ1[core(Γ2)] ∼= C5[K√q1 ] is a core by [18, Theorem 3.11]. □
Clearly, if vertex-transitive self-complementary graphs Γ1 and Γ2 both have complete
cores, then the same is true for Γ = Γ1[Γ2], and therefore ΓΓ̄ is a core by [23, Theorem 3.3].
In view of the open problem in [23], which asks if there exists a vertex-transitive self-
complementary graph Γ such that ΓΓ̄ is not a core, the following three combinations in
Ac
ce
pt
ed
 m
an
us
cr
ip
t
10 Art Discrete Appl. Math.
the lexicographic product Γ1[Γ2] of vertex-transitive self-complementary graphs should be
also addressed:
• Γ1 is a core, core(Γ2) = Km, and Γ1[Km] is neither a core nor its core is complete
(if such graphs exist);
• Γ1 and Γ2 are both cores, and Γ1[Γ2] is neither a core nor its core is complete (if
such graphs exist);
• lexicographic products with more than two factors.
However, the task seems quite challenging. In fact, in general we only know that the core
of Γ1[Γ2] is of the form Γ′1[core(Γ2)], where Γ
′
1 is a subgraph in Γ1 (see [12]).
ORCID iDs
Marko Orel https://orcid.org/0000-0002-2544-2986
References
[1] A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Universitext, Springer, New York, 2012.
[2] A. Cabrera Martı́nez, A. Estrada-Moreno and J. A. Rodrı́guez-Velázquez, From Italian dom-
ination in lexicographic product graphs to w-domination in graphs, Ars Math. Contemp. 22
(2022), 25, doi:10.26493/1855-3974.2318.fb9, id/No 4, https://doi.org/10.26493/
1855-3974.2318.fb9.
[3] A. Cabrera Martı́nez and J. A. Rodrı́guez-Velázquez, Closed formulas for the total Roman
domination number of lexicographic product graphs, Ars Math. Contemp. 20 (2021), 233–
241, doi:10.26493/1855-3974.2284.aeb, https://doi.org/10.26493/1855-3974.
2284.aeb.
[4] P. J. Cameron and P. A. Kazanidis, Cores of symmetric graphs, J. Aust. Math. Soc.
85 (2008), 145–154, doi:10.1017/S1446788708000815, https://doi.org/10.1017/
S1446788708000815.
[5] D. M. Cardoso, P. Carvalho, M. A. A. de Freitas and C. T. M. Vinagre, Spectra, signless
Laplacian and Laplacian spectra of complementary prisms of graphs, Linear Algebra Appl. 544
(2018), 325–338, doi:10.1016/j.laa.2018.01.020, https://doi.org/10.1016/j.laa.
2018.01.020.
[6] T. Dobson, A. Malnič and D. Marušič, Symmetry in Graphs, volume 198 of Camb. Stud. Adv.
Math., Cambridge University Press, Cambridge, 2022, doi:10.1017/9781108553995, https:
//doi.org/10.1017/9781108553995.
[7] A. Farrugia, Self-complementary graphs and generalisations: a comprehensive ref-
erence manual, Master’s thesis, University of Malta, Malta, 1999, http://www.
alastairfarrugia.net/sc-graph.html.
[8] I. Garcı́a-Marco and K. Knauer, Beyond symmetry in generalized petersen graphs, 2022,
arXiv:2202.06785 [math.CO].
[9] C. Godsil and K. Meagher, Erdős-Ko-Rado Theorems: Algebraic Approaches, volume 149
of Camb. Stud. Adv. Math., Cambridge University Press, Cambridge, 2016, doi:10.1017/
CBO9781316414958, https://doi.org/10.1017/CBO9781316414958.
[10] C. Godsil and G. Royle, Algebraic Graph Theory, volume 207 of Grad. Texts Math., Springer,
New York, 2001.
Ac
ce
pt
ed
 m
an
us
cr
ip
t
M. Orel: The core of a vertex-transitive complementary prism of a lexicographic product 11
[11] C. Godsil and G. F. Royle, Cores of geometric graphs, Ann. Comb. 15 (2011), 267–276, doi:
10.1007/s00026-011-0094-5, https://doi.org/10.1007/s00026-011-0094-5.
[12] G. Hahn and C. Tardif, Graph homomorphisms: Structure and symmetry, in: Graph Symme-
try, Algebraic Methods and Applications. Proceedings of the NATO Advanced Study Institute
and séminaire de mathématiques supérieures,Montréal, Canada, Kluwer Academic Publishers,
Dordrecht, pp. 107–166, 1997.
[13] R. Hammack, W. Imrich and S. Klavžar, Handbook of product graphs, Discrete Math. Appl.
(Boca Raton), CRC Press, Boca Raton, 2nd edition, 2011.
[14] T. W. Haynes, M. A. Henning, P. J. Slater and L. C. van der Merwe, The complementary
product of two graphs, Bull. Inst. Comb. Appl. 51 (2007), 21–30.
[15] R. L. Hemminger, The group of an X-join of graphs, J. Comb. Theory 5 (1968), 408–418, doi:
10.1016/S0021-9800(68)80017-1, https://doi.org/10.1016/S0021-9800(68)
80017-1.
[16] R. Kaschek, On unretractive graphs, Discrete Math. 309 (2009), 5370–5380, doi:10.1016/j.
disc.2008.11.039, https://doi.org/10.1016/j.disc.2008.11.039.
[17] R. Kaschek, On wreathed lexicographic products of graphs, Discrete Math. 310 (2010), 1275–
1281, doi:10.1016/j.disc.2009.10.021, https://doi.org/10.1016/j.disc.2009.
10.021.
[18] U. Knauer, Unretractive and S-unretractive joins and lexicographic products of graphs, J. Graph
Theory 11 (1987), 429–440, doi:10.1002/jgt.3190110316, https://doi.org/10.1002/
jgt.3190110316.
[19] C. H. Li and C. E. Praeger, Self-complementary vertex-transitive graphs need not be Cay-
ley graphs, Bull. Lond. Math. Soc. 33 (2001), 653–661, doi:10.1112/s0024609301008505,
https://doi.org/10.1112/s0024609301008505.
[20] D. W. Morris, J. Morris and G. Verret, Groups for which it is easy to detect graphical regu-
lar representations, Art Discrete Appl. Math. 5 (2022), 13, doi:10.26493/2590-9770.1373.60a,
id/No p1.07, https://doi.org/10.26493/2590-9770.1373.60a.
[21] M. Muzychuk, On Sylow subgraphs of vertex-transitive self-complementary graphs, Bull.
Lond. Math. Soc. 31 (1999), 531–533, doi:10.1112/S0024609399005925, https://doi.
org/10.1112/S0024609399005925.
[22] M. Orel, The core of a complementary prism, manuscript.
[23] M. Orel, The core of a vertex-transitive complementary prism, manuscript.
[24] M. Orel, On generalizations of the Petersen graph and the Coxeter graph, Electron. J. Comb. 22
(2015), research paper p4.27, 17 pp., doi:10.37236/3759, https://doi.org/10.37236/
3759.
[25] M. Orel, On Minkowski space and finite geometry, J. Comb. Theory, Ser. A 148 (2017), 145–
182, doi:10.1016/j.jcta.2016.12.004, https://doi.org/10.1016/j.jcta.2016.
12.004.
[26] M. Orel, A family of non-cayley cores based on vertex-transitive or strongly regular self-
complementary graphs, 2021, arXiv:2110.10416 [math.CO].
[27] G. Ringel, Selbstkomplementäre Graphen, Arch. Math. (Basel) 14 (1963), 354–358, doi:10.
1007/bf01234967, https://doi.org/10.1007/bf01234967.
[28] D. E. Roberson, Homomorphisms of strongly regular graphs, Algebr. Comb. 2 (2019), 481–497,
doi:10.5802/alco.50, https://doi.org/10.5802/alco.50.
Ac
ce
pt
ed
 m
an
us
cr
ip
t
12 Art Discrete Appl. Math.
[29] G. Sabidussi, The composition of graphs, Duke Math. J. 26 (1959), 693–
696, doi:10.1215/S0012-7094-59-02667-5, https://doi.org/10.1215/
S0012-7094-59-02667-5.
[30] H. Sachs, Über selbstkomplementäre Graphen, Publ. Math. Debrecen 9 (1962), 270–288.
[31] J. Shive, Lexicographic palindromic products, Art Discrete Appl. Math. 6 (2023), Paper
No. 2.12, 10 pp., doi:10.26493/2590-9770.1390.d21, https://doi.org/10.26493/
2590-9770.1390.d21.
[32] R. Thankachan and P. Rajamani, Coupon coloring of lexicographic product of graphs, Art
Discrete Appl. Math. 6 (2023), Paper No. 1.03, 7 pp., doi:10.26493/2590-9770.1507.dc5,
https://doi.org/10.26493/2590-9770.1507.dc5.