WorksMathematics
Asymptotical results on the automorphism groups of canonical double cover of graphs
Abstract
The canonical double cover of a graph is the direct product . A graph is stable if every automorphism of is induced by automorphisms of and , and unstable otherwise. We prove several asymptotic results on stable and unstable graphs. In particular, we show that the automorphism group of the canonical double cover of almost every graph has order , and consequently that almost all graphs are stable. We also prove that the dominant sources of instability are having twins and being disconnected, in that order, and that graphs arising from a known construction are the next step in this hierarchy.
Keywords: canonical double cover, unstable graph, automorphism group
AMS Subject Classification (2020): 05C25, 05C76
Introduction
All graphs in this paper are finite and simple. Given a graph , its automorphism group is denoted by . The canonical bipartite double cover (also called the bipartite double cover or the Kronecker cover) of , denoted by , is the direct product (where denotes the complete graph on two vertices). In other words, we have that
and
We denote by the canonical involution on interchanging and for all . We observe that and that canonically embeds into . The graph is stable if has no additional automorphism, that is, if
Otherwise, is called unstable.
Canonical double covers have proven to play an important role in algebraic graph theory and have been studied from a variety of perspectives. For example, their connections with symmetric -matrices were studied by Marušić, Scapellato and Salvi [11], their regular embeddings by Nedela and Škoviera [12], their isomorphisms by Pacco and Scapellato [13] and their symmetry properties in the context of 2-fold covers by Feng, Kutnar, Malnič and Marušič [2].
Wilson gave several sufficient conditions for a graph to be unstable, which he then used to formulate conjectures characterising instability in four families of graphs: circulants, Rose Window graphs, toroidal graphs and generalized Petersen graphs [16]. Wilson’s conjectures were proven for generalized Petersen graphs by Qin, Xia, and Zhou [15], for toroidal graphs by Witte Morris [18], and for Rose Window graphs by Ahanjideh, Kovács, and Kutnar [1].
A lot of work has been done on the stability of circulant graphs. Wilson’s conjecture was shown to be false by Qin, Xia and Zhou, who also proved that there are no nontrivially unstable arc-transitive circulants [14]. It was proven by Fernandez and the second author that there are no nontrivially unstable circulants of odd order [3]. Morris extended this result by proving that there are no nontrivially unstable Cayley graphs on abelian groups of odd order [17]. In [9], several constructions of unstable circulants were presented, and unstable circulants of order twice a prime were classified, whereas in [10] unstable circulants with valency at most 7 were classified. The connection between stability of Cayley graphs and properties of Schur rings was studied in [7]. Nevertheless, the full classification of unstable circulants remains an open problem. In [19], Xia, Zhang and Zheng proved that almost all Cayley graphs on abelian groups are stable.
In this paper, we study the asymptotic behavior of the proportion of various properties related to stability of general graphs. Throughout the paper all asymptotic statements concern labeled graphs; in particular, when we say that almost all graphs in a family have a given property, we mean that the proportion of graphs with that property among all graphs in the family with vertex-set tends to 1 as . For a precise definition, see Definition 3.1.
We first show that instability is asymptotically rare. In fact, we prove the following stronger statement.
Theorem 1.1. Almost all graphs satisfy .
As a direct consequence, we have the following:
Corollary 1.2. Almost all graphs are stable.
It is not hard to see that graphs with twins (nonadjacent distinct vertices with the same neighbourhoods) and disconnected graphs are unstable. We will prove that these are the dominant sources of instability, in that order.
Theorem 1.3. Almost all unstable graphs have twins.
Theorem 1.4. Almost all unstable twin-free graphs are disconnected.
Moving further down the asymptotic hierarchy, we consider twin-free connected unstable graphs and show that they almost all arise from the following simple construction, which was first defined in [8].
Construction 1.5. Let be a graph and let and be subsets of . Let be the graph obtained from by adding four new vertices and two new edges to , and then joining and with every vertex in and and with every vertex in .
Theorem 1.6. Almost all unstable twin-free connected graphs arise via Construction 1.5.
Finally, we determine the typical automorphism group of the canonical double cover of the graphs in Theorem 1.6. Let denote the dihedral group of order 8.
Theorem 1.7. Almost all unstable twin-free connected graphs that arise via Construction 1.5 satisfy
for some distinct vertices of .
Some authors (for example Wilson in [16]) define a graph to be nontrivially unstable if it is unstable but twin-free, connected and nonbipartite. Note that nonbipartite is slightly different from the other two conditions in this definition: graphs with twins and disconnected graphs are necessarily unstable, whereas a bipartite graph may still be stable. Moreover, we have already noted that, asymptotically speaking, graphs with twins and disconnected graphs are the dominant sources of instability. Being bipartite is much further down the list, see for example Lemma 3.2. It is also lower than graphs arising from Construction 1.5. For this reason, Theorem 1.6 and Theorem 1.7 immediately hold with “unstable twin-free connected” replaced by “nontrivially unstable”.
We first prove some important preliminary results in Section 2 and then the main theorems in Section 3.
Preliminaries
Let be a graph with vertex-set . For , the neighbourhood of in is the set of vertices of adjacent with . Note that
Let . We denote by the permutation of defined by
Given a group , the support of , denoted , is the set of elements of not fixed by .
Lemma 2.1. Let be a graph with vertex-set , let and let such that . Let , and . Then
(1) and .
(2) .
(3) and are nonadjacent in .
If moreover is twin-free, then
(4) If one of or is the identity, they both are.
(5) and have the same order.
(6) If , then .
Proof. (1) We have
It follows that , and an analogous argument yields .
(2) From (1), we get
A symmetrical argument yields that and thus $N_X(v^g) \cap W = N_X(v) \cap W.
(3) Note that and are nonadjacent in . Consequently, since , we have that
and
are also nonadjacent in . It follows that and are nonadjacent in , as desired.
(4) Without loss of generality, suppose that . Applying (1), we get . Since is twin-free, we have that and, since is arbitrary, we have , as required.
(5) Assume for contradiction that . Without loss of generality, we may assume that does not divide and thus , and
contradicting (4).
(6) Suppose for a contradiction that . By (5), and have the same order. Since , either and are distinct transpositions or is a 3-cycle and . In both cases, is a cycle of length 3 on . By (3), it follows that the three vertices contained in are nonadjacent in . Let such that , in particular, . By (2), we have and thus and are twins in , contradicting the assumption that is twin-free.
Lemma 2.2. A connected nonbipartite graph with vertex-set is unstable if and only if there exist , with , such that .
Proof. Since is connected and nonbipartite, it follows by Weichsel’s Theorem (see [6 Theorem 5.9]) that is connected hence is the unique bipartition of and thus every automorphism of preserves it.
Suppose that is unstable. Then . By the previous paragraph, there exist with and not of the form with . If , then Lemma 2.1(1) implies that , a contradiction, so we have , as required. The converse is obvious. □
Lemma 2.3. Let , let and let . Then the orbits of are exactly the sets of the form with an orbit of .
Proof. Since , an orbit of contains if and only if it contains . Using this and the fact that , the conclusion easily follows.
Corollary 2.4. Let be a twin-free graph with vertex-set and let such that and . Let and let be the subgraph of induced on . If , then there exist subsets such that .
Proof. Since , either has two orbits of size or one orbit of size .
Case 1. has an orbit of size .
Let be this orbit, so . Let be the subgraph of induced on . Then is a subgraph of and, by Lemma 2.3, acts transitively on . In particular, both and are regular graphs.
Let and let . By Lemma 2.1(2), does not depend on the choice of . In particular, since is twin-free, so is . Since , and , it follows that is unstable. The only regular twin-free graphs on four vertices are and , but is stable hence . Hence , as required.
Case 2. has two orbits of size .
Let and be distinct orbits of size of , so . By Lemma 2.1(5), and have the same order. Since , up to relabeling, we have that either
or
Subcase 2.1. and .
Let . Since , Lemma 2.1(3) implies that is nonadjacent to in and is nonadjacent to in . By Lemma 2.1(2), we have
and
Since is twin-free, and are not twins, so they are each adjacent to exactly one of or , and vice versa. Without loss of generality, let be adjacent to and nonadjacent to and be adjacent to and nonadjacent to . It now follows that , as required.
Subcase 2.2. and . Let and note that . By Lemma 2.1(1) applied with , we have
and
Let and . We now have
and
Since , it follows that , contradicting the fact that is twin-free. □
Finally, we recall some basic properties of Construction 1.5.
Proposition 2.5 ([8 Proposition 5.2]). Let be a graph with vertex-set and let . Then
,
is an automorphism of the double cover of ,
we have .
In particular, is unstable. Moreover, if is connected and twin-free, and at least one of and is nonempty, then is also connected and twin-free.
Proof. The fact that follows immediately from Construction 1.5 (and, in particular, Figure 1). By [8 Proposition 5.2], is an automorphism of the double cover of . Both and are involutions, while their product has order 4, hence, , as required. The last part is immediate. □
Figure 1. .
For fixed , we give upper bounds on the number of graphs with vertex-set such that .
Lemma 2.6. Let be a positive integer, let be a set of order , let and let . Let be the set of graphs with vertex-set such that . Let be the size of the support of and let the nontrivial orbits of have sizes . Then
.
If is an even integer with , then
Proof. Let be the nontrivial orbits of , with for all . Then
Let and let . By Lemma 2.3, is an orbit of . It follows that uniquely determines for every , which in turn uniquely determines for every .
There are at most possibilities for the set . By the previous paragraph, this choice then determines for every . It follows that is also determined, which leaves at most possibilities for , which in turn determines for every . We repeat this procedure for all obtaining that there are at most possibilities for , hence determining for every . It remains to determine the adjacencies amongst the vertices of fixed by , that is, those not contained in . There are such vertices, so at most possibilities, which concludes the proof of (1).
We now prove (2). Write . We call the vertices of other than non-representative. We order the vertices in the following way: first , then non-representative vertices in , then , then non-representative vertices in , etc., with fixed vertices at the end. We choose the neighbourhood of the vertices in order. In the usual count of the total number of labeled graphs
the vertex in the -th position contributes . In this case, the adjacency of a non-representative vertex is already determined, as in the proof of (1). Therefore, if the vertex in the -th position is non-representative, then we lose a factor of compared to the usual count.
Since , the -th non-representative vertex has position at most . Therefore, the factor lost because of the -th non-representative vertex is at least
There are non-representative vertices. Since , we have and therefore
Hence there are at least non-representative vertices. Consequently, the total loss compared from is at least
as required. □
Lemma 2.7. Let be a positive integer and let be a set of order . The number of graphs with vertex-set for which there exist such that and is .
Proof. Let and be as in the statement, and let . We consider two cases.
Case 1. . The number of pairs in this case is at most
The support of is either a single orbit of size 5, or a union of two orbits of sizes 3 and 2. For each fixed pair , Lemma 2.6(1) gives at most
graphs when has an orbit of size 5, and at most
when has an orbit of size 3 and one of size 2. The total contribution of this case is thus at most
Case 2. . Let . Note that is a positive even integer.
Subcase 2.1. . The number of pairs in this case is at most
For each fixed pair , Lemma 2.6(2) applied with gives at most
graphs satisfying . The total contribution of this case is thus at most
Subcase 2.2. . The number of pairs in this case is at most
For each fixed pair , Lemma 2.6(2) applied with gives at most
graphs satisfying . The total contribution of this case is thus at most
Dividing by gives
Since , the above exponent tends to when . Therefore this ratio is
which completes the proof. □
Lemma 2.8. The number of graphs with vertex-set admitting two distinct double transpositions as automorphisms is at most
Proof. Note that contains double transpositions, so there are at most choices for a pair of distinct double transpositions. We estimate the number of graphs with vertex-set having and as automorphisms. Let , and . Clearly, .
Each of and is a product of two disjoint transpositions. Since and are distinct, these gives us at least 3 distinct transpositions and it follows that has at most orbits on .
There are choices for the edges within , and at most choices for the edges within . Finally, if and , then is adjacent to if and only if it is adjacent to every element of the -orbit of . It follows that there are at most choices for the edges between and , and thus choices for edges between and . This gives us an upper bound of
possible graphs. □
Main results
Definition 3.1. Let and be families of graphs and let be the family of all graphs with vertex-set . We say that “almost all graphs in are in ” if
If the above holds with , then we say that “almost all graphs are in ”.
Recall that if
Lemma 3.2. Let be a positive integer. Then
The number of disconnected graphs with vertex-set is . In particular, almost all graphs are connected.
The number of bipartite graphs with vertex-set is at most . In particular, almost all graphs are nonbipartite.
The number of graphs with vertex-set with twins is . In particular, almost all graphs are twin-free.
Proof.
(1): See for example [4 Example II.15, p.138].
(2): To count the bipartite graphs with vertex-set , we consider all possible bipartitions of and then all possible edge sets for each of those bipartitions. Let and form a partition of with . Writing , there are choices for and possible edges between and . Hence the following is an upper bound on the number of bipartite graphs with vertex-set :
(3): Let denote the set of graphs with vertex-set having twin vertices, and, for distinct , let denote the set of graphs with vertex-set in which and are twins. Clearly,
By the first two Bonferroni inequalities (that is, the first two truncations of the inclusion–exclusion formula), we obtain
Let be distinct. A graph with vertex-set in which and are twins is uniquely determined by its subgraph induced on . Hence,
and
There are at most choices for and, depending on whether or not, we either get a set of three distinct twins, or two disjoint sets of disjoint twins. Either way, we get exactly two “redundant” vertices, that is vertices whose neighbourhood is determined by their twins. It follows that, for fixed , we have
This implies that
but
Together with (1) and (2), this yields
as desired.
Theorem 1.1. Almost all graphs satisfy .
Proof. Combining Lemma 3.2(1) and Lemma 3.2(2), we conclude that almost all graphs are connected and nonbipartite. Hence, without loss of generality, we may assume that is connected and nonbipartite. As noted earlier, this implies that is connected and thus is the unique bipartition of . It follows that, if , then there exist such that . Let . Note that .
We will give an upper bound on the number of graphs with vertex-set such that . We closely follow the ideas of the proof of [5 Lemma 2.3.2]. Let . Note that is a positive even integer.
Case 1. . The number of pairs in this case is at most
For each fixed pair , Lemma 2.6(2) applied with gives at most
graphs satisfying . The total contribution of this case is thus at most
Case 2. . The number of pairs in this case is at most
For each fixed pair , Lemma 2.6(2) applied with gives at most
graphs satisfying . The total contribution of this case is thus again at most
which concludes the proof. □
We now give an upper bound on the number of unstable twin-free connected graphs which will be used in the proofs of Theorems 1.3 and 1.4.
Lemma 3.3. The number of unstable twin-free connected graphs with vertex-set is .
Proof. Using Lemma 3.2(2) it is not difficult to see that the number of bipartite graphs is . It therefore suffices to count unstable twin-free connected nonbipartite graphs. For each such graph , by Lemma 2.2 there exist with and . Let . By Lemma 2.1(6), we have . There are at most pairs with . For each fixed pair, Lemma 2.6(2), applied with , gives at most graphs. Thus their total number is at most
By Lemma 2.7, the number of graphs admitting such a pair with is
The result follows. □
:::
Theorem 1.3. Almost all unstable graphs have twins.
Proof. Let denote the set of unstable graphs with vertex-set , and let denote the set of graphs on containing a pair of twins. Note that . By Lemma 3.2(3), we have that
We now estimate , that is the number of unstable twin-free graphs. First, by Lemma 3.2(1), the number of disconnected graphs on is
Comparing to (3), we see this is . It remains to count unstable twin-free connected graphs. By Lemma 3.3, their number is
Combining the estimates, we obtain
and the result follows. □
Corollary 3.4. The number of unstable graphs with vertex set is .
Proof. This follows directly from Theorem 1.3, Lemma 3.2[3] and the fact that every graph admitting twins is unstable. □
Theorem 1.4. Almost all unstable twin-free graphs are disconnected.
Proof. Let denote the set of unstable twin-free graphs with vertex-set and let denote the set of (unstable) twin-free disconnected graphs with vertex-set . Clearly, . Observe that starting with a twin-free connected graph with vertex-set and adding an isolated vertex labelled , we obtain a graph belonging to . By Lemma 3.2, it follows that . On the other hand, observe that consists of unstable twin-free connected graphs. By Lemma 3.3 it follows that , concluding the proof. □
Definition 3.5. We say that a graph arises via Construction 1.5 if there exist distinct and such that , where is the subgraph of induced on .
In the context of Definition 3.5, we will allow the vertices of to have other labels, such as elements of .
Let be the set of graphs with vertex-set that arise via Construction 1.5. Let denote the set of unstable twin-free connected graphs with vertex-set .
Proposition 3.6. We have .
Proof. Choose a connected twin-free graph with vertex-set . By Lemma 3.2, there are
choices for . Now, choose , not both empty. There are
choices for and . By Proposition 2.5, is an unstable twin-free connected graph. Let be the graph obtained from by relabelling with , respectively. Clearly, . Moreover, can be recovered from in the following way: is the subgraph of induced by , and . It follows that distinct yield distinct s and, in particular,
as required.
Theorem 1.6. Almost all unstable twin-free connected graphs arise via Construction 1.5.
Proof. We need to show
By Proposition 3.6, it suffices to show that
Let . By Lemma 3.2(2), the number of bipartite graphs is negligible, so we can assume that is nonbipartite. By Lemma 2.2, there exist such that and . Let . By Lemma 2.1(6), it follows that . If , then by Corollary 2.4 we have , which is a contradiction. Hence, and the result follows from Lemma 2.7. □
Theorem 1.7. Almost all unstable twin-free connected graphs that arise via Construction 1.5 satisfy
for some distinct vertices of .
Proof. Let and let . By definition, there exist distinct and such that , where is the subgraph of induced on . Let
Note that and have disjoint support and hence commute. It is clear that
By Proposition 2.5, we have that
and that
Note that the kernel of the action of on the canonical bipartition of is
Recall that, from Proposition 3.6, we have that
In order to establish the claim, it suffices to show that the subset , consisting of graphs for which , is a negligible subset of . In particular, we prove that
Fix . By Lemma 3.2(2), the number of bipartite graphs is negligible, so we can assume that is nonbipartite. Since is connected and nonbipartite, the assumption implies that there exist with such that
Let . By Lemma 2.1(6), we have that . If , then by Lemma 2.7, the number of possibilities for is at most
We may thus assume that . We now consider the cases which occur in the proof of Corollary 2.4. In Case 1, there exists such that and it follows that admits three distinct double transpositions (with support ). In Subcase 2.1, contains the double transposition and if , then , contrary to the choice of . Finally, Subcase 2.2 does not occur. Thus, in both cases that do occur, admits two distinct double transpositions. By Lemma 2.8, the number of such is at most
Hence, we obtain that
as desired.
Acknowledment
The authors would like to thank to Rajko Nenadov for several helpful discussions regarding this problem. Ademir Hujdurović gratefully acknowledges the hospitality of the University of Auckland and the award of a Kalman Visiting Scholarship in 2024, during which the research leading to this paper was initiated, as well as financial support from the Slovenian Research and Innovation Agency through research program P1-0404 and research projects N1-0481, N1-0428, N1-0459, J1-70035, J1-70046, J1-70047, and J1-60012.
Declaration of AI use
AI was only used for minor polishing of the text.
References
Faculty of Mathematics and Computer Science, Jagiellonian University, Krakow, Poland and Faculty of Mathematics, University of Cambridge, UK Email address: [email protected]
University of Primorska, Faculty of Mathematics, Natural Sciences and Information Technologies, Glagoljaška 8, 6000 Koper, Slovenia Email address: [email protected]
Department of Mathematics, University of Auckland, Private Bag 92019, Auckland 1142, New Zealand Email address: [email protected]
Department of Mathematics, University of Auckland, Private Bag 92019, Auckland 1142, New Zealand Email address: [email protected]
References
- [1]Milad Ahanjideh, István Kovács, and Klavdija Kutnar. Stability of Rose Window graphs. J. Graph Theory, 107(4):810–832, 2024.arxiv.org/abs/2306.01619
- [2]Yan-Quan Feng, Klavdija Kutnar, Aleksander Malnič, and Dragan Marušič. On 2-fold covers of graphs. Journal of Combinatorial Theory, Series B, 98(2):324–341, 2008.arxiv.org/abs/math/0701722
- [3]Blas Fernandez and Ademir Hujdurović. Canonical double covers of circulants. Journal of Combinatorial Theory, Series B, 154:49–59, 2022.DOI
- [4]Philippe Flajolet and Robert Sedgewick. Analytic combinatorics. cambridge University press, 2009.
- [5]Chris Godsil and Gordon Royle. Algebraic Graph Theory, volume 207 of Graduate Texts in Mathematics. Springer-Verlag, New York, 2001.DOI
- [6]Richard H Hammack, Wilfried Imrich, and Sandi Klavžar. Handbook of product graphs, volume 2. CRC press Boca Raton, 2011.DOI
- [7]Ademir Hujdurović and István Kovács. Stability of Cayley graphs and Schur rings. Electron. J. Combin., 32(2):Paper No. 2.49, 23, 2025.DOI
- [8]Ademir Hujdurović and Đorđe Mitrović. Some conditions implying stability of graphs. Journal of Graph Theory, 105(1):98–109, 2024.arxiv.org/abs/2210.15249
- [9]Ademir Hujdurović, Djordje Mitrović, and Dave Witte Morris. On automorphisms of the double cover of a circulant graph. The Electronic Journal of Combinatorics, 28(4)(P4.43), 2021.
- [10]Ademir Hujdurović, Djordje Mitrović, and Dave Witte Morris. Automorphisms of the double cover of a circulant graph of valency at most 7. Algebr. Comb., 6(5):1235–1271, 2023.
- [11]Dragan Marušič, Raffaele Scapellato, and N Zagaglia Salvi. A characterization of particular symmetric (0, 1) matrices. Linear Algebra and its Applications, 119:153–162, 1989.
- [12]Roman Nedela and Martin Škoviera. Regular embeddings of canonical double coverings of graphs. Journal of Combinatorial Theory, Series B, 67(2):249–277, 1996.
- [13]Walter Pacco and Raffaele Scapellato. Digraphs having the same canonical double covering. Discrete Math., 173(1-3):291–296, 1997.
- [14]Yan-Li Qin, Binzhou Xia, and Sanming Zhou. Stability of circulant graphs. J. Combin. Theory Ser. B, 136:154–169, 2019.arxiv.org/abs/1802.04921
- [15]Yan-Li Qin, Binzhou Xia, and Sanming Zhou. Canonical double covers of generalized Petersen graphs, and double generalized Petersen graphs. J. Graph Theory, 97(1):70–81, 2021.DOI
- [16]Steve Wilson. Unexpected symmetries in unstable graphs. Journal of Combinatorial Theory, Series B, 98(2):359–383, 2008.DOI
- [17]Dave Witte Morris. On automorphisms of direct products of cayley graphs on abelian groups. The Electronic Journal of Combinatorics, page P3.5, 2021.
- [18]Dave Witte Morris. Automorphisms of the canonical double cover of a toroidal grid. Art Discrete Appl. Math., 6(3):Paper No. 3.07, 25, 2023.
- [19]Binzhou Xia, Zhishuo Zhang, and Shasha Zheng. Asymptotic stability of cayley graphs on abelian groups. arXiv:2601.20214, 2026.
