¿^creative	, ars mathematica
^commons	contemporánea
Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 8 (2015) 215-223
On automorphism groups of graph truncations
Brian Alspach
School of Mathematical and Physical Sciences University of Newcastle Callaghan, NSW 2308 Australia
Edward Dobson
Departmentment ofMathematics and Statisitics Mississippi State University Mississippi State, MS 39762 USA and UP IAM University of Primorska Muzejeska trg 2, 6000 Koper, Slovenia
Received 11 May 2014, accepted 13 November 2014, published online 17 December 2014
Abstract
It is well known that the Petersen graph, the Coxeter graph, as well as the graphs obtained from these two graphs by replacing each vertex with a triangle, are trivalent vertex-transitive graphs without Hamilton cycles, and are indeed the only known connected vertex-transitive graphs of valency at least two without Hamilton cycles. It is known by many that the replacement of a vertex with a triangle in a trivalent vertex-transitive graph results in a vertex-transitive graph if and only if the original graph is also arc-transitive. In this paper, we generalize this notion to t-regular graphs r and replace each vertex with a complete graph Kt on t vertices. We determine necessary and sufficient conditions for T(r) to be hamiltonian, show Aut(T(r)) = Aut(r), as well as show that if r is vertex-transitive, then T(r) is vertex-transitive if and only if r is arc-transitive. Finally, in the case where t is prime we determine necessary and sufficient conditions for T(r) to be isomorphic to a Cayley graph as well as an additional necessary and sufficient condition for T(r) to be vertex-transitive.
Keywords: Truncation, automorphism group, Cayley graph, Hamiltonian. Math. Subj. Class.: 05C25
E-mail addresses: brian.alspach@newcastle.edu.au (Brian Alspach), dobson@math.msstate.edu (Edward Dobson)
©® This work is licensed under http://creativecommons.org/licenses/by/3.0/
216
ArsMath. Contemp. 8(2015)215-223
1 Introduction
In 1969 Lovasz posed the problem below (this statement is written exactly as Lovasz wrote it).
Problem 1.1 (Lovasz, 1969). Let us construct a finite, connected, undirected graph which is symmetric and has no simple path containing all elements. A graph is called symmetric, if for any two vertices x, y it has an automorphism mapping x into y.
Usually this problem is stated as the conjecture that every vertex-transitive graph contains a Hamilton path (here "vertex-transitive" and "symmetric" are synonyms). Typically though it is usually the case that this conjecture is verified by showing that a a particular vertex-transitive graph contains a Hamilton cycle. Much work has been done in attempting to verify this conjecture — see [5] for some recent information regarding progress on this conjecture. The Petersen graph is vertex-transitive but does not contain a Hamilton cycle (see for example [3, Theorem 1.5.1]), while Tutte [9] first showed that the Coxeter graph is not hamiltonian, with an additional proof by Biggs [1]. The graphs obtained from the Petersen graph and the Coxeter graph by replacing each vertex with a triangle — called the truncation — are also vertex-transitive graphs that do not contain a Hamilton cycle. These four graphs are the only known connected vertex-transitive graphs, other than K2, that do not have a Hamilton cycle. The truncation of the Petersen graph is shown in Figure 1.
It turns out that the truncation of the truncation of the Petersen and Coxeter graphs are not vertex-transitive. It is known by many that the truncation of a trivalent graph r
Brian Alspach and Edward Dobson: On automorphism groups of graph truncations
217
is vertex-transitive if and only if Aut(T) is also transitive on the edges of r, or edge-transitive, although neither of the previously stated facts are proven in the literature. We will generalize the notion of truncation to vertex-transitive graphs of valencies other than 3. Note that as a triangle can be viewed as either a cycle of length 3 or a complete graph K3, there are two natural generalizations of the idea of truncation. Namely, one can "replace" each vertex with a cycle or with a complete graph, or even with an arbitrary graph. These have been studied for example in [2, 6, 11] We note that in [11], the graph obtained by replacing each vertex with a complete graph is called a clique-inserted graph, and that replacing each vertex with a cycle is motivated by map truncation. For a vertex v e V(T), we denote the valency of v in r by val(v).
Definition 1.2. Let r be a graph. The truncation T(r) of r is obtained from r by replacing each vertex v of r with a clique on val(v) vertices, denoted Tv, and whenever uv e E(r), then one vertex of Tv is adjacent to one vertex of Tu and no vertex of Tv is adjacent to more than one vertex outside of Tv.
Note that if uv e E(r), we do not specify which vertex of Tu is adjacent to Tv. Obviously, different choices of such vertices will result in different graphs, but all such choices result in isomorphic graphs as each Tu and Tv is a complete graph and no vertex of Tv is adjacent to more than one vertex outside of Tv. Also, as each vertex in Tv is adjacent to val(v) - 1 vertices inside Tv and exactly one vertex outside Tv, a vertex u e Tv has valency val(v) in the truncation T(r) . In particular, the truncation of a t-regular graph is still t-regular.
We should point out that there is an equivalent definition of graph truncation introduced in [7]. For a graph r, let S(r) be the graph obtained from r by subdividing each edge via the insertion of a single vertex, and L(r) be the line graph of r. Then T(r) = L(S(r)).
In this paper we show T(r) contains a Hamilton cycle if and only if r has a spanning eulerian subgraph (Theorem 2.1). We then show that for a graph r with minimal valency at least 3 the automorphism group of its truncation is isomorphic to Aut(r) (Theorem 3.6), and subsequently that a connected vertex-transitive graph with minimal valency at least 3 has a vertex-transitive truncation if and only if it is arc-transitive (Theorem 3.7), or transitive on the set of directed edges or arcs of r. We remark that this is consistent with the statements earlier that a trivalent vertex-transitive graph has vertex-transitive truncation if and only if it is edge-transitive as a vertex- and edge-transitive graph of odd valency is necessarily arc-transitive [10, 7.53]. Finally, for a vertex-transitive graph r of prime valency, we also determine necessary and sufficient conditions for T(r) be a Cayley graph provided that T(r) is vertex-transitive (Theorem 3.8), as well as provide an alternative characterization of when T(r) is vertex-transitive (Theorem 3.10). We begin with necessary and sufficient conditions for T(r) to be Hamiltonian.
2 Hamiltonicity of Graph Truncations
Theorem 2.1. If r is a graph, then T(r) contains a Hamilton cycle if and only if r contains a connected spanning eulerian subgraph.
Proof. First suppose that r has a connected spanning eulerian subgraph A, and let v0vi • • • vrv0 be an Euler tour of A, where we traverse the tour so that the edge vjvi+1 is traversed from vi to vi+1. Given that the edge vjvi+1 is traversed from vi to vi+1, let uij0 and ui+1j1 denote the vertices of Tv. and Tvi+1, respectively, that are adjacent. For each x e V(r), we
218
Ars Math. Contemp. 8 (2015) 215-223
let xm be the largest nonnegative integer for which vXm = x, set Yx = {i < xm : vi = x}, and Zx = {«¿,0, «i,i : i € Yx}. For each 1 < i < r construct a path Pi as follows: Setting x = vi, we let Pi = ui,0 if i < xm, while if i = xm, we let Qi be a Hamilton path from «i,i to Ui,o in T(r)[Tx - Zx], the subgraph of T(T) induced by Tx - Zx. Let Pi be the path obtained from Qi by removing the initial vertex ui,1 of Qi. We observe that Qi and consequently Pi certainly exist as T(r)[Tx - Zx] is a clique. Then
U0,0«1,lPl«1,0«2,lP2«2,0 . . . «r,lPr«r,0«0,lP0«0,0
is a Hamilton cycle in T(r). Intuitively, we travel along the Euler tour until the last time we visit a Tv, at which point we traverse all the previously unvisited vertices of Tv.
Conversely, suppose that H = v0vl... vn is a Hamilton cycle in T(r) (so vn = v0). For each 0 < i < n, let vi € Txi, xi € V(r). Let E' = {xixi+l : Txi = Txi+1}, so that E' is simply the set of edges of H that connect different inserted cliques. Then the edges of E' form a spanning connected subgraph of r as H is a Hamilton cycle in T(r). Additionally, with the exception of Tx0 and Txn = Tx0, each time one traverses H and enters a Tx, one must exit that Tx. We conclude that every vertex of the graph formed by the edges of E' has even valency and so this graph is eulerian.	□
In the case of trivalent graphs, as the only spanning eulerian subgraph of a trivalent graph is necessarily a Hamilton cycle, we have the following result.
Corollary 2.2. The truncation of a trivalent graph r is hamiltonian if and only if r is hamiltonian.
As the Petersen graph and the Coxeter graph are both trivalent graphs that are not hamiltonian, the following result is evident.
Corollary 2.3. The truncations of the Petersen graph and the Coxeter graph are not hamil-tonian.
3 Vertex-transitive Graph Truncations
While the truncation of any vertex-transitive trivalent graph that is not hamiltonian will give a trivalent graph that is not hamiltonian, the truncation of such a graph need not be vertex-transitive. Indeed, the truncations of the truncations of the Petersen and Coexeter graphs are not hamiltonian, but it turns out that they are not vertex-transitive. We now investigate when the truncation of a vertex-transitive graph is vertex-transitive. We begin by studying the relationship between Aut(r) and Aut(T(r)) for any graph r.
Definition 3.1. Let r be a graph. We call the set T = {Tv : v € V(r)} the fundamental vertex partition of V(T(r). There is also a fundamental edge partition of E(T(r)) with two cells, where one cell consists of those edges within a Tv, v € V(r) (the clique edges), and the other cell consisting of those edges between two inserted cliques (the original edges).
Lemma 3.2. Let r be a graph with each vertex of valency at least 3. Then the fundamental vertex and edge partitions of T(r) are invariant under Aut(T(r)).
Brian Alspach and Edward Dobson: On automorphism groups of graph truncations
219
Proof. We need only show that the fundamental vertex partition of T(T) is invariant under Aut(T(r)), as this implies that the fundamental edge partition is invariant under Aut(T(r)). An edge xy with x G V(Tv) and y G V(Tu), u = v, cannot belong to a triangle because y is the only neighbor of x not in V(Tv) and x is the only neighbor of y not in V(Tu). On the other hand, every edge xy with x, y in the same V(Tv) belongs to a triangle because Tv is a clique and t > 3. This then implies that Aut(T(r)) permutes the sets in the partition T = {V(Tv) : v G V(r)}.	□
We now introduce standard permutation group theoretic terms related to the fundamental vertex partition.
Definition 3.3. Let G < Sn be transitive and act on Zn. Let B C Zn. If g(B) = B or g(B) n B = 0 for every g G G, then B is a block of G. If B is a block, then g(B) is also a block for all g G G, and {g(B) : g G G} is a G-invariant partition. Of course, singleton sets and Zn are blocks for every transitive group G < Sn, and the corresponding G-invariant partitions are trivial. If G has a nontrivial G-invariant partition, then G is imprimitive, and is primitive otherwise. Finally, for a G-invariant partition B, we denote by fixG(B) the subgroup of G which fixes each block of B setwise. That is, fixG(B) = {g G G : g(B) = B for all B G B}.
We remark that if Aut(T(r)) is transitive, then the fundamental vertex partition is an Aut(T (r))-invariant partition.
Now observe that if r is a cycle of length n, then T(r) is a cycle of length 2n. Hence Aut(T (r)) = D2n, the dihedral group of order 4n. Henceforth, we will assume that every vertex has valency at least 3, in which case T(r) always contains a triangle.
Theorem 3.4. Let r be a graph where each vertex of r has valency at least 3. Then Aut(T (r)) acts faithfully on the fundamental vertex partition T and is isomorphic to a subgroup of Aut(r).
Proof. That Aut(r) acts on T was established in Lemma 3.2. Let K be the kernel of the action of Aut(T(r)) on T (if Aut(T(r)) is transitive, then K = fixAut(T(r}}(T)). We claim that K = 1. Indeed, if K = 1 with 1 = 7 G K, then let Tv G T such that K |Tv = 1. Then there exist distinct x, y G Tv such that 7(x) = y. Now, x is adjacent to some vertex z G Tu, u = v, and so y(x)y(z) is also an edge from Tv to Tu. However, there is only one edge from a vertex of Tv to a vertex of Tu in T(r), a contradiction. Thus K =1.
To finish the result, we need only show that if 7 G Aut(T(r)), then 7 G Aut(r), where 7 is the induced action of 7 on T. So suppose that uv g E(r). Then some vertex of Tu is adjacent to some vertex of Tv ,andas 7 G Aut(T (r)), some vertex of y(Tu) = T^(u} is adjacent to some vertex of y(Tv) = T^(v}. But this occurs if and only if 7(u)7(v) G
E(r).	□
Corollary 3.5. The truncations of the truncations of the Petersen and Coxeter graphs are not vertex-transitive.
Proof. Let r be the Petersen or Coexeter graph. If T(T(r)) is vertex-transitive, then 9 divides |Aut(T(T(r)))| as |V(T(T(r)))| = 9|V(r)| and the size of an orbit or a group divides the order of the group. By Theorem 3.4 applied twice, we see that 9 divides |Aut(r)|. However, the automorphism group of the Petersen graph has order 120 as it is isomorphic to S5 (see for example [3, Theorem 1.4.6]) while the automorphism group of
220
Ars Math. Contemp. 8 (2015) 215-223
the Coexeter graph has order 336 as it is PGL(2,7) (see for example [1]), neither of which are divisible by 9.	□
Theorem 3.6. If r is a graph with each vertex of valency at least 3, then Aut(T (r)) =
Aut(r).
Proof. In view of Theorem 3.4, it suffices to show that each element of Aut(r) induces an element of Aut(T(r)), and that different elements of Aut(r) induce different elements
of Aut(T (r)).
Let y € Aut(r). Let x G V(T(r)), and v G V(r) with x G Tv. Then there exists a unique y G V(T) not contained in Tv with xy G E(T(r)). Let u G V(r) such that y G Tu. Then y(u)y(v) g E(r), and so there exists vertices xX G TY(v) and y' G TY(u) such that x'y' G E(T(r)). Define Y : V(T(r)) ^ (T(r)) by Y(x) = x'. Note that as the original edges of T(r) form a perfect matching, Y is a well-defined bijection. Additionally, by definition, Y maps the original edges of T(r) to the original edges of T(r). As y also map the fundamental vertex partition of T(r) to itself, it maps the clique edges of T(r) to the clique edges of T(r). Thus Y G Aut(T(r). Finally, as the induced action of Y on T is y and Aut(T(r) is faithful on T by Lemma 3.2, different elements of Aut(r) induce different elements of Aut(T(r).	□
For a transitive group G acting on Zn, we denote the stabilizer in G of v by StabG (v). Then StabG(v) = {g G G : g(v) = v}. Concerning the statement of the following result, a vertex- and edge-transitive graph of odd valency is necessarily arc-transitive [10, 7.53].
Theorem 3.7. If r is a connected vertex-transitive graph with each vertex of valency t > 3, then T (r) is vertex-transitive if and only if r is arc-transitive. Additionally, T (T (r)) is not vertex-transitive.
Proof. Before proceeding, some general observations about T(r) are in order. As T(r) is regular of valency t, T(r)[Tv] is regular of valency t - 1. As | V(Tv) | = t, we see that there are exactly t edges with one end in Tv and the other end not in Tv, and of course each vertex of Tv is incident with exactly one such edge. Additionally, between some vertex of Tv and some vertex of Tu there is either exactly one edge if uv g E(r) or no edges if uv G E(r). Thus, each edge with one endpoint in Tv and the other endpoint outside of Tv uniquely determines a vertex in Tv and uniquely determines a Tu in which the other endpoint of the edge is a vertex. Conversely, each vertex x of Tv uniquely determines an edge with x as an endpoint and one endpoint not in Tv.
Suppose that r is arc-transitive, with v G V(r). Then StabAut(-r) (v) is transitive on the neighbors Nr(v) of v. Set Nr(v) = {ui,..., ut} and let Yi,j G StabAut(r)(v) such that Yi(ui) = uj. As Aut(r) = Aut(T(r)) by Theorem 3.6 and Aut(T(r)) acts faithfully on T = {Tv : v G V(r)} by Theorem 3.4, there exists a unique Yi,j G Aut(T(r)) such that the action of Yi,j on T is Yi,j. As the action of Aut(T(r)) on T is Aut(r) which is transitive, in order to show that Aut(T(r)) is transitive it suffices to show that {J G Aut(T(r)) : J(Tv) = Tv} is transitive on Tv. Let x, y G Tv. Then there exist 1 < ij < t such that xvui,yvu3- G E(T(r)), where vu, G Tu, and vu3 G T^. Then Yi,j(Tu,) = Tu3-and Yi,j (Tv) = Tv. As each vertex of Tv is incident with exactly one edge whose other endpoint is not in Tv and Yi,j G Aut(T(r)), we have that Yi,j(xvui) is the unique edge of T(r) with one endpoint in Tv and the other in Tuj. That is, Yi,j (xvu,) = yvuj. As
Brian Alspach and Edward Dobson: On automorphism groups of graph truncations
221
%j(TV) = TV, we conclude that (x) = y. Thus {J G Aut(T(r)) : ¿(Tv) = Tv} is transitive on Tv and the result follows.
Conversely, suppose that T(r) is vertex-transitive. It suffices to show that the stabilizer in Aut(r) of v G V(r) is transitive on its neighbors. Observe that T = {Tv : v G V(r)} is an Aut(T(r))-invariant partition and Hv = {h G Aut(T(r)) : h(Tv) = Tv}, v G V(r), is transitive on Tv. Hence, if x, y G V(Tv), then there exists Yx,y G Aut(T(r)) such that Yx,y (x) = y. For each vertex x of Tv, we denote the uniquely determined edge with x as an endpoint and with the other endpoint not in Tv by 6x — xZx. We let vx g V(r) be such that zx G V(Tvx), and observe that if x, y G V(Tv) with x = y, then Tvx = Tvy. Each edge xzx with x g V(Tv) then induces an edge vvx g E(r), and such edges are pairwise distinct. More specifically, there are exactly t edges vvx g E(r) induced by edges of the form xzx with x G V(Tv). This then implies that the neighbors in r of v are {vx : x G V(Tv)}. Finally, observe that Yx,y (xzx) is an edge with one endpoint y G V(Tv) and Yx,y (zx) G V(Tv). Denoting by 7x,y the automorphism of V(r) induced by the action of Yx,y on T (with each Ta identified with the vertex a), we see that 7x,y (vvx) = vvy, and the stabilizer of v G V(r) in Aut(r) is transitive on the neighbors of v and so r is arc-transitive.
It now only remains to show that T(T(r)) is not vertex-transitive. In view of our earlier arguments, it suffices to show that if r is edge-transitive, then T(r) is not edge-transitive. If r is edge-transitive, then Aut(T(r)) is transitive, and Aut(T(r)) admits T as an Aut(r)-invariant partition. But T(r) contains edges with both endpoints in Tv and edges with one endpoint in Tv and one endpoint outside of Tv. As T is an Aut(r)-invariant partition, no automorphism will map an edge of the former type to an edge of the latter type.	□
We now restrict our attention to graphs with prime valency. We remark that in the following result, the restriction to prime valency is only used to establish sufficiency.
Theorem 3.8. If r is a connected arc-transitive graph of prime valency t > 3 and order n, then T (r) is isomorphic to a Cayley graph if and only if Aut(r) contains a transitive group of order nt.
Proof. As a vertex-transitive graph is isomorphic to a Cayley graph if and only if its automorphism group contains a regular subgroup [8], T(r) being a Cayley graph implies that Aut(T(r)) contains a transitive group R of order nt which is a isomorphic to a transitive subgroup of Aut(r) of order nt by Theorem 3.4.
Conversely suppose there exists R < Aut(r) such that R is transitive on V(r) and has order nt. It suffices to show that for fixed v G V(r), the subgroup H of R fixing the set V(Tv) is transitive on V(Tv), as then R is transitive and as |R| = |V(T(r))|, we have that R is regular.
Now, T is an Aut(T(r))-invariant partition, and the action of R on T, which we denote by R/T, is transitive. Then H/T fixes the vertex v G V(r), and so |H/T| = t. Let t G H be of prime order t. Then every orbit of t has prime order t or has order 1. If t in its action on Tv is a t-cycle, then H is transitive on V(Tv) and the result follows. Otherwise, t is the identity in its action on V(Tv). As r is connected and t has prime order t = 1, there exists u G V(r) such that the action of t on Tu is the identity, and some vertex y of Tu is adjacent to a vertex z g V(Tw), w = v, and z is not fixed by t. Applying t to the edge yz, we see that y is adjacent to t vertices not in Tv and to t - 1 vertices contained in Tv. Then the valency of y is 2t - 1, a contradiction.	□
222
Ars Math. Contemp. 8 (2015) 215-223
Corollary 3.9. The truncations of neither the Petersen graph nor the Coxeter graph are isomorphic to Cayley graphs.
Proof. As the automorphism groups of the Petersen graph and the Coxeter graph are S5 and PGL(2,7) of orders 120 and 336, respectively, according to Theorem 3.8 the truncations of these graphs are Cayley if and only if their automorphism groups contain subgroups of index 4. Each of these automorphism groups though contain simple groups of index 2 (A5 and PSL(2,7) respectively), and as neither of them are direct products, their only normal proper nontrivial subgroups are A5 and PSL(2,7), respectively. Any subgroup of either of index 4 would then give an embedding into S4 by [4, Corollary 4.9], which is solvable. □
Theorem 3.10. If r is a connected vertex-transitive graph of prime valency p, then T (r) is vertex-transitive if and only if Aut(r) contains an element of order p with a fixed point.
Proof. Suppose that T(r) is vertex-transitive. Then T is an Aut(T(r))-invariant partition, and so StabAut(T(r))(Tv)|Tv is transitive on Tv. As Tv has order p, it follows that StabAut(T(r))(Tv)|contains an element of order p. Let 7 G StabAut(T(r)) (Tv) such that y| Tv has order p. Without loss of generality, we assume that 7 has order p (although we will no longer necessarily have that 7|Tv has order p — for our purposes we only need an element of order p that fixes some Tv). By Theorem 3.4, Aut(T(r)) acts faithfully on T, and so 7/T = 1. Then 7/T has order p, fixes the point v, and by Theorem 3.4 the permutation 7/T is contained in Aut(r).
Suppose that Aut(r) contains an element 7 of order p with a fixed point. As r is connected, some fixed point u of 7 is adjacent in r to some point u that is not fixed by 7. This follows as there is certainly vertices x, y G V(r) with x fixed by 7 and y not fixed by 7. We then let u be the first vertex of an xy-path in r that is not fixed by 7, and v its predecessor on the chosen xy-path. As 7 preserves adjacency, all elements in the (nontrivial) orbit of u are neighbors of v. Since 7 is of prime order p, the orbit of u is of length p, and since p is the valency of the graph, the orbit of u contains all the neighbors of v. Thus, Aut(r) acts transitively on the arcs emanating from v and transitively on the vertices of r, and is therefore arc-transitive. The result then follows by Theorem 3.7.	□
There are a few questions which remain unanswered. First, is it true that Theorem 3.8 holds when the valency t is not prime? Similarly, does Theorem 3.10 hold when the valency is not prime? More specifically, if r has valency t is it the case that T(r) is vertex-transitive if and only if Aut(r) contains a subgroup of order t with a fixed point (i.e. every element fixes the same point). Finally, what exactly is the group StabAut(T(r))(Tv) in its action on Tv ? Of course, as an abstract group it is isomorphic to StabAut(r)(v), but what is the action?
Acknowledgement: The authors are indebted to the anonymous referees whose careful reading of this manuscript resulted in suggestions that improved the exposition, results, and proofs in this paper.
References
[1]	N. Biggs, Three remarkable graphs, Canad. J. Math. 25 (1973), 397-411.
[2]	G. Exoo and R. Jajcay, Recursive constructions of small regular graphs of given degree and girth, Discrete Math. 312 (2012), 2612-2619, doi:10.1016/j.disc.2011.10.021.
Brian Alspach and Edward Dobson: On automorphism groups of graph truncations
223
[3]	D. A. Holton and J. Sheehan, The Petersen graph, volume 7 of Australian Mathematical Society Lecture Series, Cambridge University Press, Cambridge, 1993, doi:10.1017/ CBO9780511662058.
[4]	T. W. Hungerford, Algebra, volume 73 of Graduate Texts in Mathematics, Springer-Verlag, New York, 1980, reprint of the 1974 original.
[5]	K. Kutnar and D. Marusic, Hamilton cycles and paths in vertex-transitive graphs—current directions, Discrete Math. 309 (2009), 5491-5500, doi:10.1016/j.disc.2009.02.017.
[6]	A. Malnic, T. Pisanski and A. Zitnik, The clone cover, Ars Math. Contemp. 8 (2015), 95-113.
[7]	T. Pisanski and T. W. Tucker, Growth in repeated truncations of maps, Atti Sem. Mat. Fis. Univ. Modena 49 (2001), 167-176, dedicated to the memory of Professor M. Pezzana (Italian).
[8]	G. Sabidussi, Vertex-transitive graphs, Monatsh. Math. 68 (1964), 426-438.
[9]	W. T. Tutte, A non-Hamiltonian graph, Canad. Math. Bull. 3 (1960), 1-5.
[10]	W. T. Tutte, Connectivity in graphs, Mathematical Expositions, No. 15, University of Toronto Press, Toronto, Ont., 1966.
[11]	F. Zhang, Y.-C. Chen and Z. Chen, Clique-inserted-graphs and spectral dynamics of clique-inserting, J. Math. Anal. Appl. 349 (2009), 211-225, doi:10.1016/j.jmaa.2008.08.036.