ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 23 (2023) #P4.07
https://doi.org/10.26493/1855-3974.3072.3ec
(Also available at http://amc-journal.eu)
The core of a vertex-transitive complementary
prism
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 15 March 2023, published online 12 May 2023
Abstract
The complementary prism ΓΓ̄ is obtained from the union of a graph Γ and its comple-
ment Γ̄ where each pair of identical vertices in Γ and Γ̄ is joined by an edge. It generalizes
the Petersen graph, which is the complementary prism of the pentagon. The core of a
vertex-transitive complementary prism is studied. In particular, it is shown that a vertex-
transitive complementary prism ΓΓ̄ is a core, i.e. all its endomorphisms are automorphisms,
whenever Γ is a core or its core is a complete graph.
Keywords: Graph homomorphism, core, complementary prism, self-complementary graph, vertex-
transitive graph.
Math. Subj. Class. (2020): 05C60, 05C76
1 Introduction
In the study of graph homomorphism a basic object is a core (a.k.a. unretractive graph),
which is a graph such that all its endomorphisms are automorphisms. A subgraph Γ′ of a
graph Γ is its core, if there exists some graph homomorphism φ : Γ → Γ′ and Γ′ is a core.
Equivalently, Γ′ is the minimal retract of Γ (cf. [17]). Despite that each graph has its core,
which is unique up to isomorphism, it can be often very difficult to determine if a given
graph is a core or not (cf. [6, 16, 30]). From this point of view, graphs that have either high
degree of symmetry (i.e. ‘large’ automorphism group) or some ‘nice’ combinatorial prop-
erties are the most interesting. Many of such classes of graphs are core-complete, which
*The author thanks the anonymous referees for the 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/
2 Ars Math. Contemp. 23 (2023) #P4.07
means that they are either cores or their cores are complete graphs. Among them we can
find all non-edge-transitive graphs [6, Corollary 2.2], connected regular graphs with the au-
tomorphism group that acts transitively on unordered pairs of vertices at distance two [16,
Theorem 4.1], and all primitive strongly regular graphs [36, Corollary 3.6]. Given a core-
complete graph, it can be extremely complicated to decide if the graph is a core or its core is
complete. For some graphs, this task is equivalent to some of the longstanding open prob-
lems in finite geometry (see [6, 30]). A well known core is the Petersen graph, which has
both ‘large’ automorphism group and ‘nice’ combinatorial properties. Given a family of
graphs that (naturally) generalize the Petersen graph it is interesting to study if its members
are cores or not. Kneser graphs K(n, r), with 2r < n, are all cores [15, Theorem 7.9.1].
The graph HGLn(F4), whose vertex set is formed by all n× n invertible hermitian matri-
ces over the field with four elements and with the edge set {{A,B} : rank(A − B) = 1},
is a core whenever n ≥ 2 [29]. The core of a generalized Petersen graph G(n, k) was stud-
ied very recently in [13]. The complementary prism ΓΓ̄, whose definition in full details
is given in Section 2, is another generalization of the Petersen graph, which is obtained if
Γ is the 5-cycle C51. Graph ΓΓ̄ was introduced in [18] and is the main mater of research
in several papers (see for example [1, 3, 7, 10, 19, 26]). Recall that C5 is strongly reg-
ular vertex-transitive self-complementary graph. The core of ΓΓ̄ was recently studied by
the author [28] (see also the arXiv version [31]). In particular, it was shown that ΓΓ̄ is
a core whenever Γ is strongly regular and self-complementary. In this paper we build on
a result from [28] and investigate vertex-transitive self-complementary graphs Γ. These
are precisely the graphs that provide vertex-transitive complementary prisms [31, Corol-
lary 3.8]. For such graphs we prove that ΓΓ̄ is a core whenever Γ is core-complete (see
Theorem 3.3), and state an open problem, which asks if there exists a vertex-transitive self-
complementary graph Γ such that ΓΓ̄ is not a core (Problem 3.6). The main results are
presented in Section 3. In Section 2 we recall some tools and definitions that we need in
what follows.
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. The clique number ω(Γ) and the independence number α(Γ) are the orders of the
largest clique and the largest independent set in Γ, respectively. In particular, α(Γ) = ω(Γ̄),
where Γ̄ is the complement of the graph Γ. The chromatic number of a graph is denoted
by χ(Γ). It is well known that χ(Γ) ≥ ω(Γ) and χ(Γ) ≥ nα(Γ) , where n = |V (Γ)|
(cf. [5]). A graph homomorphism between graphs Γ1,Γ2 is a map φ : V (Γ1) → V (Γ2)
such that {φ(u), φ(v)} ∈ E(Γ2) whenever {u, v} ∈ E(Γ1). If in addition φ is bijective
and {u, v} ∈ E(Γ1) ⇐⇒ {φ(u), φ(v)} ∈ E(Γ2), then φ is a graph isomorphism and
graphs Γ1,Γ2 are isomorphic, which we denote by Γ1 ∼= Γ2. If Γ1 = Γ2, then a graph
homomorphism/graph isomorphism is a graph endomorphism/automorphism, respectively.
A graph Γ is self-complementary if there exists a graph isomorphism σ : Γ → Γ̄, which
is referred to as antimorphism or a complementing permutation. Observe that in this case
σ is also an antimorphism as a map Γ̄ → Γ. A graph Γ is regular if each vertex has
the same number of neighbors. If this number equals k, then we say that it is k-regular.
1Graphs K(5, 2), HGL2(F4), G(5, 2), C5C5 are all isomorphic to the Petersen graph.
M. Orel: The core of a vertex-transitive complementary prism 3
If for each pair of vertices u, v ∈ V (Γ) there exists an automorphism φ of Γ such that
u = φ(v), then Γ is a vertex-transitive graph. Clearly, each vertex-transitive graph is
regular. Lemma 2.1 can be found in [14, Corollaries 2.1.2, 2.1.3], where it is stated in a
more general settings.
Lemma 2.1. If a graph Γ is vertex-transitive, then α(Γ)ω(Γ) ≤ |V (Γ)|. If the equality
holds, then |C ∩ I| = 1 for each clique C and each independent set I that provide the
equality.
If a graph on n vertices is (n−12 )-regular, then n must be odd. Moreover, it follows
from the hand-shaking lemma that n = 4m+ 1 for some integer m ≥ 0. In particular, this
is true for all regular self-complementary graphs. By a result of Sachs [37] or Ringel [35],
each cycle in an antimorphism of a self-complementary graph has the length divisible by
four, except for one cycle of length one, in the case the order of the graph equals 1 modulo
4 (a proof in English can be found in [11, page 12]). Lemma 2.2 is a special case of this
fact, and is crucial in the proof of Theorem 3.3.
Lemma 2.2. If σ is an antimorphism of a regular self-complementary graph Γ, then there
exists a unique vertex v ∈ V (Γ) such that σ(v) = v.
A graph Γ is a core if each its endomorphism is an automorphism. Given a graph Γ, we
use core(Γ) to denote any subgraph of Γ that is a core and such that there exists some graph
homomorphism φ : Γ → core(Γ). Graph core(Γ) is referred to as the core of Γ. It is always
an induced subgraph and unique up to isomorphism [15, 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 χ(Γ) = ω(Γ). We remark that there always exists a retraction ψ : Γ → core(Γ), i.e.
a graph homomorphism that fixes each vertex in core(Γ). In fact, if φ : Γ → core(Γ) is any
graph homomorphism, then the restriction φ|V (core(Γ)) is invertible and the composition
(φ|V (core(Γ)))−1 ◦ φ is the required retraction. Lemma 2.3 is proved in [39, Theorem 3.2],
where it is stated in an old terminology. Its proof can be found also in [15, 17].
Lemma 2.3. If graph Γ is vertex-transitive, then core(Γ) is vertex-transitive.
Let Γ be a graph with the vertex set V (Γ) = {v1, . . . , vn}. The complementary prism
of Γ is the graph ΓΓ̄, which is obtained from the disjoint union of Γ and its complement Γ̄,
by adding an edge between each vertex in Γ and its copy in Γ̄. In this paper we use
the following notation. The vertex set of the complementary prism of graph Γ is the set
V (ΓΓ̄) =W1 ∪W2, where
W1 =W1(ΓΓ̄) = {(v1, 1), . . . , (vn, 1)} and W2 =W2(ΓΓ̄) = {(v1, 2), . . . , (vn, 2)}.
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 (Γ)
}
.
It follows from the definition that a complementary prism ΓΓ̄ is regular if and only if Γ is(
n−1
2
)
-regular (see also [7, Theorem 3.6]). The core of a complementary prism for general
graph Γ was recently studied in [28] (see also the arXiv version [31]). For regular case, the
following result was proved.
4 Ars Math. Contemp. 23 (2023) #P4.07
Lemma 2.4 ([28, Corollary 3.4]). Let Γ be any graph on n vertices that is
(
n−1
2
)
-regular.
Then one of the following three possibilities is true.
(i) Graph ΓΓ̄ 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(Γ̄).
The same conclusion can be obtained also if the core of ΓΓ̄ is regular and we exclude
some small graphs. Below, K2 is a complete graph on two vertices, and P3 is a path on
three vertices.
Lemma 2.5 ([28, Corollary 3.6]). Let Γ be any graph, which is not isomorphic to K2, K2,
P3, or P3. If core(ΓΓ̄) is regular, then one of the three possibilities in Lemma 2.4 is true.
Clearly, Lemma 2.4 is valid for each regular self-complementary graph Γ. The study of
such graphs and their vertex-transitive counterparts has origins in the papers [21, 37, 40],
which influenced a lot of research related to vertex-transitive self-complementary graphs
(see for example [2, 4, 8, 9, 12, 20, 22, 23, 24, 25, 27, 33, 34, 38, 41] and the references
therein). In this paper the aim is to to study the core of a complementary prism ΓΓ̄, where Γ
is vertex-transitive and self-complementary graph. The following observation is obtained
for free, with a double proof.
Corollary 2.6. If graph Γ is vertex-transitive and self-complementary graph, then one of
the three possibilities in Lemma 2.4 is true.
Proof. The claim follows directly from Lemma 2.4. The same claim is deduced also if we
combine Lemmas 2.5 and 2.3.
In [28] some examples of regular self-complementary graphs Γ are provided such that
the statement (ii) or (iii) in Lemma 2.4 is true. In this paper we show that this is not possi-
ble for a large class of vertex-transitive self-complementary graphs. It should be mentioned
that it was recently proved that a complementary prism ΓΓ̄ is vertex-transitive if and only
if Γ is vertex-transitive and self-complementary [31, Corollary 3.8]. Despite our proofs do
not rely on this result, it means that this paper studies the core of vertex-transitive comple-
mentary prisms.
3 Main results
The main result of this paper is Theorem 3.3. Propositions 3.1 and 3.2 are the stepping
stones towards its proof.
Proposition 3.1. Let Γ be a regular self-complementary graph. If Γ is a core, then ΓΓ̄ is a
core.
M. Orel: The core of a vertex-transitive complementary prism 5
Proof. Let core(ΓΓ̄) be any core of Γ and let n = |V (Γ)|. Since Γ is
(
n−1
2
)
-regular, one
of the statements (i), (ii), (iii) in Lemma 2.4 is true. Suppose that (iii) is correct, that is,
V (core(ΓΓ̄)) ⊆W2 (3.1)
and
core(ΓΓ̄) ∼= core(Γ̄). (3.2)
Since Γ̄ is a core, (3.2) implies that core(ΓΓ̄) ∼= Γ̄. Hence, (3.1) yields
V (core(ΓΓ̄)) =W2. (3.3)
Let ψ1(v) = (v, 1), for v ∈ V (Γ), be the canonical isomorphism between Γ and the
subgraph of ΓΓ̄, which is induced by the set W1. Similarly, let ψ2(v) = (v, 2), for v ∈
V (Γ), be the canonical isomorphism between Γ̄ and the subgraph induced by W2. If Ψ
is any retraction from ΓΓ̄ onto core(ΓΓ̄), and σ is any antimorphism between Γ̄ and Γ,
then the composition σ ◦ ψ−12 ◦ (Ψ|W1) ◦ ψ1 is an endomorphism of Γ. Since Γ is a
core, the restriction Ψ|W1 is an isomorphism between the subgraphs in ΓΓ̄ that are induced
by the sets W1 and W2, respectively. Consequently ψ−12 ◦ (Ψ|W1) ◦ ψ1 : Γ → Γ̄ is an
antimorphism. By Lemma 2.2, there exists v ∈ V (Γ) such that
(
ψ−12 ◦(Ψ|W1)◦ψ1
)
(v) = v.
Consequently, Ψ(v, 1) = (Ψ|W1)(v, 1) = (v, 2). Since Ψ is a retraction, (3.3) implies that
Ψ(v, 2) = (v, 2). Since {(v, 1), (v, 2)} is an edge in ΓΓ̄, we have a contradiction.
In the same way we see that (ii) in Lemma 2.4 is not possible, which means that ΓΓ̄ is
a core.
Proposition 3.2. If Γ is a vertex-transitive self-complementary graph on n > 1 vertices,
then core(ΓΓ̄) is not a complete graph.
Proof. We need to prove that χ(ΓΓ̄) > ω(ΓΓ̄). Since n > 1 and Γ is both self-complement-
ary and vertex-transitive, Lemma 2.1 implies that
ω(ΓΓ̄) = max{α(Γ), ω(Γ)} = ω(Γ) ≤
√
n.
Let I be any independent set in ΓΓ̄. Then I is a disjoint union of some sets I1 ⊆ W1 and
I2 ⊆W2. If we write Ii = {(u, i) : u ∈ Ji} for i ∈ {1, 2}, where J1, J2 ⊆ V (Γ), then
J1 ∩ J2 = ∅. (3.4)
Since J1 and J2 are an independent set and a clique in Γ, respectively, we have |J1| ≤
α(Γ) = ω(Γ) ≤
√
n and |J2| ≤ ω(Γ) =
√
n, while Lemma 2.1 and (3.4) imply that
|J1| · |J2| < n. Hence, |I| = |J1|+ |J2| < 2
√
n, and therefore
χ(ΓΓ̄) ≥ |V (ΓΓ̄)|
α(ΓΓ̄)
>
2n
2
√
n
=
√
n ≥ ω(ΓΓ̄).
Theorem 3.3. Let Γ be a vertex-transitive self-complementary graph. If Γ is either a core
or its core is a complete graph, then ΓΓ̄ is a core.
6 Ars Math. Contemp. 23 (2023) #P4.07
Proof. If Γ is a core, then the claim follows from Proposition 3.1. Hence, we may as-
sume that Γ has a complete core and more than one vertex. By Corollary 2.6, one of the
statements (i), (ii), (iii) in Lemma 2.4 is true for core(ΓΓ̄). If (ii) or (iii) is correct, then
the self-complementarity implies that core(ΓΓ̄) is complete, which contradicts Proposi-
tion 3.2.
Remark 3.4. The claims in Proposition 3.2 and Theorem 3.3 are not true for some reg-
ular self-complementary graphs. In fact, there exists a regular self-complementary graph
Γ with a complete core such that core(ΓΓ̄) is complete (see [28, Example 3.5] or [31,
Example 5.5]).
Recall that a k-regular graph on n vertices is strongly regular with parameters (n, k, λ, µ)
if each pair of adjacent vertices has λ common neighbors and each pair of distinct non-
adjacent vertices has µ common neighbors. Theorem 3.5 was very recently proved in [28]
(see also the arXiv version [31, Theorem 5.7]). The proof relied on application of Lemma 2.4
together with several properties of the Lovász theta function and the graph spectrum. Here
we provide a sketch of an alternative proof that essentially copies the proofs in this section
and applies a remarkable result that Roberson recently proved [36].
Theorem 3.5 ([28]). If Γ is a strongly regular self-complementary graph, then ΓΓ̄ is a
core.
Sketch of a proof. To see that ΓΓ̄ does not have a complete core, we copy the proof of
Proposition 3.2, where we replace the application of Lemma 2.1 by its analog that can
be found in [14, Corolarry 3.8.6 and Theorem 3.8.4] and is valid for all strongly regular
graphs. From [36, Corollary 3.6] it follows that Γ is either a core or its core is complete.
Then we just copy the proof of Theorem 3.3, where we rely directly on Lemma 2.4 instead
on Corollary 2.6.
Recall from the introduction that many ‘nice’ graphs are either cores or their cores are
complete. Hence it is expected that many vertex-transitive self-complementary graphs fulfil
the assumptions in Theorem 3.3. Consequently, we state the following open problem.
Problem 3.6. Does there exist a vertex-transitive self-complementary graph Γ such that
ΓΓ̄ is not a core?
Note that edge-transitive self-complementary graphs are also arc-transitive (see [11]).
Since self-complementary graphs are always connected (cf. [11]), it follows that each edge-
transitive self-complementary graph is also vertex-transitive. However, such graphs are
always strongly regular (cf. [11]) and therefore their complementary prisms are cores by
Theorem 3.5. Despite the orders of vertex-transitive self-complementary graphs were fully
determined in [27], there is a major gap between the understanding of vertex-transitive
self-complementary graphs and the understanding of edge-transitive self-complementary
graphs. In fact, the later were completely characterized in [33]. Moreover, the first non-
Cayley vertex-transitive self-complementary graph was constructed only in 2001 [24], and
the construction is highly nontrivial. We believe that all these facts indicate that Prob-
lem 3.6 may be challenging.
In a distinct paper [32], we consider the only families of vertex-transitive self-comple-
mentary graphs the author is aware of, which are neither cores nor their cores are complete
graphs (i.e. they do not satisfy the assumption in Theorem 3.3). Unfortunately they do not
solve Problem 3.6.
M. Orel: The core of a vertex-transitive complementary prism 7
ORCID iDs
Marko Orel https://orcid.org/0000-0002-2544-2986
References
[1] A. Alhashim, W. J. Desormeaux and T. W. Haynes, Roman domination in complementary
prisms, Australas. J. Comb. 68 (2017), 218–228, https://ajc.maths.uq.edu.au/
pdf/68/ajc_v68_p218.pdf.
[2] B. Alspach, J. Morris and V. Vilfred, Self-complementary circulant graphs, Ars Comb. 53
(1999), 187–191.
[3] R. M. Barbosa, M. R. Cappelle and E. M. M. Coelho, Maximal independent sets in comple-
mentary prism graphs, Ars Comb. 137 (2018), 283–294.
[4] R. A. Beezer, Sylow subgraphs in self-complementary vertex transitive graphs, Expo. Math.
24 (2006), 185–194, doi:10.1016/j.exmath.2005.09.003, https://doi.org/10.1016/
j.exmath.2005.09.003.
[5] A. E. Brouwer and W. H. Haemers, Spectra of Graphs, Universitext, Springer, New York, 2012.
[6] 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.
[7] 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.
[8] E. Dobson, On self-complementary vertex-transitive graphs of order a product of distinct
primes, Ars Comb. 71 (2004), 249–256.
[9] E. Dobson and M. Šajna, Almost self-complementary circulant graphs, Discrete Math. 278
(2004), 23–44, doi:10.1016/j.disc.2003.05.002, https://doi.org/10.1016/j.disc.
2003.05.002.
[10] M. A. Duarte, L. Penso, D. Rautenbach and U. d. S. Souza, Complexity properties of com-
plementary prisms, J. Comb. Optim. 33 (2017), 365–372, doi:10.1007/s10878-015-9968-5,
https://doi.org/10.1007/s10878-015-9968-5.
[11] 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.
[12] D. Fronček, A. Rosa and J. Širáň, The existence of selfcomplementary circulant graphs, Euro-
pean J. Comb. 17 (1996), 625–628, doi:10.1006/eujc.1996.0053, https://doi.org/10.
1006/eujc.1996.0053.
[13] I. Garcı́a-Marco and K. Knauer, Beyond symmetry in generalized petersen graphs, 2022,
arXiv:2202.06785 [math.CO].
[14] 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.
[15] C. Godsil and G. Royle, Algebraic Graph Theory, volume 207 of Grad. Texts Math., Springer,
New York, 2001.
[16] 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.
8 Ars Math. Contemp. 23 (2023) #P4.07
[17] 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.
[18] 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.
[19] T. W. Haynes, M. A. Henning and L. C. van der Merwe, Domination and total domination in
complementary prisms, J. Comb. Optim. 18 (2009), 23–37, doi:10.1007/s10878-007-9135-8,
https://doi.org/10.1007/s10878-007-9135-8.
[20] R. Jajcay and C. H. Li, Constructions of self-complementary circulants with no multiplica-
tive isomorphisms, European J. Comb. 22 (2001), 1093–1100, doi:10.1006/eujc.2001.0529,
https://doi.org/10.1006/eujc.2001.0529.
[21] A. Kotzig, Selected open problems in graph theory, in: J. A. Bondy and U. S. R. Murty (eds.),
Graph Theory and Related Topics, Academic Press, New York, pp. 358–367, 1979.
[22] C. H. Li, On self-complementary vertex-transitive graphs, Comm. Algebra 25 (1997),
3903–3908, doi:10.1080/00927879708826094, https://doi.org/10.1080/
00927879708826094.
[23] C. H. Li, On finite graphs that are self-complementary and vertex-transitive, Aus-
tralas. J. Comb. 18 (1998), 147–155, https://ajc.maths.uq.edu.au/pdf/18/
ocr-ajc-v18-p147.pdf.
[24] 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.
[25] C. H. Li, G. Rao and S. J. Song, On finite self-complementary metacirculants, J. Algebraic
Comb. 40 (2014), 1135–1144, doi:10.1007/s10801-014-0522-9, https://doi.org/10.
1007/s10801-014-0522-9.
[26] D. Meierling, F. Protti, D. Rautenbach and A. R. de Almeida, Cycles in complementary prisms,
Discrete Appl. Math. 193 (2015), 180–186, doi:10.1016/j.dam.2015.04.016, https://doi.
org/10.1016/j.dam.2015.04.016.
[27] 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.
[28] M. Orel, The core of a complementary prism, accepted for publication in Journal of Algebraic
Combinatorics.
[29] 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.
[30] 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.
[31] M. Orel, A family of non-Cayley cores based on vertex-transitive or strongly regular self-
complementary graphs, 2021, arXiv:2110.10416 [math.CO].
[32] M. Orel, The core of a vertex-transitive complementary prism of a lexicographic product, Art
Discrete Appl. Math. (2023), doi:10.26493/2590-9770.1623.7f0, https://doi.org/10.
26493/2590-9770.1623.7f0.
M. Orel: The core of a vertex-transitive complementary prism 9
[33] W. Peisert, All self-complementary symmetric graphs, J. Algebra 240 (2001), 209–229, doi:
10.1006/jabr.2000.8714, https://doi.org/10.1006/jabr.2000.8714.
[34] S. B. Rao, On regular and strongly-regular self-complementary graphs, Discrete Math.
54 (1985), 73–82, doi:10.1016/0012-365X(85)90063-9, https://doi.org/10.1016/
0012-365X(85)90063-9.
[35] G. Ringel, Selbstkomplementäre Graphen, Arch. Math. (Basel) 14 (1963), 354–358, doi:10.
1007/bf01234967, https://doi.org/10.1007/bf01234967.
[36] 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.
[37] H. Sachs, Über selbstkomplementäre Graphen, Publ. Math. Debrecen 9 (1962), 270–288.
[38] D. A. Suprunenko, Self-complementary graphs, Cybern. Syst. Anal. 21 (1985), 559–567, doi:
10.1007/bf01074707, https://doi.org/10.1007/bf01074707.
[39] E. Welzl, Symmetric graphs and interpretations, J. Comb. Theory, Ser. B 37 (1984), 235–244,
doi:10.1016/0095-8956(84)90056-X, https://doi.org/10.1016/0095-8956(84)
90056-X.
[40] B. Zelinka, Self-complementary vertex-transitive undirected graphs, Math. Slovaca 29 (1979),
91–95.
[41] H. Zhang, Self-complementary symmetric graphs, J. Graph Theory 16 (1992), 1–5, doi:10.
1002/jgt.3190160102, https://doi.org/10.1002/jgt.3190160102.