The majority of graphs are well-known to be asymmetric, i.e., having no non-trivial automorphisms. Moreover, removing just a single vertex from a vertex transitive graph may result in a graph with a trivial automorphism group; while removing a vertex from a graph belonging to the family of minimal asymmetric graphs (introduced by Nešetřil) always leads to a graph with a non-trivial automorphism group. Moreover, every two-vertex induced subgraph of any given graph Γ possesses a non-trivial automorphism. These observations call for the use of the concept of a partial (graph) automorphism which is an isomorphism between two induced subgraphs of a given graph. The set of all partial automorphisms together with the operation of partial composition forms an inverse monoid. Based on the study of inverse monoids of partial automorphisms, we propose to use a graph parameter we call the symmetry level of a graph, defined to be the ratio between the maximal rank of a nontrivial partial automorphism and the order of the graph, as a measure of the graph's asymmetricity. In our paper, we present some basic observations concerning the symmetry levels of graphs, and present some computational results concerning the symmetry levels of small asymmetric graphs.
induced subgraphs symmetric. Specifically, he proposed the concept of a minimal asymmetric graph which is a While the order of the automorphism group of a finite graph with no induced asymmetric subgraphs of order graph is considered to be one of the more important pa- at least 2. He conjectured the existence of only a finite rameters of a given graph Γ , in view of the well-known number of such graphs, and was proven to be right by 1963 result of Erdős and Rényi [1] asserting that almost Schweitzer and Schweitzer in 2017 who have shown that all graphs are asymmetric, i.e., having no non-trivial au- the complete list of such graphs consists of exactly 18 tomorphisms, this parameter turns out to be generally graphs [7]. rather irrelevant. This fact has already been acknowl- In our paper, we propose to study a diferent measure edged in [1], where the authors proposed to study the of asymmetricity of a graph Γ from both of the above. symmetrization of a graph Γ achieved via removing Based on our research in the inverse monoids of parand adding edges, and thereby producing a graph pos- tial automorphisms of graphs, we realized that inverse sessing at least one non-trivial automorphism. The de- monoids are better suited for investigation of asymmetric gree of asymmetry, (Γ) , is then defined to be the min- graphs, as the inverse monoid of partial automorphisms imum of the sum + taken over all possible sym- of a graph Γ determines Γ uniquely [3] (regardless of metrizations of Γ . They also noted that the asymmetry whether Γ is asymmetric or not). A partial automorphism of a graph of order can not exceed −2 1 , and showed of a graph Γ = ( , ) is an isomorphism between two inthat this estimate is asymptotically best possible, which duced subgraphs of Γ (with an automorphism of Γ being led them to the concept of the relative asymmetry of Γ , a partial automorphism from Γ onto itself). The set of all gr(aΓ)ph=s, and(−2Γ1)(.Γ) =Cle0arlfyo,r0gr≤aphs(pΓ)oss≤ ess1in, gfoart laelalsfint iotene opfarptaiarltiaaultcoommopropshitisiomnsfoofrmΓ taongeinthveerrswe imthotnhoeidopweerasthioanll non-trivial automorphism. denote (Γ) . The order of an inverse monoid is its
In 1988, Nešetřil proposed a diferent approach to cardinality, and the rank of a partial automorphism is the studying the asymmetry level of finite graphs by sug- size of its domain. Any Γ of order at least 2 possesses at gesting to study the order of asymmetric graphs with all least one non-trivial (non-identity) partial automorphism of rank 2, namely a partial automorphism mapping a pair of adjacent vertices to any other such pair (in case ITAT’23: Computational Aspects of Large-Scale Problems in Discrete of the complement of , one can take pairs of nonM$acthinegmeal1ti3c@s, uSenpibteam.sbke(rV2.2C–i2n6g, e2l0);23g,aTl3a9t@ranusnkiébaM.saktl(iMar.e,GSállo)v;akia adjacent vertices, and in a graph containing exactly one jajcayova@fmph.uniba.sk (T. B. Jajcayová) edge, one can take the partial automorphism swapping its © 2023 Copyright for this paper by its authors. Use permitted under Creative Commons License end-points). On the other hand, the largest rank of a nonCPWrEooUrckReshdoinpgs IhStpN:/c1e6u1r3-w-0s.o7r3g ACttEribUutRion W4.0oInrtekrnsahtioonpal (PCCroBYce4.0e).dings (CEUR-WS.org) trivial partial automorphism of a non-asymmetric Γ is of symmetry of Γ containing no edges is equal to 1. If the order of Γ , while the largest rank of a non-trivial par- Γ contains a connected component consisting of a single tial automorphism of a minimal asymmetric Γ of order edge or two isolated vertices , , it admits a non-trivial is − 1. Since it is not hard to see that the largest rank of automorphism swapping and and leaving all other a non-trivial partial automorphism of a graph Γ is related vertices fixed, hence, (Γ) = 1 again. If Γ contains a to the order of Γ , the measure of asymmetry of a graph Γ component of order 3, it is necessarily a path , , and we propose to study is defined as the ratio between the Γ admits a non-trivial automorphism swapping and largest rank of a non-trivial partial automorphism of a and leaving all other vertices fixed; (Γ) = 1 . Finally, graph Γ and its order | (Γ) |. As this ratio is equal to 1 suppose that Γ contains a component (a tree) of order if and only if Γ admits a non-trivial automorphism, we ≥ 4. Then either contains two leaves , attached to the will call this ratio the level of symmetry of Γ , denote it same , or it contains a path , , of length 3 in which by (Γ) , and note that (Γ) < 1 for almost all graphs is of degree 2 and is of degree 1 (a leaf). In either case, Γ [1]. We find it important to emphasize, that the level Γ admits a non-trivial partial automorphism of rank − 1 of symmetry of Γ might be greater than the order of a swapping and and fixing all the other vertices of Γ but smallest non-asymmetric induced subgraph of Γ ; which the vertex , which is left out of the domain of this partial may happen if Γ contains two distinct but isomorphic automorphism. Therefore, (Γ) ≥ − 1 . induced asymmetric subgraphs of orders larger than the order of a smallest non-asymmetric induced subgraph of Γ .
constructing partial automorphisms by ‘ignoring’ neigh
sic results concerning the level of symmetry of graphs in general, we present some computational results concerning graphs of orders for which the complete lists of non-isomorphic graphs have already been determined. Lemma 3. Let Γ be a graph of order , and let and be two vertices of Γ of degrees , sharing common neighbors. Then there exists a non-trivial partial automorphism of Γ of rank at least − − + . In addition, if and are adjacent in Γ , there exists a partial automorphism of Γ of rank at least − − + + 2.
monoid of partial automorphisms of a graph Γ , and the level of symmetry of Γ are relatively new, in this section, we present some basic facts.
Lemma 1. Let Γ be a graph, and let Γ˜ denote its complement. A partial permutation of the vertices of Γ is a partial automorphism of Γ if and only if, it is a partial automorphism of Γ˜, and thus (Γ) = (Γ˜), and (Γ) = (Γ˜).
Proof 1. The claim follows from the well-known fact that (Γ) = (Γ˜) and the observation that a subgraph of Γ induced by a subset ⊆ (Γ) is the complement of the subgraph of Γ˜ induced by .
Lemma 2. Let Γ be a forest of order . Then, (Γ) ≥ − 1 .
Proof 2. We proceed by considering all possible orders of connected components of Γ . As observed above, the level Proof 3. The domain of the desired partial automorphism is the set of vertices of Γ minus the neighbors of and that fixes all the vertices in its domain and swaps and . The rank (i.e., the cardinality of its domain) of such partial automorphism can be easily seen to be equal to the values stated in the statement of the lemma.
Corollary 1. Let Γ be a graph of order , and let be the maximum of the values − − + or − − + + 2, if and are adjacent, over all pairs of distinct vertices , ∈ (Γ) . Then (Γ) ≥ − . In particular, if and are vertices of minimum degrees , among all vertices of Γ , (Γ) ≥ − − .
The above corollary yields a relatively high level of symmetry for all graphs containing two vertices of small degree. Even though this may seem like a rather strong requirement, two vertices of high degree are likely to share some common neighbors, and moreover, Lemma 1 allows us to extend the result to the opposite case of graphs in which all the vertices have high degrees. The interesting cases lie therefore among the graphs in which the majority of vertices are of degree roughly 2 ; with being the order of the graph. However, instead of proceeding further and improving the above lower bounds, we choose to state a series of open questions inspired by our results on possible levels of symmetry which will be addressed in the last section of our paper where we present computational evidence toward answering the questions listed here.
Question 2. What is the minimal level of symmetry of a graph Γ of order as a function of ? Question 1. Does there exist a graph Γ of order and level of symmetry equal to − for arbitrarily large ≥ 2?
but suggest a possible relation between the parameters and .
Lemma 4. Let < be positive integers, and suppose that the number of asymmetric graphs of order is smaller than (︀ )︀ . Then, the level of symmetry of any graph Γ of order is greater than or equal to .
Proof 4. If Γ is of order , and (︀ )︀ is greater than the number of asymmetric graphs of order , the list of all -vertex induced graphs of Γ necessarily contains an induced non-asymmetric subgraph of order or contains two isomorphic asymmetric induced subgraphs of order . In either case, Γ admits a non-trivial partial automorphism whose domain is a -vertex induced subgraph of Γ , and whose rank is therefore .
Corollary 2. Let be a positive integer and let be the smallest positive integer satisfying the inequality ( − 1)( − 2) · · · ( − + 1) ≥ 2(2). (1) The level of symmetry of any graph Γ of order is greater than or equal to .
Proof 5. Our proof is based on a rather rough estimate. As it is well-known, the number of non-labeled non-isomorphic () graphs of order is at most 2 2! , and so the same must be true for the number of non-isomorphic asymmetric graphs of order . Thus, applying Lemma 4 yields the desired result for all graphs of order satisfying the inequality ︃( )︃ =
! !( − )! ≥ 2(2) ! which can be simplified into (1).
which might prove useful in determination of (Γ) . Question 3. When given two graphs of the same order, does higher symmetry level of one of them necessarily mean that it will also have a larger monoid of partial automorphisms?
Diploma Thesis [2] and are based on an application and an algorithm for finding partial symmetries of graphs developed therein. A quick summary of the obtained results includes the following: • An exhaustive search of all graphs of order ≤ 10 determined the symmetry levels of all of them and showed that all of them have level of symmetry at least − 2
. • A recursive construction of graphs of order = 11 from asymmetric graphs of order 10 yielded a complete list of graphs of order 11 whose level of symmetry is 111− 1 3 ; it also determined that there are no graphs of order 11 with the level of symmetry 111− 1 , 4 ≤ ≤ . • Constructions of graphs with smaller level of symmetry include a record graph of symmetry level − 4 , for = 14. • Randomized constructions of graphs with smaller level of symmetry yield graphs of symmetry level − 5 , for ≥ 15.
3.1. Minimal asymmetric graphs
Even though the above corollary does not resolve Ques- As stated already in the Introduction, all minimal asymtion 1, it does yield the result that the minimal rank of metric graphs are of the symmetry level − 1 , with a partial automorphism of a graph increases with the being the order of the graph. Figure 1 shows the smallest order of the graph. More precisely, solving the equa- (with respect to the order and number of edges) asymmetric graph. Under inspection we see, that the graph tion ( − 1)( − 2) · · · ( − + 1) ≈ 2(2) yields does not have any non-trivial symmetries, but its every ≈ log√2 which gives the approximate lower bound induced subgraph on at least two vertices has non-trivial (Γ) ≥ log√2 , for all graphs Γ of order . This re- automorphisms. sult does not, however, take into the account the struc- Table 1 shows the minimal asymmetric graphs, their tural properties of graphs. In fact, preliminary results numbers of vertices, edges, pairwise non-isomorphic inof the first of the authors suggest the improved bound duced subgraphs (number of isomorphism classes), and (Γ) ≥ 3 . This motivates us to state the following number of partial symmetries. We know from Lemma 1 refinement of Question 1: that the partial automorphism monoids for a graph Γ lows that none of the 8 asymmetric graphs of order 6, of which all are minimal, have asymmetric subgraphs with 5 vertices [6][7]. Using the above mentioned script, it was then shown that of all the 1044 of order 7, exactly 152 are asymmetric [5]. None of these graphs have symmetry level 7− 2
with 8 vertices, there are 8 graphs with symmetry level 8− 8 2 . Of all asymmetric graphs of orders 9 and 10, 2608 are of symmetry level 9− 9 2 and more than a million of symmetry level 10− 2 10 .
Figure 1: The smallest (with respect to the order and number Based on the findings from [ 1], we know that almost of edges) asymmetric graph; graph X1 in the list of asymmetric all finite graphs are asymmetric. Thus, as grows, the graphs in [7]. number of asymmetric graphs with vertices gets closer to the total number of all graphs of order . It is also reasonable to expect that the number of asymmetric graphs and its complement Γ˜ are equal. Similarly, the number of wofitohrdthere graonwdthsyomfm.eTtrhyislepvaetlter−n 2sesehmousltdo bbee isnucprpeaosritnedg induced subgraphs and the number of partial symmetries by the obtained data, as only 8 graphs of order 8 are of is the same for any graph and its complement. Hence, symmetry level 8− 8 2 , 2608 graphs of order 9 have symthe list contains only 9 of the 18 minimal asymmetric metry level 9− 9 2 , and more than a million have symmetry graphs (which come in complementary pairs). level 10− 2 (of almost 8 million asymmetric graphs).
We also found the partial automorphism monoid for Chec1k0ing all previously found graphs determined that ceoacmhpolefttehelismt ionfimthaelseasmymonmoeidtrsi.c graphs. [2] contains the Wnoe garvaopihdsedofusoirndgerth≤ e d1e0vealroepeodf spyromgmraemtrytolecvheelck−a3ll. unlabelled graphs with 11 vertices, since there are more 3.2. Symmetry Levels of Small Graphs than a billion such graphs. Instead, a diferent approach The second author created an application to provide an in- was used. Based on the list of all asymmetric graphs of terface for easy work with graphs, graph symmetries, and order 10, a program created all possible 11-vertex graphs partial symmetries. As a result, a simple script allowed by adding a new vertex. In total, there are 210 possible us to answer the question whether there exist graphs of ways of adding a new vertex to a 10-vertex graph. Using order ≤ 10 of symmetry levels − 1 . The script relied ltehviselap1p1−ro3ach, we found 11-vertex graphs with symmetry on the list of (non-isomorphic) unlabelled simple graphs 11 . generated by McKay and published in GAP format [4]. Utilizing the previous findings and our extensive liErdős and Rényi already established that there are no brary, we implemented a function __, which tahsyermemareetrnicogarsaypmhsmwetirtihc 2g r≤aphs≤ w5ithve5rtviceerstic[1e]s., Sitinfocel- lteavkeels. aTghreanphwaes eaxntaerngduemdetnhteaanpdprreotaucrhnsdietsscsryibmemdeptrreyviously by taking any -vertex asymmetric graph and creating an + 1-vertex graph by adding a new verGraph Vertices Edges # of # of tex. In total, there are 2 diferent ways of doing this, code non-isomorphic partial since the new vertex is either isolated or it is added as induced symmetries a neighbor to any -vertex subset of the set of vertices, subgraphs 1 ≤ ≤ . The function ℎ__ is X1 6 6 20 768 then used to verify whether the new graph has a desired X2 6 7 22 704 symmetry level. Using this approach recursively, graphs XX43 66 77 2210 678104 of order 14 vertices and symmetry level 141− 4 4 were conX9 7 6 28 3373 structed. Unfortunately, this approach is computationally X10 7 7 30 2793 dificult and would not be appropriate for finding all 14
X15 8 9 45 9728 Finally, in order to construct graphs of order and X16 8 10 45 8560 symmetry level − 5 , random graphs of orders between Table 1 15 and 30 were generated and their symmetry levels were The number of non-isomorphic induced subgraphs and partial determined. The search did yield some graphs of symsymmetries of minimal asymmetric graphs (graph codes taken metry level − 5 . Due to the combinatorial explosion ocfrom [7]). curring when working with graphs, their subgraphs, and symmetries, exhaustive searches become very quickly infeasible. the complete graph or its complement. Removal of just one edge from significantly reduces the number 3.3. Number of partial automorphisms of partial symmetries. For = 9, the number drops from 17, 572, 114 partial symmetries in case of 9 to Due to the fast rise of the number of partial symmetries 4, 582, 270 partial symmetries for 9 ∖ {}. with respect to the rise of the orders of the considered Next, we noticed that for graphs with edges, 1 ≤ graphs, we wanted to know if one can predict the number ≤ 9, there is always one graph with a number of parof partial symmetries of a graph by looking at its struc- tial symmetries higher than all the other -edge graphs. ture. For this reason, the numbers of partial symmetries These special graphs consist of a -vertex star with all for all unlabelled graphs of orders , 3 ≤ ≤ 9, were other vertices being isolated. calculated. Despite 9 having more than 17 million partial sym
To find the number of partial automorphisms of a given metries, the mean number of partial symmetries for graph Γ , it sufices to find all isomorphism classes of graphs of order 9 is only 22154, a decrease of 99.5%. induced subgraphs of Γ , the corresponding numbers of We also calculated the mean values for graphs of 3 to 8 induced subgraphs belonging to these classes, and the vertices, and based on the data, we predicted the mean of orders of the automorphism groups of representatives in partial symmetries for graphs with fewer than 17 vertices. these classes. The number of partial symmetries within The prediction can be seen in Fig. 3. a specific isomorphism class can then be calculated using the formula ||2 × | ( )|, where is a representative of .