A graph is called \(t\)-existentially closed (\(t\)-e.c.) if it satisfies the following adjacency property: for every \(t\)-element subset \(A\) of the vertices, and for every subset \(B \subseteq A\), there exists a vertex \(x \in A\) that is adjacent to all vertices in \(B\) and to none of the vertices in \(A \setminus B\). A \(t\)-e.c. graph is critical if removing any single vertex results in a graph that is no longer \(t\)-e.c. This paper investigates \(2\)-e.c. critical Cayley graphs and vertex-transitive graphs, providing explicit constructions of \(2\)-e.c. critical Cayley graphs on cyclic groups. It is shown that a \(2\)-e.c. critical Cayley graph (as well as vertex-transitive graphs) of order \(n\) exists if and only if \(n \geq 9\) and \(n \notin \{10, 11, 14\}\). Additionally, this paper examines the numbers of \(2\)-e.c. (critical) vertex-transitive graphs among all vertex-transitive graphs for small orders, and presents detailed observations on some \(2\)-e.c. and \(3\)-e.c. vertex-transitive graphs.
A graph is called \(t\)-existentially closed or simply \(t\)-e.c. if it satisfies the following adjacency property: for every \(t\)-element subset \(A\) of the vertices, and for every subset \(B \subseteq A\), there exists a vertex \(x \in A\) that is adjacent to all vertices in \(B\) and to none of the vertices in \(A \setminus B\). It is clear that a \((t+1)\)-e.c. graph is also a \(t\)-e.c. graph.
Adjacency properties, such as the \(t\)-e.c. property, were first investigated in a seminal paper on random graphs by Erdős and Rényi [11] published in 1963. The formal notion of \(t\)-e.c.graphs was later studied by Caccetta, Erdős, and Vijayan [10], where they were referred to as graphs with property \(P(t)\). The study of \(t\)-e.c. graphs has gained significant attention due to their natural connections to random graphs and mathematical logic. The countable random graph is known to be \(t\)-e.c. for all \(t\). Equivalently speaking, for any fixed \(t\), almost all finite graphs are \(t\)-e.c. However, explicit constructions of \(t\)-e.c. graphs are less well known, drawing attention to the notable gap between random and deterministic structures.
Among deterministic (i.e., non-randomized) constructions, Paley graphs are the best-known family of \(t\)-e.c.graphs for general \(t\). It was independently proven in [3, 4] that the Paley graph of order \(q\) is \(t\)-e.c. if \(q > t^2 2^{2t-2}\). Beyond Paley graphs, explicit constructions of \(t\)-e.c.graphs with \(t \ge 3\) include those based on block designs [12, 15, 18], finite geometries [2, 22], Hadamard matrices [8], permutation polynomials over finite fields [14], quadratic residues modulo \(q^e\) (as generalizations of Paley graphs) [20], and line graphs [9].
The search for smallest \(t\)-e.c. graphs for \(t \ge 3\) remains a challenging research problem. The smallest \(2\)-e.c. graph has order \(9\), which is the Paley graph of order \(9\). The smallest order of a \(3\)-e.c. graph is known to be at least \(24\), with the smallest known example having order \(28\). For further details, see [5, 13].
In this work, we focus on a special class of \(t\)-e.c. graphs, called \(t\)-e.c. critical graphs, first introduced by Bonato and Cameron [6]. A \(t\)-e.c. graph is critical if removing any single vertex results in a graph that is no longer \(t\)-e.c. Bonato and Cameron [6] classified \(1\)-e.c. critical graphs and constructed \(2\)-e.c. critical graphs of order greater than \(9\). They provided an explicit construction for \(2\)-e.c. critical graphs for orders \(n \equiv 1 \pmod{4}\) and recursive constructions for \(n \equiv 0, 2, 3 \pmod{4}\) using a graph operation called replication. The \(2\)-e.c. critical graphs they constructed are not regular.
In contrast, most known explicit \(t\)-e.c. graphs are regular. Notably, the best-known \(t\)-e.c. graphs, the Paley graphs, are Cayley graphs and are therefore both regular and vertex-transitive. These observations motivate further exploration of regular or vertex-transitive \(t\)-e.c. critical graphs, with particular interest in Cayley graphs exhibiting \(2\)-e.c. criticality.
A graph is vertex-transitive if, for any two distinct vertices, there exists an automorphism of the graph mapping one vertex to the other. Intuitively, this means that all vertices in a vertex-transitive graph behave identically. A Cayley graph \(\Gamma = \mathop{\mathrm{Cay}}(G, S)\) is defined using a finite group \(G\) and a generating set \(S \subseteq G\), where \(1 \notin S\) and \(S^{-1} = S\), with \(S^{-1}:=\{ s^{-1} \mid s \in S\}\). The vertex set is \(V(\Gamma) = G\), and edge set is \(E(\Gamma) = \{ (g, sg) \mid g \in G, s \in S \}\). By construction, every Cayley graph is vertex-transitive.
Notably, the Paley graph of order \(q\) can be regarded as the Cayley graph on \((\mathbb{F}_q, +)\) with the generating set \(\mathbb{F}_q^\square\), where \(\mathbb{F}_q\) denotes the finite field of order \(q\), and \(\mathbb{F}_q^\square\) denotes the set of nonzero quadratic residues in \(\mathbb{F}_q\). However, Paley graphs have increasingly strong e.c. properties as their order grows, making them unsuitable as a family of critical \(t\)-e.c. graphs for a fixed \(t\).
In this work, we investigate the existence and constructions of \(2\)-e.c. critical Cayley graphs, which are inherently regular and vertex-transitive. Note that removing a vertex from a \(2\)-e.c. critical Cayley graph destroys both its vertex-transitivity and regularity.
The main theorems are as follows:
Theorem 1.1. A \(2\)-e.c. critical Cayley graph on the cyclic group of order \(n\) exists if and only if \(n \ge 12\) and \(n \neq 14\).
Theorem 1.2. A \(2\)-e.c. critical Cayley graph of order \(n\) exists if and only if \(n \ge 9\) and \(n \notin \{10, 11, 14\}\).
The remainder of the paper is organized as follows: In Section 2, we present explicit constructions for \(2\)-e.c. critical Cayley graphs on cyclic groups. Section 3 focuses on the non-existence results for \(2\)-e.c. critical Cayley graphs, with the proofs of Theorems 1.1 and 1.2 following thereafter. In Section 4, we provide further remarks on the existence of \(2\)-e.c. critical vertex-transitive graphs that are not Cayley graphs and explore some observations on \(3\)-e.c. vertex-transitive graphs.
For integer \(n \ge 2\), let \(\mathbb{Z}_n\) denote the residue ring of integers by modulo \(n\), and let \(\mathbb{Z}_n^\ast := \mathbb{Z}_n \setminus \{0\}\). Throughout this section, arithmetic is performed in the additive group of \(\mathbb{Z}_n\). For \(0 \le a < b \le n-1\), we denote the subset of consecutive elements in \(\mathbb{Z}_n\) by the interval notation \([a, b] := \{a, a+1, \ldots, b\}\).
For any subsets \(X, Y \subseteq \mathbb{Z}_n\), we define \(X – Y := \{ x- y \mid x \in X, y \in Y\}\). Moreover, for any \(X \subseteq \mathbb{Z}_n\), we define \(-X := \{ -x \mid x \in X\}\) and \(X^\complement := \mathbb{Z}_n^\ast \setminus X\).
Lemma 2.1. Let \(S\) be a symmetric subset of \(\mathbb{Z}_n^\ast\), i.e., \(0 \notin S\) and \(S = -S\). Then \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) is \(2\)-e.c. if and only if \[S – S = \mathbb{Z}_n, \quad S – S^\complement = \mathbb{Z}_n^\ast, \quad \text{and} \quad S^\complement – S^\complement = \mathbb{Z}_n.\]
Furthermore, when \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) is \(2\)-e.c., it is critical if there exists \(w \in \mathbb{Z}_n^\ast\) such that at least one of the following hold:
\(\left|{S \cap (S+w)}\right| = 1\),
\(\left|{S \cap (S^\complement+w)}\right| = 1\),
\(\left|{S^\complement \cap (S^\complement+w)}\right| = 1\).
Proof. Due to the vertex-transitivity of Cayley graphs, \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) is \(2\)-e.c. if and only if, for any vertex \(w \in \mathbb{Z}_n \setminus \{0\}\), there exist four vertices \(z_{11}\), \(z_{10}\), \(z_{01}\), and \(z_{00}\) in \(\mathbb{Z}_n \setminus \{0, w\}\) such that the following conditions are satisfied:
(i) \(z_{11}\) is adjacent to both \(0\) and \(w\);
(ii) \(z_{10}\) is adjacent to \(0\) but not adjacent to \(w\);
(iii) \(z_{01}\) is not adjacent to \(0\) but adjacent to \(w\);
(iv) \(z_{00}\) is not adjacent \(0\) and not adjacent to \(w\) either.
Using the definition of Cayley graphs, the above conditions can be rewritten as follows:
(i’) \(z_{11} – 0 \in S\) and \(z_{11}-w \in S\);
(ii’) \(z_{10} – 0 \in S\) and \(z_{10}-w \in S^\complement\);
(iii’) \(z_{01} – 0 \in S^\complement\) and \(z_{01} – w\in S\);
(iv’) \(z_{00} – 0 \in S^\complement\) and \(z_{00} – w \in S^\complement\).
This is equivalent to stating that \(U \cap (V + w)\) is non-empty for any \(w \in \mathbb{Z}_n^\ast\) and any combination of \(U, V \in S, S^\complement\). In other words, for an arbitrarily chosen nonzero \(w\), there exist elements \(u \in U\) and \(v \in V\) such that \(w = u – v\), i.e., \(w \in U-V\).
Thus, the necessary and sufficient condition for \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) to be \(2\)-e.c. is \(\mathbb{Z}_n^\ast \subseteq U – V\) for any \(U, V \in \{ S, S^\complement\}\). Additionally, it follows that \(0 \in S-S\) and \(0 \in S^\complement – S^\complement\), and \(0 \notin S – S^\complement\). Finally, noting that \(\mathbb{Z}_n^\ast \subseteq S – S^\complement\) is equivalent to \(\mathbb{Z}_n^\ast \subseteq S^\complement – S\), the proof of the first half is complete.
Next, suppose \(w\) is a nonzero element in \(\mathbb{Z}_n\) such that \(\left|{U \cap (V+w)}\right| = 1\) (equivalently, \(\left|{(U-w)\cap V}\right| = 1\)) for some \(U, V \in \{ S, S^\complement\}\). Let \(z\) be the unique element in \(U \cap (V+w)\). Deleting the vertex \(z\) from \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) results in the following violations to the \(2\)-e.c. property with respect to vertices \(0\) and \(w\):
Condition (i) fails when \(U=S\) and \(V = S\),
Condition (ii) fails when \(U=S\) and \(V = S^\complement\),
Condition (iii) fails when \(U=S^\complement\) and \(V = S\),
Condition (iv) fails when \(U=S^\complement\) and \(V = S^\complement\).
By applying the vertex-transitivity of Cayley graphs again, we conclude that deleting any vertex from \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) will destroy the \(2\)-e.c. property. Therefore, \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) is \(2\)-e.c. critical. ◻
Now, we explicitly provide the generating set satisfying the conditions in Lemma 2.1 for \(n\) in different congruence classes.
Lemma 2.2. Let \(n \ge 13\) be an odd integer. Let \(k = \left\lfloor{n/4}\right\rfloor\), \[S_0 = [1, k-1] \cup \{k+1\},\] and \(S= S_0 \cup -S_0\). Then, \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) is \(2\)-e.c. critical.
Proof. Consider the case \(n = 4k + 1\). We have \[\begin{aligned} S &= [1, k-1] \cup \{k+1\} \cup \{ 3k \} \cup [3k+2, 4k], \\ S^\complement &= \{k\} \cup [k+2, 3k-1] \cup \{3k+1\}. \end{aligned}\] Through careful calculations, we obtain \(S – S = \mathbb{Z}_n\), \(S – S^\complement = \mathbb{Z}_n^\ast\), and \(S^\complement – S^\complement = \mathbb{Z}_n\). For the detailed calculations, refer to Tables 1, 2, and 3, respectively. Moreover, it can be verified that \[\begin{aligned} S^\complement \cap \left(S^\complement + 2k\right) &= \{k\}, \\ S^\complement \cap \left(S^\complement + 2k+1\right) &= \{3k+1\}. \end{aligned}\]
| \(X \ \backslash \ Y\) | \([1, k-1]\) | \(\{k+1\}\) | \(\{3k\}\) | \([3k+2, 4k]\) |
| \([1, k-1]\) | \([3k+3, 4k] \cup [0, k-2]\) | \([3k+1, 4k-1]\) | \([k+2, 2k]\) | \([2, 2k-2]\) |
| \(\{k+1\}\) | \([2,k]\) | \(\{0\}\) | \(\{2k+2\}\) | \([k+2, 2k]\) |
| \(\{3k\}\)? | \([2k+1, 3k-1]\) | \(\{2k-1\}\) | \(\{0\}\) | \([3k+1, 4k-1]\)? |
| \([3k+2, 4k]\) | \([2k+3, 4k-1]\) | \([2k+1, 3k-1]\) | \([2,k]\) | \([3k+3, 4k] \cup [0, k-2]\) |
| \(X \ \backslash \ Y\) | \(\{k\}\) | \([k+2, 3k-1]\) | \(\{3k+1\}\) |
| \([1, k-1]\) | \([3k+2, 4k]\) | \([k+3, 4k-2]\) | \([k+1, 2k-1]\) |
| \(\{k+1\}\) | \(\{1\}\) | \([2k+3, 4k]\) | \(\{2k+1\}\) |
| \(\{3k\}\) | \(\{2k\}\) | \([1, 2k-2]\) | \(\{4k\}\) |
| \([3k+2, 4k]\) | \([2k+2, 3k]\) | \([3, 3k-2]\) | \([1, k-1]\) |
| \(X \backslash Y\) | \(\{k\}\) | \([k+2, 3k-1]\) | \(\{3k+1\}\) |
| \(\{k\}\) | \(\{0\}\) | \([2k+2, 4k-1]\) | \(\{\underline{2k}\}\) |
| \([k+2, 3k-1]\) | \([2, 2k-1]\) | \([2k+4, 4k] \cup [0, 2k-3]\) | \([2k+2, 4k-1]\) |
| \(\{3k+1\}\) | \(\{\underline{2k+1}\}\) | \([2, 2k-1]\) | \(\{0\}\) |
See Table 3, where the underlined elements indicate the desired element \(w\) for applying Lemma 2.1. It follows from Lemma 2.1 that \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) is \(2\)-e.c. critical when \(n = 4k+1\) with \(k \ge 3\).
Consider the case \(n = 4k + 3\). We have \[\begin{aligned} S &= [1, k-1] \cup \{k+1\} \cup \{ 3k+2 \} \cup [3k+4, 4k+2], \\ S^\complement &= \{k\} \cup [k+2, 3k+1] \cup \{3k+3\}. \end{aligned}\] Similarly to the previous case, we obtain \(S – S = \mathbb{Z}_n\), \(S – S^\complement = \mathbb{Z}_n^\ast\), and \(S^\complement – S^\complement = \mathbb{Z}_n\). For the detailed calculations, refer to Tables 4, 5, and 6, respectively. Moreover, it is observed that \[\begin{aligned} S \cap \left(S + 2k+2\right) &= \{k+1\}, \\ S \cap \left(S + 2k+1\right) &= \{3k+2\}. \end{aligned}\]
| \(X \ \backslash \ Y\) | \(\{k\}\) | \([k+2, 3k+1]\) | \(\{3k+2\}\) | \([3k+4, 4k+2]\) |
| \([1, k-1]\) | \([3k+5, 4k+2] \cup [0, k-2]\) | \([3k+3, 4k+1]\) | \([k+2, 2k]\) | \([2, 2k-2]\) |
| \(\{k+1\}\) | \([2, k]\) | \(\{0\}\) | \(\{\underline{2k+2}\}\) | \([k+2, 2k]\) |
| \(\{3k+2\}\) | \([2k+3, 3k+1]\) | \(\{\underline{2k+1}\}\) | \(\{0\}\) | \([3k+3, 4k+1]\) |
| \([3k+4, 4k+2]\) | \([2k+5, 4k+1]\) | \([2k+3, 3k+1]\) | \([2, k]\) | \([3k+5, 4k+2] \cup [0, k-2]\) |
See Table 4, where the underlined elements indicate the desired element \(w\) for applying Lemma 2.1. It follows from Lemma 2.1 that \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) is \(2\)-e.c. critical when \(n = 4k+3\) with \(k \ge 3\). ◻
| \(X \ \backslash \ Y\) | \(\{k\}\) | \([k+2, 3k+1]\) | \(\{3k+3\}\) |
| \([1, k-1]\) | \([3k+4, 4k+2]\) | \([k+3, 4k]\) | \([k+1, 2k-1]\) |
| \(\{k+1\}\) | \(\{1\}\) | \([2k+3, 4k+2]\) | \(\{2k+1\}\) |
| \(\{3k+2\}\) | \(\{2k+2\}\) | \([1, 2k]\) | \(\{4k+2\}\) |
| \([3k+4, 4k+2]\) | \([2k+4, 3k+2]\) | \([3, 3k]\) | \([1, k-1]\) |
| \(X \ \backslash \ Y\) | \(\{k\}\) | \([k+2, 3k+1]\) | \(\{3k+3\}\) |
| \(\{k\}\) | \(\{0\}\) | \([2k+2, 4k+1]\) | \(\{2k\}\) |
| \([k+2, 3k+1]\) | \([2, 2k+1]\) | \([2k+4, 4k+2] \cup [0, 2k-1]\) | \([2k+2, 4k+1]\) |
| \(\{3k+3\}\) | \(\{2k+3\}\) | \([2, 2k+1]\) | \(\{0\}\) |
Remark 2.3. For \(n \in \{9, 11\}\), we have \(k=2\), and Lemma 2.2 gives a \(4\)-regular graph \(\mathop{\mathrm{Cay}}(\mathbb{Z}_{n}, S)\) where \(S=\{\pm 1, \pm 3\}\). It is easily verified that \(S \cap (S+1) = \emptyset\), which means that there is no vertex adjacent to both \(0\) and \(1\) in this Cayley graph. This implies that the graph is not \(2\)-e.c.
Lemma 2.4. Let \(n \ge 12\) be an integer with \(n \equiv 0 \pmod{4}\). Let \(k = {n/4}\), \[S_0 = [1, k-1] \cup \{k+2\},\] and \(S= S_0 \cup -S_0\). Then, \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) is \(2\)-e.c. critical.
Proof. The sets \(S\) and \(S^\complement\) can be explicitly expressed as follows: \[\begin{aligned} S &= [1, k-1] \cup \{k+2\} \cup \{ 3k-2 \} \cup [3k+1, 4k-1], \\ S^\complement &= \{k, k+1\} \cup [k+3, 3k-3] \cup \{3k-1, 3k\}. \end{aligned}\] Through careful calculations, we obtain \(S – S = \mathbb{Z}_n\), \(S – S^\complement = \mathbb{Z}_n^\ast\), and \(S^\complement – S^\complement = \mathbb{Z}_n\). For the detailed calculations, see Tables 7, 8, and 9, respectively. Moreover, it is observed that \[\begin{aligned} S^\complement \cap \left(S^\complement + 2k+2\right) &= \{k+1\}, \\ S^\complement \cap \left(S^\complement + 2k-2\right) &= \{3k-1\}. \end{aligned}\]
| \(X \ \backslash \ Y\) | \([1, k-1]\) | \(\{k+2\}\) | \(\{3k-2\}\) | \([3k+1, 4k-1]\) |
| \([1, k-1]\) | \([3k+2, 4k-1] \cup [0, k-2]\) | \([3k-1, 4k-3]\) | \([k+3, 2k+1]\) | \([2, 2k-2]\) |
| \(\{k+2\}\) | \([3, k+1]\) | \(\{0\}\) | \(\{2k+4\}\) | \([k+3, 2k+1]\) |
| \(\{3k-2\}\) | \([2k-1, 3k-3]\) | \(\{2k-4\}\) | \(\{0\}\) | \([3k-1, 4k-3]\) |
| \([3k+1, 4k-1]\) | \([2k+2, 4k-2]\) | \([2k-1, 3k-3]\) | \([3, k+1]\) | \([3k+2, 4k-1] \cup [0, k-2]\) |
| \(X \ \backslash \ Y\) | \(\{k, k+1\}\) | \([k+3, 3k-3]\) | \(\{3k-1, 3k\}\) |
| \([1, k-1]\) | \([3k, 4k-1]\) | \([k+4, 4k-4]\) | \([k+1, 2k]\) |
| \(\{k+2\}\) | \(\{1, 2\}\) | \([2k+5, 4k-1]\) | \(\{2k+2, 2k+3\}\) |
| \(\{3k-2\}\) | \(\{2k-2, 2k-3\}\) | \([1, 2k-5]\) | \(\{4k-2, 4k-1\}\) |
| \([3k+1, 4k-1]\) | \([2k, 3k-1]\) | \([4, 3k-4]\) | \([1, k]\) |
| \(X \ \backslash \ Y\) | \(\{k, k+1\}\) | \([k+3, 3k-3]\) | \(\{3k-1, 3k\}\) |
| \(\{k, k+1\}\) | \(\{4k-1, 0, 1\}\) | \([2k+3, 4k-2]\) | \(\{2k, 2k+1, \underline{2k+2}\}\) |
| \([k+3, 3k-3]\) | \([2, 2k-3]\) | \([2k+6, 4k-1] \cup [0, 2k-6]\) | \([2k+3, 4k-2]\) |
| \(\{3k-1, 3k\}\) | \(\{\underline{2k-2}, 2k-1, 2k\}\) | \([2, 2k-3]\) | \(\{4k-1, 0, 1\}\) |
See Table 9, where the underlined elements show the desired element \(w\) for applying Lemma 2.1. It follows from Lemma 2.1 that \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) is \(2\)-e.c. critical when \(n = 4k\) with \(k \ge 3\). ◻
Lemma 2.5. Let \(n \ge 18\) be an integer with \(n \equiv 2 \pmod{8}\). Let \(h = \left\lfloor{n/8}\right\rfloor\), \[S_0 = [1, h+1] \cup [3h+2, 4h+1]\] and \(S= S_0 \cup -S_0\). Then, \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) is \(2\)-e.c. critical.
Proof. The sets \(S\) and \(S^\complement\) can be explicitly expressed as follows: \[\begin{aligned} S &= [1, h+1] \cup [3h+2, 5h] \cup [7h+1, 8h+1], \\ S^\complement &= [h+2, 3h+1] \cup [5h+1, 7h]. \end{aligned}\]
Through careful calculations, we obtain \(S – S = \mathbb{Z}_n\), \(S – S^\complement = \mathbb{Z}_n^\ast\), and \(S^\complement – S^\complement = \mathbb{Z}_n\). For the detailed calculations, see Tables 10, 11, and 12, respectively. Moreover, it is observed that \[\begin{aligned} S^\complement \cap \left(S^\complement + 2h\right) &= \{5h+1\}, \\ S^\complement \cap \left(S^\complement + 6h+2\right) &= \{3h+1\}. \end{aligned}\]
| \(X \ \setminus \ Y\) | \([1, h+1]\) | \([3h+2, 5h]\) | \([7h+1, 8h+1]\) |
| \([1, h+1]\) | \([7h+2, 8h+1] \cup [0, h]\) | \([3h+3, 6h+1]\) | \([2, 2h+2]\) |
| \([3h+2, 5h]\) | \([2h+1, 5h-1]\) | \([6h+4, 8h+1] \cup [0, 2h-2]\) | \([3h+3, 6h+1]\) |
| \([7h+1, 8h+1]\) | \([6h, 8h]\) | \([2h+1, 5h-1]\) | \([7h+2, 8h+1] \cup [0, h]\) |
| \(X \ \setminus \ Y\) | \([h+2, 3h+1]\) | \([5h+1, 7h]\) |
| \([1, h+1]\) | \([5h+2, 8h+1]\) | \([h+3, 4h+2]\) |
| \([3h+2, 5h]\) | \([1, 4h-2]\) | \([4h+4, 8h+1]\) |
| \([7h+1, 8h+1]\) | \([4h, 7h-1]\) | \([1, 3h]\) |
| X \ Y | [h+2, 3h] | {3h+2, 3h+3} | {5h+3, 5h+4} | [5h+6, 7h+4] |
|---|---|---|---|---|
| [h+2, 3h] | [6h+8, 8h+5] ∪ [0, 2h-2] | [6h+5, 8h+4] | [4h+4, 6h+3] | [2h+4, 6h] |
| {3h+2, 3h+3} | [2, 2h+1] | {8h+5, 0, 1} | {6h+4, 6h+5, 6h+6} | [4h+4, 6h+3] |
| {5h+3, 5h+4} | [2h+3, 4h+2] | {2h, 2h+1, 2h+2} | {8h+5, 0, 1} | [6h+5, 8h+4] |
| [5h+6, 7h+4] | [2h+6, 6h+2] | [2h+3, 4h+2] | [2, 2h+1] | [6h+8, 8h+5] ∪ [0, 2h-2] |
See Table 12, where the underlined elements indicate the desired element \(w\) for applying Lemma 2.1. It follows from Lemma 2.1 that \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) is \(2\)-e.c. c ritical when \(n = 8h+2\) with \(h \ge 2\). ◻
Remark 2.6. For \(n = 10\), we have \(h=1\), and Lemma 2.5 gives a \(5\)-regular graph \(\mathop{\mathrm{Cay}}(\mathbb{Z}_{10}, S)\) where \(S=\{\pm 1, \pm 2, 5\}\). It is easily verified that \(S \cap (S+5) = \emptyset\), which means that, there is no vertex adjacent to both \(0\) and \(5\) in this Cayley graph. This implies that the graph is not \(2\)-e.c.
Lemma 2.7. Let \(n \ge 22\) be an integer with \(n \equiv 6 \pmod{8}\). Let \(h = \left\lfloor{n/8}\right\rfloor\), \[S_0 = [1, h+1] \cup \{3h+1\} \cup [3h+4, 4h+3]\] and \(S= S_0 \cup -S_0\). Then, \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) is \(2\)-e.c. critical.
Proof. The sets \(S\) and \(S^\complement\) can be explicitly expressed as follows: \[\begin{aligned} S &= [1, h+1] \cup \{3h+1\} \cup [3h+4, 5h+2] \cup \{5h+5\} \cup [7h+5, 8h+5], \\ S^\complement &= [h+2, 3h] \cup \{3h+2, 3h+3\} \cup \{5h+3, 5h+4\} \cup [5h+6, 7h+4]. \end{aligned}\] Through careful calculations, we obtain \(S – S = \mathbb{Z}_n\), \(S – S^\complement = \mathbb{Z}_n^\ast\), and \(S^\complement – S^\complement = \mathbb{Z}_n\). For the detailed calculations, see Tables 13, 14, and 15, respectively. Moreover, it is observed that \[\begin{aligned} S^\complement \cap \left(S^\complement + 2h+2\right) &= \{5h+4\}, \\ S^\complement \cap \left(S^\complement + 6h+4\right) &= \{3h+2\}. \end{aligned}\]
See Table 15, where the underlined elements indicate the desired element \(w\) for applying Lemma 2.1. It follows from Lemma 2.1 that \(\mathop{\mathrm{Cay}}(\mathbb{Z}_n, S)\) is \(2\)-e.c. critical when \(n = 8h+6\) with \(h \ge 2\). ◻
Remark 2.8. For \(n = 14\), we have \(h=1\), and Lemma 2.7 gives a \(7\)-regular graph \(\mathop{\mathrm{Cay}}(\mathbb{Z}_{14}, S)\) where \(S=\{\pm 1, \pm 2, \pm4, 7\}\). It is easily verified that \(S \cap (S+7) = \emptyset\), which means that, there is no vertex adjacent to both \(0\) and \(7\) in this Cayley graph. This implies that the graph is not \(2\)-e.c.
The constructions in Lemmas 2.2, 2.4, 2.5, and 2.7 establish the existence of \(2\)-e.c. critical Cayley graphs on \(\mathbb{Z}_n\) for the following cases:
\(n \geq 13\), \(n \equiv 1 \pmod{2}\),
\(n \geq 12\), \(n \equiv 0 \pmod{4}\),
\(n \geq 18\), \(n \equiv 2 \pmod{8}\),
\(n \geq 22\), \(n \equiv 6 \pmod{8}\).
These cover the cases where \(n \ge 12\), with the only (possible) exception \(n = 14\).
For \(n \in \{9, 10, 11, 14\}\), we verified by computers that there does not exist a Cayley graph on the cyclic group \(\mathbb{Z}_n\) that is \(2\)-e.c. critical. The details are as follows:
Order 9: There are two finite groups of order \(9\): the cyclic group \(\mathbb{Z}_9\) and the elementary abelian group \(\mathbb{Z}_3^2\). It is known that the Paley graph on the finite field \(\mathbb{F}_{9}\) is the unique \(2\)-e.c. graph of order \(9\). However, this is a Cayley graph on the group \(\mathbb{Z}_3^2\), not on \(\mathbb{Z}_9\). Moreover, since the Paley graph of order \(9\) is the smallest \(2\)-e.c. graph, it is obviously \(2\)-e.c. critical.
Order 10: There are two finite groups of order \(10\): the cyclic group \(\mathbb{Z}_{10}\) and the dihedral group \(D_{10}\). We verified by computer that there does not exist a \(2\)-e.c. Cayley graph on either \(\mathbb{Z}_{10}\) or \(D_{10}\), regardless of criticality.
Order 11: There is only one finite group of order \(11\), the cyclic group \(\mathbb{Z}_{11}\). We verified by computer that there does not exist a \(2\)-e.c. Cayley graph on \(\mathbb{Z}_{11}\), regardless of criticality.
Order 14: There are two finite groups of order \(14\): the cyclic group \(\mathbb{Z}_{14}\) and the dihedral group \(D_{14}\). For these groups, there are four non-isomorphic \(2\)-e.c. Cayley graphs: two on \(\mathbb{Z}_{14}\), which are complementary to each other, and two on \(D_{14}\), also complementary to each other. However, none of these graphs is \(2\)-e.c. critical. The explicit constructions of two of the graphs, each with valency \(6\), are given in Examples 3.1 and 3.2, respectively.
Example 3.1. Let \(\Gamma := \mathop{\mathrm{Cay}}(\mathbb{Z}_{14}, S)\), where \(S = \{\pm 1, \pm 2, \pm 6\}\). We have \[\begin{aligned} S – S &= \{ 0^{[6]}, 1^{[2]}, 2^{[2]}, 3^{[2]}, 4^{[3]}, 5^{[2]}, 6^{[2]}, 7^{[4]}, 8^{[2]}, 9^{[2]}, 10^{[3]}, 11^{[2]}, 12^{[2]}, 13^{[2]}\}, \\ S – S^\complement &= \{ 1^{[3]}, 2^{[3]}, 3^{[4]}, 4^{[3]}, 5^{[4]}, 6^{[3]}, 7^{[2]}, 8^{[3]}, 9^{[4]}, 10^{[3]}, 11^{[4]}, 12^{[3]}, 13^{[3]}\}, \\ S^\complement – S^\complement &= \{ 0^{[7]}, 1^{[4]}, 2^{[4]}, 3^{[2]}, 4^{[3]}, 5^{[2]}, 6^{[4]}, 7^{[4]}, 8^{[4]}, 9^{[2]}, 10^{[3]}, 11^{[2]}, 12^{[4]}, 13^{[4]}\}, \end{aligned}\] where the numbers in brackets as superscripts indicate the multiplicity of the elements. Notably, there is no element in the above lists with multiplicity one. Then, it follows from Lemma 2.1 that \(\Gamma\) is \(2\)-e.c. but not \(2\)-e.c. critical.
Example 3.2. Let \(\Gamma := \mathop{\mathrm{Cay}}(D_{14}, S)\), where \(D_{14} =\left\langle r , s \mid r^7 = s^2 = (sr)^2 = 1\right\rangle\) is the dihedral group of order \(14\), and \(S = \{ r, r^{-1}, s, sr, sr^3, sr^4\}\). For simplify, we denote \(D_{14} = \{1=r_0, r_1, \ldots, r_6, s=s_0, s_1, \ldots, s_6\}\), where \(r_i = r^i\) and \(s_i= s r^i\) for \(1 \le i \le 6\). We have \[\begin{aligned} S \cdot S^{-1} &= \{ r_0^{[6]}, r_1^{[2]}, r_2^{[2]}, r_3^{[3]}, r_4^{[3]}, r_5^{[2]}, r_6^{[2]}, s_0^{[2]}, s_1^{[2]}, s_2^{[4]}, s_3^{[2]}, s_4^{[2]}, s_5^{[2]}, s_6^{[2]}\}, \\ S \cdot (S^\complement)^{-1} &= \{ r_1^{[3]}, r_2^{[4]}, r_3^{[3]}, r_4^{[3]}, r_5^{[4]}, r_6^{[3]}, s_0^{[3]}, s_1^{[3]}, s_2^{[2]}, s_3^{[3]}, s_4^{[3]}, s_5^{[4]}, s_6^{[4]}\}, \\ S^\complement \cdot (S^\complement)^{-1} &= \{ r_0^{[7]}, r_1^{[4]}, r_2^{[2]}, r_3^{[3]}, r_4^{[3]}, r_5^{[2]}, r_6^{[4]}, s_0^{[4]}, s_1^{[4]}, s_2^{[4]}, s_3^{[4]}, s_4^{[4]}, s_5^{[2]}, s_6^{[2]}\}, \end{aligned}\] where \(X \cdot Y^{-1} = \{ x y^{-1} \mid x \in X, y \in Y \}\) under the group operation in \(D_{14}\), and the numbers in brackets as superscripts indicate the multiplicity of the elements. There is no element in the above lists with multiplicity one. Then, using a generalization of Lemma 2.1 to arbitrary finite groups, which is straightforward to obtain, it follows that \(\Gamma\) is \(2\)-e.c. but not \(2\)-e.c. critical.
Now, we are in a position to provide the proofs of Theorems 1.1 and 1.2.
Proof of Theorem 1.1. Lemmas 2.2, 2.4, 2.5, and 2.7 show that a \(2\)-e.c. critical Cayley graph on \(\mathbb{Z}_n\) exists for all positive integers \(n \ge 12\) with \(n \neq 14\). Combining this with the non-existence results for \(n \le 8\) (where no \(2\)-e.c. graph of order \(n\) exists) and for \(n \in \{9, 10, 11, 14\}\) confirmed by computer verification, we conclude that a \(2\)-e.c. critical Cayley graph on the cyclic group of order \(n\) exists if and only if \(n \ge 12\) and \(n \neq 14\). ◻
Proof of Theorem 1.2. The only difference from Theorem 1.1 lies in the case \(n = 9\). For \(n = 9\), although a \(2\)-e.c. critical Cayley graph on \(\mathbb{Z}_9\) does not exist, the Paley graph of order \(9\) provides an example (and the unique one) of a \(2\)-e.c. critical Cayley graph on \(\mathbb{Z}_3^2\). ◻
Remark 3.3. It would be interesting to explore constructions on other finite groups, such as non-cyclic abelian groups and non-abelian groups including the dihedral groups. Notably, for order \(9\) the only \(2\)-e.c. Cayley graph is non-cyclic, while for order \(14\), cyclic and dihedral groups yield non-isomorphic \(2\)-e.c. critical graphs. This suggests the natural question of whether for every finite group of order \(n \ge 12\) with \(n \ne 14\) there exists a \(2\)-e.c. critical Cayley graph.
Remark 3.4. Supporting code using SageMath [21] for reproducing the non-existence results and for generating Examples 3.1 and 3.2 is available at the following GitHub repository:
https://github.com/xnlu-math/2ec-critical-cayley-graph-checker
To conclude the paper, we examine the case of \(2\)-e.c. critical vertex-transitive graphs that are not Cayley graphs.
It was shown by Marušič [16] that all vertex-transitive graphs of order \(p^k\) are Cayley graphs for any prime \(p\) and \(k \in \{1, 2, 3\}\). Additionally, Alspach and Sutcliffe [1] proved that a vertex-transitive, non-Cayley graph of order \(2p\) with \(p\) prime exists if and only if \(p \equiv 1 \pmod 4\). (See also [17] for the characterization of non-Cayley vertex-transitive graphs whose orders are the product of two distinct primes.) Hence, there do not exist non-Cayley vertex-transitive graphs of order \(9\), \(11\), or \(14\).
| Order | Total Number | Connected | $$2$$-e.c. | $$2$$-e.c. critical |
| 10 | 22 | 18 | 0 | 0 |
| 11 | 8 | 7 | 0 | 0 |
| 12 | 74 | 64 | 2 | 2 |
| 13 | 14 | 13 | 2 | 1 |
| 14 | 56 | 51 | 4 | 0 |
| 15 | 48 | 44 | 14 | 14 |
| 16 | 286 | 272 | 58 | 20 |
| 17 | 36 | 35 | 10 | 5 |
| 18 | 380 | 365 | 86 | 28 |
| 19 | 60 | 59 | 22 | 14 |
| 20 | 1214 | 1190 | 362 | 104 |
| 21 | 240 | 235 | 120 | 58 |
| 22 | 816 | 807 | 282 | 42 |
| 23 | 188 | 187 | 92 | 40 |
| 24 | 15506 | 15422 | 7570 | 1118 |
| 25 | 464 | 461 | 248 | 79 |
| 26 | 4236 | 4221 | 2072 | 216 |
| 27 | 1434 | 1425 | 934 | 258 |
| 28 | 25850 | 25792 | 14374 | 1204 |
| 29 | 1182 | 1181 | 756 | 182 |
| 30 | 46308 | 46236 | 28548 | 2186 |
| 31 | 2192 | 2191 | 1496 | 306 |
| 32 | 677402 | 677116 | 484264 | 33452 |
| 33 | 6768 | 6759 | 4904 | 844 |
| 34 | 132580 | 132543 | 93856 | 3796 |
| 35 | 11150 | 11144 | 8386 | 1224 |
Furthermore, we verified all the graphs of the orders mentioned below in the database of vertex-transitive graphs maintained by Royle and Holt [19]. The numbers of vertex-transitive graphs, connected vertex-transitive graphs, \(2\)-e.c. vertex-transitive graphs, and \(2\)-e.c. critical vertex-transitive graphs for \(10 \le n \le 35\) are summarized in Table 16.
For some small orders, a detailed investigation has also been conducted. Interesting observations related to the proposed constructions are highlighted and presented as follows:
There are only two non-Cayley vertex-transitive graphs of order \(10\): the Petersen graph and its complement. However, neither of them is \(2\)-e.c.
There are only two \(2\)-e.c. Cayley graphs of order \(12\): one is the 6-regular Cayley graph constructed in Lemma 2.4, and the other is its complement. Both of them are \(2\)-e.c. critical.
The \(6\)-regular Cayley graph of order \(13\) obtained from Lemma 2.2 is the unique \(2\)-e.c. critical Cayley graph of that order up to isomorphism. There is another \(2\)-e.c. Cayley graph of order \(13\) and valency \(6\), isomorphic to \(\mathop{\mathrm{Cay}}(\mathbb{Z}_{13}, \{ \pm 1, \pm 3, \pm 4\})\), but it is not \(2\)-e.c. critical.
Combining the above facts with Theorem 1.2, we have the following:
Theorem 4.1. A \(2\)-e.c. critical vertex-transitive graph of order \(n\) exists if and only if \(n \ge 9\) and \(n \notin \{10, 11, 14\}\).
Finally, we report some observations on \(3\)-e.c. vertex-transitive graphs.
There does not exist any \(3\)-e.c. vertex-transitive graph of order less than or equal to \(27\).
The smallest \(3\)-e.c. vertex-transitive graph has order \(28\). There are only two \(3\)-e.c. vertex-transitive graphs of order \(28\)1, both of which are Cayley graphs on the dihedral group \(D_{28}\) and are complementary to each other. Both of them are \(3\)-e.c. critical.
The Paley graph of order \(29\) is the unique \(3\)-e.c. vertex-transitive graph of that order, and it is also the smallest order for a \(3\)-e.c. Paley graph. However, removing any vertex from this graph still results in a \(3\)-e.c. graph, meaning it is not \(3\)-e.c. critical.
There are only two \(3\)-e.c. vertex-transitive graphs of order \(30\), both of which are Cayley graphs on \(\mathbb{Z}_5 \times \mathfrak{S}_3\), the direct product of the cyclic group \(\mathbb{Z}_5\) and the symmetric group \(\mathfrak{S}_3\), and are complementary to each other. Both of them are \(3\)-e.c. critical.
Providing an explicit construction for \(3\)-e.c. critical vertex-transitive graphs (even for Cayley graphs) remains a challenging problem. However, there are a few explicit constructions for \(3\)-e.c. graphs (e.g., [2, 8, 14, 22]), most of which involve combinatorial designs or finite fields as a source. Investigating these constructions presents a potential direction for future research.
The author would like to thank the referees for their valuable comments and suggestions. This research was partly supported by JSPS KAKENHI Grant Number 22K13949.