# TorontoCity: Seeing the World with a Million Eyes

Shenlong Wang, Min Bai, Gellert Mattyus, Hang Chu, Wenjie Luo, Bin Yang,
Justin Liang, Joel Cheverie, Sanja Fidler, Raquel Urtasun
Department of Computer Science, University of Toronto
{slwang, mbai, mattyusg, chuhang1122, wenjie, byang, justinliang, joel,
fidler<EMAIL_ADDRESS>
###### Abstract

In this paper we introduce the TorontoCity benchmark, which covers the full
greater Toronto area (GTA) with $712.5km^{2}$ of land, $8439km$ of road and
around $400,000$ buildings. Our benchmark provides different perspectives of
the world captured from airplanes, drones and cars driving around the city.
Manually labeling such a large scale dataset is infeasible. Instead, we
propose to utilize different sources of high-precision maps to create our
ground truth. Towards this goal, we develop algorithms that allow us to align
all data sources with the maps while requiring minimal human supervision. We
have designed a wide variety of tasks including building height estimation
(reconstruction), road centerline and curb extraction, building instance
segmentation, building contour extraction (reorganization), semantic labeling
and scene type classification (recognition). Our pilot study shows that most
of these tasks are still difficult for modern convolutional neural networks.

##  1 Introduction

> ”It is a narrow mind which cannot look at a subject from various points of
> view.”
>
> George Eliot, Middlemarch

In recent times, a great deal of effort has been devoted to creating large
scale benchmarks. These have been instrumental to the development of the
field, and have enabled many significant break-throughs. ImageNet [9] made it
possible to train large-scale convolutional neural networks, initiating the
deep learning revolution in computer vision in 2012 with SuperVision (most
commonly refer as AlexNet [16]). Efforts such as PASCAL [11] and Microsoft
COCO [18] have pushed the performance of segmentation and object detection
approaches to previously inconceivable levels. Similarly, benchmarks such as
KITTI [12] and Cityscapes [8] have shown that visual perception is going to be
an important component of advanced driver assistance systems (ADAS) and self-
driving cars in the imminent future.

Data

Maps

Tasks

Figure 1: Summary of the TorontoCity benchmark. Data source: aerial RGB image,
streetview panorama, GoPro, stereo image, street-view LIDAR, airborne LIDAR;
Maps: buildings and roads, 3D buildings, property meta-data; Tasks: semantic
segmentation, building height estimation, instance segmentation, road
topology, zoning segmentation and classification.

However, current large scale datasets suffer from two shortcomings. First,
they have been captured by a small set of sensors with similar perspectives of
the world, e.g., internet photos for ImageNet or cameras/LIDAR mounted on top
of a car in the case of KITTI. Second, they do not contain rich semantics and
3D information at a large-scale. We refer the reader to Fig. 2 for an analysis
of existing datasets.

In this paper, we argue that the field is in need of large scale benchmarks
that allow joint reasoning about geometry, grouping and semantics. This has
been commonly referred to as the three R’s of computer vision. Towards this
goal, we have created the TorontoCity benchmark, covering the full greater
Toronto area (GTA) with $712.5km^{2}$ of land, $8439km$ of road and around
$400,000$ buildings. According to the census, $6.8million$ people live in the
GTA, which is around $20\%$ of the population of Canada. We have gathered a
wide range of views of the city: from the overhead perspective, we have aerial
images captured during four different years as well as LIDAR from airborne.
From the ground, we have HD panoramas as well as stereo, Velodyne LIDAR and
Go-pro data captured from a moving vehicle driving around in the city. We are
also augmenting the dataset with a 3D camera as well as imagery captured from
drones.

Manually labeling such a large scale dataset is not feasible. Instead, we
propose to utilize different sources of high-precision maps to create our
ground truth. Compared to online map services such as OpenStreetMap [1] and
Google Maps, our maps are much more accurate and contain richer meta-data,
which we exploit to create a wide variety of diverse benchmarks. This includes
tasks such as building height estimation (reconstruction), road centerline and
curb extraction, building instance segmentation, building contour extraction
(reorganization), semantic labeling and scene type classfication
(recognition). Participants can exploit any subset of the data (e.g., aerial
and ground images) to solve these tasks.

One of the main challenges in creating TorontoCity was aligning the maps to
all data sources such that the maps can produce accurate ground truth. While
the aerial data was perfectly aligned, this is not the case of the panoramas
where geolocalization is fairly noisy. To alleviate this problem, we have
created a set of tools which allow us to reduce the labeling task to a simple
verification process, speeding up labeling, thus making TorontoCity possible.

We perform a pilot study using the aerial images captured in 2011 as well as
the ground panoramas. Our experiments show that state-of-the-art methods work
well on some tasks, such as semantic segmentation and scene classification.
However, tasks such as instance segmentation, contour extraction and height
estimation remain an open challenge. We believe our benchmark provides a great
platform for developing and evaluating new ideas, particularly techniques that
can leverage different viewpoints of the world. We plan to extend the current
set of benchmarks in the near future with tasks such as building
reconstruction, facade parsing, tree detection and tree species classification
as well as traffic lights and traffic sign detection, for which our maps
provide accurate ground truth. We have only scratched the surface of
TorontoCity’s full potential.

##  2 Related Work

Dataset | ISPRS | TUM-DLR | Aerial KITTI | KITTI | RobotCar | Ours
---|---|---|---|---|---|---
Location | Vaihingen/Toronto | Munich | Karlsruhe | Karlsruhe | Oxford | Toronto
Aerial Coverage ( $km^{2}$) | 3.49+1.45 | 8.32 | 3.23 | - | - | 712
Ground Coverage ($km$) | - |  $<$1 |  $<$20 | 39.2 | 10 |  $>$1000(pano)111We are keeping collecting more data
Aerial RGB | yes | yes | yes | - | - | yes
Drone RGB | - | yes | - | - | - | yes
Aerial LIDAR | yes | yes | - | - | - | yes
Ground Perspective | - | - | - | yes | yes | yes
Ground Panorama | - | - | - | - | yes | yes
Ground Stereo | - | yes | - | yes | yes | yes
Ground LIDAR | - | yes | - | yes | yes | yes
Aerial Resolution (pixel/$cm^{2}$) | 8 | 50 | 9 | - | - | 10
Repeats | - | - | - | partial | x10 | x4 (aerial)
Top Semantic GT (# of classes) | 100% (8) | - | 100% (4) | - | - | 100% (2 + 8)
Top Geometric GT (source) | dense (lidar) | dense (lidar) | - | - | - | dense (map+lidar)
Ground Semantic GT (# of classes) | - | - | dense (4) | object (3) | - | dense (2) / image (6)
Ground Geometric GT (source) | - | - | - | sparse (lidar) | sparse (lidar) | dense (map+lidar)

Figure 2: Statistics of our data and comparison of current state-of-the-art
urban benchmarks and datasets.

Automatic mapping, reconstruction and semantic labeling from urban scenes have
been an important topic for many decades. Several benchmarks have been
proposed to tackle subsets of these tasks. KITTI [12] is composed of stereo
images and LIDAR data collected from a moving vehicle, and evaluates SLAM,
optical flow, stereo and road segmentation tasks. Cityscapes [8] focuses on
semantic and instance annotations of images captured from a car. Aerial-KITTI
[21] augments the KITTI dataset with aerial imagery of a subset of Karlsruhe
to encourage reasoning of semantics from both ground and bird’s eye view.

The photometry community has developed several benchmarks towards urban scene
understanding [15, 24, 30, 25, 20]. TUM-DLR [15] and ISPRS Multi-Platform [24]
benchmarks contain imagery captured through multiple perspectives from UAV,
satellite images and handheld cameras. Oxford RobotCar contains lidar point
cloud and stereo images captured from a vehicle [20]. However, these
benchmarks do not offer any semantic ground-truth for benchmarking purposes.
Perhaps the most closely related dataset to ours is the ISPRS Urban
classification and building reconstruction benchmark [30], where the task is
to extract urban object, such as building, road and trees from both aerial
images and airborne laserscanner point clouds. However, this dataset has a
relatively small coverage and does not provide ground-view imagery. In
contrast, TorontoCity is more than two orders of magnitude bigger.
Furthermore, we offer many different perspectives through various sensors,
along with diverse semantic and geometric benchmarks with accurate ground-
truth. The readers may refer to Fig. 2 for a detailed comparison against
previous datasets.

A popular alternative is to use synthetic data to generate large scale
benchmarks [3, 5, 26, 29, 31, 13, 6, 28]. Through 3D synthetic scenes and
photo-realistic renderers large-scale datasets can be easily created. To date,
however, these datasets have been focused on a single view of the world. This
contrasts TorontoCity. Unlike other benchmarks, our input is real-world
imagery, and the large-scale 3D models are a high-fidelity modeling of the
real world rather than a synthetic scene.

Maps have been proven useful for many computer vision and robotics
applications [34, 23, 22, 35, 21], including vehicle detection and pose
estimation [23], semantic labeling and monocular depth estimation [34] as well
as HD-map extraction [21]. However, there has been a lack of literature that
exploit maps as ground-truth to build benchmarks. This is mainly due to both
the lack of high-fidelity maps to provide pixel-level annotation and the lack
of accurately georeferenced imagery that aligned well with the maps. One
exception is [35], where the streetree catalog is used to generate ground-
truth for tree detection. [36] utilizes 3D building models to generate
correspondences from multiple streetview images. In this paper, we use maps to
create multiple benchmarks for reconstruction, recognition and reorganization
from many different views of the world.

Figure 3: Road surface generation: (left) input data with curbs (yellow) and
center lines (red). Extracted road surface is the union of polygons shown in
blue and black. Note that a formulation ensuring connectivity is needed,
otherwise the road surface would contain holes at intersections.

(a) NCC: before vs. after

(b) Overlay: before vs. after

(c) Location: before vs. after

Figure 4: Ground-aerial alignment

(a) Input

(b) GT

(c) ResNet56

(d) Input

(e) GT

(f) ResNet56

Figure 5: Examples of aerial semantic segmentation, road curb extraction, and
road centerline estimation.

##  3 TorontoCity at a Glimpse

TorontoCity is an extremely large dataset enabling work on many exciting new
tasks. We first describe the data in detail. In the next section we describe
our efforts to simplify the labeling task, as otherwise it is infeasible to
create such a large-scale dataset. We then show the challenges and metrics
that will compose the benchmark. Finally, we perform a pilot study of how
current algorithms perform on most tasks, and analyze the remaining
challenges.

###  3.1 Dataset

Toronto is the largest city in Canada, and the fourth largest in North
America. The TorontoCity dataset covers the greater Toronto area (GTA), which
contains $712.5km^{2}$ of land, $8439km$ of road and around $400,000$
buildings. According to the census $6.8million$ people live in the GTA, which
is around $20\%$ of the population of Canada.

We have gathered a wide range of views of the city: from the overhead
perspective, we have aerial images captured during four different years
(containing several seasons) as well as airborne LIDAR. From the ground
perspective, we have HD panoramas as well as stereo, Velodyne LIDAR and Go-pro
data captured from a moving vehicle driving around the city. In addition, we
are augmenting the dataset with a 3D camera as well as imagery captured from
drones. Fig. 1 depicts some of the data sources that compose our dataset. We
now describe the data in more details and refer the reader to Fig. 2 for a
comparison against existing datasets.

(a) Input

(b) GT

(c) ResNet56

(d) Input

(e) GT

(f) ResNet56

Figure 6: Examples of building instance segmentation.

#### Panoramas:

We downloaded Google Streetview panoramas [2] that densely populate the GTA.
On average, we crawled around 520 full $360^{\circ}$ spherical panoramas for
each $km^{2}$. In addition, we crawled the associated metadata, including the
geolocation, address and the parameters of the spherical projection, including
pitch, yaw and tilt angles. We resized all panoramas to $3200\times 1600$
pixels.

#### Aerial Imagery:

We use aerial images with full coverage of the GTA taken in 2009, 2011, 2012
and 2013. They are orthorectified to $10cm$/pixel resolution for 2009 and
2011, and $5$ and $8cm$/pixel for 2012 and 2013 respectively. This contrasts
satellite images, which are at best $50cm$/pixel. Our aerial images have four
channels (i.e., RGB and Near infrared), and are 16 bit resolution for 2011 and
8 bit for the rest. As is common practice in remote sensing [4], we projected
each image to the Universal Transverse Mercator (UTM) 17 zone in the WGS84
geodetic datum and tiled the area to $500\times 500m^{2}$ images without
overlap. Note that the images are not true orthophotos and thus facades are
visible.

#### Airborne LIDAR:

We also exploit airborne LIDAR data captured in 2008 with a Leica ALS sensor
with a resolution of 6.8 points per $m^{2}$. The total coverage is 22
$km^{2}$. All of the points are also geo-referenced and projected to the UTM17
Zone in WGS84 geodetic datum.

#### Car setting:

Our recording platform includes a GoPro Hero 4 RGB camera, a Velodyne HDL-64E
LIDAR and a PointGray Bumblebee3 Stereo Camera mounted on top of the vehicle.
All the sensors are calibrated and synchronized with a Applanix POS LV
positioning system to record real-time geo-location and orientation
information. We have driven this platform for around 90km, which includes
repeats of the same area. Note that we are collecting and aligning new data
from ground-view vehicles, and plan to have a much larger coverage by the time
of release.

###  3.2 Maps as Annotations

Manually labeling such a large scale dataset as TorontoCity is simply not
possible. Instead, in this paper we exploit different sources of high-
precision maps covering the whole GTA to create our ground truth. Compared to
online map services such as OpenStreetMap [1] and Google Maps, our maps are
much more accurate. Furthermore, they contain many additional sources of
detailed meta data which we exploit. One of the main challenges in creating
TorontoCity was the alignment of the maps to all data sources. In the
following, we first describe the annotated data composing TorontoCity and
postpone our discussion on the algorithms we developed to align all data
sources to the next section.

#### Buildings:

The TorontoCity dataset contains $400,000$ 3D buildings covering the full GTA.
As shown in Fig. 2, the buildings are very diverse, with the tallest being the
CN Tower with 443m of elevation. Toronto contains many individual family
houses, which makes tasks such as instance level segmentation particularly
difficult. The mean height of each building is 4.7m, and the mean building
area is $148m^{2}$. In contrast, the largest building has an area
$120,000m^{2}$. The level of detail of the 3D models varies per building (see
Fig. 1). Many of these buildings are accurate to within centimeters and
contain many other semantic primitives such as roof types, windows and
balconies.

#### Roads:

Our maps contain very accurate polylines representing streets, sidewalks,
rivers and railways within the GTA. Each line segment is described with a
series of attributes such as name, road category and address number range.
Road intersections are explicitly encoded as intersecting points between
polylines. Road curbs are also available, and describe the shape of roads (see
Fig. 1).

#### Urban Zoning:

Our maps contain government zoning information on the division of land into
categories. This zoning includes categories such as residential, commercial,
industrial and institutional. Note that multiple categories are allowed for
one zone, e.g., commercial+residential. Understanding urban zoning is
important in applications such as urban planning, real estate and law-
enforcement.

#### Additional data:

We also have cartographic information with full coverage of the GTA. For
instance, we have the location of all the poles, traffic lights, street lights
and street trees with meta-information for each. The meta-information includes
the height of the pole/traffic light, type of model of each street lights,
trunk radius and species of each trees. We plan to exploit this in the near
future.

Figure 7: Qualitative results on building structured contour prediction:
ResNet vs  GT

##  4 Maps for Creating Large Scale Benchmarks

In this section we describe our algorithms to automatically align maps with
our sources of imagery. We then describe the alignment of the different road
maps.

###  4.1 Aligning Maps with All Data Sources

The aerial images we employed are already perfectly aligned with the maps.
This, however, is not the case for the panoramas. As noted in [7], the
geolocalizaiton error is up to $5m$ with an average of $1.5m$, while rotation
is very accurate. As a consequence, projecting our maps will not generate good
ground truth due to the large misalignments as shown in Fig. 4. To handle this
issue, we design an alignment algorithm that exploits both aerial images and
maps. Their information is complementary, as aerial images give us appearance,
while maps give us sparse structures (e.g., road curves).

For this, we first rectify the panoramas by projecting them onto the ground-
plane. We extract a $400\times 400$ m ground plane region with $10$cm/pixel
resolution and parameterize the alignment with three degrees of freedom
representing the camera’s offset. We then perform a two step alignment
process. We obtain a coarse alignment by maximizing a scoring function that
compromises between appearance matching and a regularizer. In particular, we
use normalized cross correlation (NCC) as our appearance matching term and a
Gaussian prior with mean $(0,0,2.5)m$ and diagonal covariance $(2,2,0.2)m$. We
re-scale both aerial and ground images to $[0,1]$ before NCC. The solution
space is a discrete search window in the range
$[-10m,10m]\times[-10m,10m]\times[2.2m,2.6m]$ with a step of $0.1m$. We use
exhaustive search to perform this search, and exploit the fact that NCC can be
computed efficiently using FFT and the Gaussian prior score is a fixed look-
up-table. As shown in Fig. 4 this procedure produces very good coarse
alignments. The alignment is coarse as we reason at the aerial images’
resolution, which is relatively lower.

Our fine alignment then utilizes the road curves and aligns them to the
boundary edges [10] in the panorama. We use a search area of
$[-1m,1m]\times[-1m,1m]$ with a step of 5cm. This is followed by a human
verification process that selects the images where this alignment succeeds.
Mistakes in the alignment are due to occlusions (e.g., cars in the panoramas)
as well as significant non-flat terrain. Our success rate is 34.35%, and it
takes less than 2s to verify an image. In contrast annotating the alignment
takes 20s.

Figure 8: Examples of road segmentation. Left: panoramic view; right: top-down view. (TP:  yellow, FP:  red, FN:  green) Method | Mean | Building | Road
---|---|---|---
FCN [19] | 77.64% | 70.44% | 73.32%
ResNet [14] | 78.46% | 69.15% | 76.44%
Table 1: Aerial image semantic segmentation IoU.  Method | WeightedCov | AP | Re-50% | Pr-50%
---|---|---|---|---
FCN | 39.74% | 8.04% | 19.64% | 18.38%
FCN + Open | 43.19% | 16.45% | 24.55% | 36.09%
ResNet | 38.70% | 10.47% | 21.30% | 21.93%
ResNet + Open | 41.10% | 22.92% | 22.78% | 43.78%
Table 2: Building instance segmentation IoU.

###  4.2 Semantic Segmentation from Polyline Data

Our maps provide two types of road structures: curbs defining the road
boundaries as well as center lines defining the connectivity (adjacency) in
the street network. Unfortunately, these two sources are not aligned, and
occasionally center lines are outside the road area. In this section we show
our procedure of exploiting a Markov random field (MRF) to align road
centerlines and curves. We can then generate the polygons describing the road
surfaces. Fig. 3 shows an example for the road surface generation.

Let $y_{i}\in\\{0,1,\cdots,k\\}$ be the assignment of the $i$-th curb segment
to one of the $k$ nearest centerline segments, where state $0$ denotes no
match. We define an MRF composed of unary and pairwise terms, which connects
only adjacent curbs segments, and thus naturally form a set of chains. For the
unary terms $\phi_{un}(y_{i})$, we use the weighted sum of the distance of the
curve to each centerline segment (condition on the state) and the angular
distance between curves and centerlines. For the pairwise terms
$\phi_{con}(y_{i},y_{i+1})$, we employ a Potts potential that encourages
smoothness along the road. This is important as otherwise there may be holes
in places such as intersections, since the center of the intersection is
further away from other points. Due to the chain structure of the graphical
model, inference can be done exactly and efficiently in parallel for each
chain using dynamic programming. Our formulation allows for multiple curbs to
be matched to one road, which is needed as there are curbs on both sides of
the centerline. We manually inspect the results and mark errors as “don’t
care” regions. We convert each continuous curb-road center line assignment to
polygons which gives us the final road surface. We refer the reader to Fig. 3
for an example.

| Road centerline | Road curb
---|---|---
Method |  F10.5 |  Pr0.5 |  Re0.5 |  F12 |  Pr2 |  Re2 |  F10.5 |  Pr0.5 |  Re0.5 |  F12 |  Pr2 |  Re2
FCN | 0.169 | 0.156 | 0.186 | 0.626 | 0.576 | 0.687 | 0.444 | 0.413 | 0.482 | 0.778 | 0.726 | 0.837
FCN+Close | 0.173 | 0.164 | 0.183 | 0.639 | 0.604 | 0.678 | 0.444 | 0.427 | 0.462 | 0.781 | 0.752 | 0.812
ResNet | 0.162 | 0.143 | 0.186 | 0.613 | 0.567 | 0.667 | 0.575 | 0.585 | 0.566 | 0.796 | 0.830 | 0.765
ResNet+Close | 0.162 | 0.169 | 0.155 | 0.644 | 0.671 | 0.619 | 0.568 | 0.614 | 0.529 | 0.799 | 0.862 | 0.745
Table 3: Road centerline and curb results. Metric: F1, Precision, Recall with
minimal distance threshold 0.5m and 2m.

##  5 Benchmark Tasks and Metrics

We designed a diverse set of benchmarks to push computer vision approaches to
reason about geometry, semantics and grouping. To our knowledge, no previous
dataset is able to do this at this scale. In the evaluation server,
participants can submit results using any subset of the imagery types provided
in the benchmark (e.g., aerial images, panoramas, Go-Pro, stereo). In this
section, we briefly describe the tasks and metrics, and refer the reader to
the supplementary material for further details. Note also that Fig. 1 shows an
illustration of some of our tasks.

#### Building Footprint and Road segmentation:

Our first task is semantic segmentation of building footprints and roads.
Following common practice in semantic segmentation, we utilize mean
Intersection-Over-Union (mIOU) as our metric. This is evaluated from a top-
down view.

#### Building Footprint Instance Segmentation:

Our second task is building instance segmentation. We adopt multiple metrics
for this task, since there is no consensus in the community of what is the
best metric. We thus evaluate weighted coverage (Cov), average precision (AP)
as well as instance level precision and recall at $50\%$.

#### Building Structured Contours:

Most semantic and instance segmentation algorithms produce ”blob”-like
results, which do not follow the geometry of the roads and/or buildings. We
thus want to push the community to produce instance segmentations that follow
the structure of the primitives. Towards this goal, we define a metric that
merges (in a multiplicative fashion) segmentation scoring with geometric
similarity. In particular, segmentation is measured in terms of IOU, and we
exploit the similarity between the turning functions of the estimated and
ground truth polygons as a geometric metric. We refer the reader to the
supplementary material for more details.

#### Road Topology:

One of the remaining fundamental challenges in mapping is estimating road
topology. In this task, participants are asked to extract polylines that
represent road curbs and road centerlines in bird’s eye perspective. We
discretize both estimated and ground truth polylines in intervals of size
$10$cm. We define precision and recall as our metrics, where an estimated
segment is correct if its distance to the closest segment on the target
polyline set is smaller than a threshold (i.e., 0.5m and 2.0m).

Method |  AlexNet [16] |  VGG-16 [32] |  GoogleNet [33] |  ResNet-152 [14] |  AlexNet [16] |  ResNet-32 [14] |  GoogleNet [33] |  NiN [17]
---|---|---|---|---|---|---|---|---
From-scratch | no | no | no | no | yes | yes | yes | yes
Top-1 accuracy | 75.49% | 79.12% | 77.95% | 79.33% | 66.48% | 75.65% | 75.08% | 79.07%
Table 4:  Ground-Level Urban Zoning Classification

#### Ground Road Segmentation:

We use IOU as our metric.

#### Ground Urban Zoning Classification:

This benchmark is motivated by the human’s ability to recognize the urban
function of a local region by its appearance. We use Top-1 accuracy as our
metric and evaluate on the ground view.

#### Urban Zoning Segmentation:

Our goal is to produce a segmentation in bird’s eye view of the different
urban zones including residential, commercial, open space, employment, _etc_.
We utilize IOU as our metric.

#### Building Height Estimation:

This tasks consists on estimating building height. Useful cues include size of
the buildings, pattern of shading and shadows as well as the imperfect
rectification in aerial views. We adopt root mean square error in the log
domain (log-RMSE) as our metric.

#### Additional Tasks:

We plan to add many tasks in the coming months. This includes detecting trees
and recognizing their species. Moreover, the accurate 3D building models allow
us to build a benchmark of normal estimation as well as facade parsing. We
also plan to have benchmarks for detection and segmentation of traffic lights,
traffic signs and poles. We are just scratching the surface of the plenthora
of possibilities with this dataset.

##  6 Experimental Evaluation

Method | WeightedCov | PolySim
---|---|---
FCN | 0.456 | 0.323
ResNet | 0.401 | 0.292
Table 5: Building contour results.  Method | Residential | Open Space | Others
---|---|---|---
FCN | 60.20% | 32.20% | 5.57%
ResNet | 51.71% | 33.63% | 1.49%
Table 6: Qualitative results for urban zoning segmentation.

We perform a pilot study of the difficulty of our tasks in a subset of
TorontoCity, containing 125 $km^{2}$ region (50 $km^{2}$ for training, 50
$km^{2}$ for testing and $25km^{2}$ for validation). The train/val/test
regions do not overlap and are not adjacent. We utilize 56K streetview images
around these regions (22K for training, 18K for validation and 16K for
testing). Hyper-parameters are chosen based on validation performance, and all
numbers reported are on the testing set.

To perform the different segmentation related tasks, we train two types of
convolutional networks: a variant of FCN-8 architecture [19] as well as a
ResNet [14] with 56 convolutional layers. More details are in supp. material.

#### Semantic Segmentation:

As shown in Tab. 1, both networks perform well. Fig. 5 illustrates qualitative
results of ResNet56 output. It is worth noting that large networks such as
ResNet56 can be trained from scratch given our large-scale dataset. Visually
ResNet’s output tends to be more sharp, while FCN’s output is more smooth.

#### Instance Segmentation:

We estimate instance segmentation by taking the output of the semantic
labeling and performing connected-component labeling. Each component is
assigned a different label. Since convolutional nets tend to generate blob
like structures, a single component might contain multiple instances connected
with a small number of pixels. To alleviate this problem, we apply
morphological opening operators over the semantic labeling masks (an erosion
filtering followed by a dilation filtering with the same size). As shown in
Tab. 2 and Fig. 6 the performance is low. There is still much for the
community to do to solve this task. With more than $400,000$ buildings, the
TorontoCity dataset provides an ideal platform for new developments.

#### Road Centerlines and Curbs:

We compute the medial axis of the semantic segmentation to extract the
skeleton of the mask as our estimate of road centerline. In order to smooth
the skeletonization, we first conduct a morphological closing operator
(dilation followed by erosion) over the road masks. To estimate road curbs, we
simply extract the contours of the road segmentation and exploit closing
operator. As shown in Table. 1, ResNet achieves the highest score in both
tasks, and morphological filtering helps for both networks. Qualitative
results are shown in Fig. 5. Note that there is still much room for
improvement.

#### Building Contours:

We compute building contours from our estimated building instances, and apply
the Ramer-Douglas-Peucker algorithm [27] to simplify each polygon with a
threshold of $0.5$m. This results in polygons with 13 vertices on average. As
shown in Tab. 5 and Fig. 7, this simple procedure offers reasonable yet not
satisfactory resulst. This suggests there is still a large improvement space
for generating building polygons from aerial images.

#### Ground Urban Zoning Classification:

We train multiple state-of-the-art convolutional networks for this task
including AlexNet [16], VGG-16 [32], GoogleNet [33] and ResNet-152 [14] that
are fine-tuned from the ImageNet benchmark [9]. We also train AlexNet [16],
ResNet-32 [14], Network-In-Network [17] and ResNet-152 [14] from scratch over
our ground-view panoramic image tiles. As shown in Table. 1 ResNet-152 with
pre-trained initialization achieves the best results. Net-in-net achieves the
best performance among all models that are trained from scratch. For more
details, please refer to the supplementary material.

#### Urban Zoning Segmentation:

This is an extremely hard task from aerial views alone. To simplify it, we
merged the zone-types into residential, others (including commercial, utility
and employment) as well as open spaces (including natural, park, recreational
_etc_.). Please refer to the supplementary material for detailed label
merging. As shown in Tab. 6 more research is needed to solve this task.

#### Ground-view road segmentation:

We utilize a subset of the labeled panoramas, which includes 1000 training,
200 validation and 800 testing images. The average IOU is $97.21\%$. The
average pixel accuracy is $98.64\%$ and average top-down IOU is $87.53\%$.
This shows that a state-of-the-art neural network can nearly solve this task,
suggesting that it is promising to automatically generate high-resolution maps
by capturing geo-referenced street-view panoramas.

#### Building Height:

No network was able to estimate building height from aerial images alone. This
task is either too hard, or more sophisticated methods are needed. For
example, utilizing ground imagery seems a logical first step.

##  7 Conclusions

In this paper, we have argued that the field is in need of large scale
benchmarks that will allow joint reasoning about geometry, grouping and
semantics. Towards this goal, we have created the TorontoCity benchmark,
covering the full Greater Toronto area (GTA) with $712.5km^{2}$ of land,
$8439km$ of road and around $400,000$ buildings. Unlike existing datasets, our
benchmark provides a wide variety of views of the world captured from
airplanes, drones, as well as cars driving around the city. As using human
annotators is not feasible for such a large-scale dataset, we have exploited
different sources of high-precision maps to create our ground truth. We have
designed a wide variety of tasks including building height estimation, road
centerline and curb extraction, building instance segmentation, building
contour extraction (reorganization), semantic labeling and scene type
classification (recognition). Our pilot study shows that most of these tasks
are still difficult for modern convolutional networks. We plan to extend the
current set of benchmarks with tasks such as building reconstruction, facade
parsing, tree detection, tree species categorization, traffic light detection,
and traffic sign detection. This is only the beginning of the exciting
TorontoCity benchmark.

## References

  * [1] Openstreetmap.  https://www.openstreetmap.org/.
  * [2] D. Anguelov, C. Dulong, D. Filip, C. Frueh, S. Lafon, R. Lyon, A. Ogale, L. Vincent, and J. Weaver.  Google street view: Capturing the world at street level.  IEEE Computer, 2010.
  * [3] S. Baker, D. Scharstein, J. Lewis, S. Roth, M. J. Black, and R. Szeliski.  A database and evaluation methodology for optical flow.  IJCV, 2011.
  * [4] W. Brooks.  The universal transverse mercator grid.  In Proceedings of the Indiana Academy of Science, 1973.
  * [5] D. J. Butler, J. Wulff, G. B. Stanley, and M. J. Black.  A naturalistic open source movie for optical flow evaluation.  In ECCV, 2012.
  * [6] C. Chen, A. Seff, A. Kornhauser, and J. Xiao.  Deepdriving: Learning affordance for direct perception in autonomous driving.  In ICCV, 2015.
  * [7] H. Chu, S. Wang, R. Urtasun, and S. Fidler.  Housecraft: Building houses from rental ads and street views.  In ECCV, 2016.
  * [8] M. Cordts, M. Omran, S. Ramos, T. Rehfeld, M. Enzweiler, R. Benenson, U. Franke, S. Roth, and B. Schiele.  The cityscapes dataset for semantic urban scene understanding.  In CVPR, 2016.
  * [9] J. Deng, W. Dong, R. Socher, L.-J. Li, K. Li, and L. Fei-Fei.  Imagenet: A large-scale hierarchical image database.  In CVPR, 2009.
  * [10] P. Dollár and C. L. Zitnick.  Structured forests for fast edge detection.  In ICCV, 2013.
  * [11] M. Everingham, L. Van Gool, C. K. Williams, J. Winn, and A. Zisserman.  The pascal visual object classes (voc) challenge.  IJCV, 2010.
  * [12] A. Geiger, P. Lenz, and R. Urtasun.  Are we ready for autonomous driving? the kitti vision benchmark suite.  In CVPR, 2012.
  * [13] A. Handa, V. Patraucean, V. Badrinarayanan, S. Stent, and R. Cipolla.  Scenenet: Understanding real world indoor scenes with synthetic data.  arXiv, 2015.
  * [14] K. He, X. Zhang, S. Ren, and J. Sun.  Deep residual learning for image recognition.  CVPR, 2016.
  * [15] T. Koch, P. d’Angelo, F. Kurz, F. Fraundorfer, P. Reinartz, and M. Korner.  The tum-dlr multimodal earth observation evaluation benchmark.  In CVPRW, 2016.
  * [16] A. Krizhevsky, I. Sutskever, and G. E. Hinton.  Imagenet classification with deep convolutional neural networks.  In NIPS, 2012.
  * [17] M. Lin, Q. Chen, and S. Yan.  Network in network.  ICLR, 2014.
  * [18] T.-Y. Lin, M. Maire, S. Belongie, J. Hays, P. Perona, D. Ramanan, P. Dollár, and C. L. Zitnick.  Microsoft coco: Common objects in context.  In ECCV, 2014.
  * [19] J. Long, E. Shelhamer, and T. Darrell.  Fully convolutional networks for semantic segmentation.  In CVPR, 2015.
  * [20] W. Maddern, G. Pascoe, C. Linegar, and P. Newman.  1 year, 1000km: The oxford robotcar dataset.  IJRR, 2016.
  * [21] G. Máttyus, S. Wang, S. Fidler, and R. Urtasun.  Enhancing road maps by parsing aerial images around the world.  In ICCV, 2015.
  * [22] G. Máttyus, S. Wang, S. Fidler, and R. Urtasun.  Hd maps: Fine-grained road segmentation by parsing ground and aerial images.  In CVPR, 2016.
  * [23] K. Matzen and N. Snavely.  Nyc3dcars: A dataset of 3d vehicles in geographic context.  In ICCV, 2013.
  * [24] F. Nex, M. Gerke, F. Remondino, H. Przybilla, M. Bäumker, and A. Zurhorst.  Isprs benchmark for multi-platform photogrammetry.  ISPRS Annals of the Photogrammetry, Remote Sensing and Spatial Information Sciences, 2015.
  * [25] J. Niemeyer, F. Rottensteiner, and U. Soergel.  Contextual classification of lidar data and building object detection in urban areas.  ISPRS journal of photogrammetry and remote sensing, 2014.
  * [26] N.Mayer, E.Ilg, P.Häusser, P.Fischer, D.Cremers, A.Dosovitskiy, and T.Brox.  A large dataset to train convolutional networks for disparity, optical flow, and scene flow estimation.  In CVPR, 2016.
  * [27] U. Ramer.  An iterative procedure for the polygonal approximation of plane curves.  Computer graphics and image processing, 1972.
  * [28] S. R. Richter, V. Vineet, S. Roth, and V. Koltun.  Playing for data: Ground truth from computer games.  In ECCV, 2016.
  * [29] G. Ros, L. Sellart, J. Materzynska, D. Vazquez, and A. M. Lopez.  The synthia dataset: A large collection of synthetic images for semantic segmentation of urban scenes.  In CVPR, 2016.
  * [30] F. Rottensteiner, G. Sohn, M. Gerke, and J. D. Wegner.  Isprs test project on urban classification and 3d building reconstruction.  2013\.
  * [31] A. Shafaei, J. J. Little, and M. Schmidt.  Play and learn: using video games to train computer vision models.  arXiv, 2016.
  * [32] K. Simonyan and A. Zisserman.  Very deep convolutional networks for large-scale image recognition.  arXiv, 2014.
  * [33] C. Szegedy, W. Liu, Y. Jia, P. Sermanet, S. Reed, D. Anguelov, D. Erhan, V. Vanhoucke, and A. Rabinovich.  Going deeper with convolutions.  In CVPR, 2015.
  * [34] S. Wang, S. Fidler, and R. Urtasun.  Holistic 3d scene understanding from a single geo-tagged image.  In CVPR, 2015.
  * [35] J. D. Wegner, S. Branson, D. Hall, K. Schindler, and P. Perona.  Cataloging public objects using aerial and street-level images-urban trees.  In CVPR, 2016.
  * [36] A. R. Zamir, T. Wekel, P. Agrawal, C. Wei, J. Malik, and S. Savarese.  Generic 3d representation via pose estimation and matching.  In ECCV, 2016.


# Stabilizers of consistent walks

Maruša Lekše  Faculty of Mathematics and Physics, University of Ljubljana,
Slovenia;
Institute of Mathematics, Physics, and Mechanics, Ljubljana, Slovenia
<EMAIL_ADDRESS>
###### Abstract.

A walk of length $n$ in a graph is consistent if there exists an automorphism
of the graph that maps the initial $n-1$ vertices to the final $n-1$ vertices
of the walk. In this paper we find some sufficient conditions for a consistent
walk in an arc-transitive graph to have a trivial pointwise stabilizer. We
show that in that case, the size of the smallest generating set of the group
is bounded by the valence of the graph.

###### Key words and phrases:

Consistent walk, stabilizer, weakly $p$-subregular, number of generators

###### 2020 Mathematics Subject Classification:

05E18, 05C25.

The work was supported by Javna agencija za znanstvenoraziskovalno in
inovacijsko dejavnost Republike Slovenije (ARIS), research program P1-0294.

##  1\. Introduction

For a graph $\Gamma$ and a group $G\leq\text{{\rm Aut}}(\Gamma)$, we say that
a walk $(v_{0},v_{1},\ldots,v_{n})$ of length $n\geq 1$ is _$G$ -consistent_
if there exists an automorphism $g\in G$ (called a _shunt_ for the walk) such
that $v_{i}^{g}=v_{i+1}$ for all $i\in\\{0,\ldots,n-1\\}$.

Consistent walks play a prominent role in algebraic graph theory and feature
already in the seminal work of Tutte [16, 17] on cubic arc-transitive graphs,
where he proved that the order of a vertex stabilizer $G_{v}$ in a $G$-arc-
transitive $3$-valent graph is bounded from above by the constant $48$. In his
proof, he considered the largest value of $s$ such that $G$ acts transitively
on the set of all $s$-arcs of $\Gamma$ (observe that then every $s$-arc is a
$G$-consistent walk). Tutte’s proof consists of two parts:

  1. (i)

show that the stabilizer of an $s$-arc is trivial,

  2. (ii)

show that $s$ is bounded by $5$.

Bounding the order of a vertex-stabilizer in highly symmetric graphs has
become a classical theme in algebraic graph theory, see [13, 12, 14, 15, 18,
19, 20]. In this paper, we will be interested in generalizations of part (i)
of Tutte’s approach. In particular, we will be interested in circumstances in
which we can guarantee the existence of a $G$-consistent walk with a trivial
stabilizer. We will focus on the conditions imposed on the _local group_
$G_{v}^{\Gamma(v)}$, that is, the permutation group induced by the action of a
vertex stabilizer on the neighborhood of that vertex. As a consequence of a
technical result, Lemma 3.6 proved in Section 3, the following two results are
obtained: if $\Gamma$ is a $G$-arc-transitive graph and either its valence is
at most $4$, or the local group $G_{v}^{\Gamma(v)}$ is a weakly $p$-subregular
group, then there exists a $G$-consistent walk with a trivial stabilizer (see
Definition 4.1 in Section 4). In Section 6 we find examples of graphs in which
no $G$-consistent walk has a trivial stabilizer.

Finally, in Section 7, we use the techniques and results developed in this
paper to address a question raised by Marco Barbieri and Pablo Spiga in [3].
Indeed, [3, Problem 4] asks under which additional assumptions one can
guarantee existence of a function $f(d)$ such that every vertex-transitive
group of automorphisms of a finite $d$-valent graph can be generated by $f(d)$
generators. As a partial answer to this question, we show that whenever a
vertex-transitive group $G$ of automorphisms of a finite $d$-valent graph
$\Gamma$ is such that there exists a $G$-consistent walk with a trivial
stabilizer in $G$, the size of the smallest generating set of $G$ is bounded
from above by the valence of $\Gamma$ (see Corollary 7.4 for a detailed
statement). In particular, this implies that the assumption of having weakly
$p$-subregular local group implies that $G$ is $3$-generated.

##  2\. Preliminaries

Throughout this paper, $\Gamma$ is a finite simple graph with at least three
vertices, unless otherwise stated. We say that two vertices $u,v\in V(\Gamma)$
are _twin vertices_ , if $\Gamma(u)=\Gamma(v)$, where $\Gamma(u)$ denotes the
neighborhood of a vertex $u$ in $V(\Gamma)$. In what follows let $n$ be a
positive integer and let $\alpha=(v_{0},\ldots,v_{n})$ be a $(n+1)$-tuple of
vertices of $\Gamma$ such that any two consecutive vertices are adjacent in
$\Gamma$; in this case we say that $\alpha$ is a _walk_ of length $n$. If any
three consecutive vertices in $\alpha$ are pairwise distinct we say that
$\alpha$ is a _$n$ -arc_ (or simply an _arc_ when $n=1$). If $v_{0}=v_{n}$ we
say that $\alpha$ is _closed_ and if in addition any two vertices in
$\\{v_{0},\ldots,v_{n-1}\\}$ are distinct, then $\alpha$ is a _cycle_. Note
that there are no cycles of length $1$, and that every arc $(u,v)$ of length
$2$ yields a cycle $(u,v,u)$ of length $2$; we will refer to cycles of length
$2$ as _trivial_. Note that contrary to the usual definition, all cycles in
this paper are directed and rooted (that is, they have a designated initial
vertex). Finally if $n\geq 1$ we let $\hat{\alpha}=(v_{0},\ldots,v_{n-1})$.

Let $G\leq\text{{\rm Aut}}(\Gamma)$. We say that $G$ is _vertex-transitive_
(or that $\Gamma$ is $G$-vertex-transitive) if it acts transitively on the set
$V(\Gamma)$, that $G$ is _arc-transitive_ (or that $\Gamma$ is $G$-arc-
transitive) if it acts transitively on the set of all arcs in $\Gamma$ and
that that $G$ is _n-arc-transitive_ (or that $\Gamma$ is $(G,n)$-arc-
transitive) if it acts transitively on the set of all $n$-arcs in $\Gamma$.
Recall that a walk $\alpha=(v_{0},\ldots,v_{n})$ is $G$-consistent with a
shunt $g\in G$ whenever $(v_{0},\ldots,v_{n-1})^{g}=(v_{1},\ldots,v_{n})$
(when $G=\text{{\rm Aut}}(\Gamma)$ we will omit $G$ and say that $\alpha$ is
consistent). The set of all shunts of $\alpha$ will be denoted by $\text{{\rm
Sh}}_{G}(\alpha)$. Observe that if $\alpha$ is a $G$-consistent walk of length
at least $2$, then also $\hat{\alpha}$ is $G$-consistent and $\text{{\rm
Sh}}_{G}(\alpha)\subseteq\text{{\rm Sh}}_{G}(\hat{\alpha})$.

If $\alpha$ is $G$-consistent with a shunt $g$, then $\alpha^{x}$ is
$G$-consistent with a shunt $g^{x}$ for every $x\in G$. Note that this action
preserves the set of $G$-consistent cycles in $\Gamma$. As was pointed out by
J. H. Conway in [4], the number of $G$-orbits on the set of $G$-consistent
cycles in a $G$-arc transitive graph is equal to the valence of $\Gamma$. The
following generalization to vertex-transitive graphs was proved in [10]. (For
further results and applications on consistent cycles, see [2, 5, 9, 10, 11])

######  Theorem 2.1 ([10, Theorem 5.1]).

Let $G$ be a vertex transitive group of automorphisms of a $d$-valent graph
$\Gamma$. Then $G$ has precisely $d$ orbits in its action on the set of
$G$-consistent cycles of $\Gamma$.

The following results are easy to prove and were either proved or mentioned in
[10]. We list them here for the convenience of the reader.

######  Definition 2.2.

Let $\Gamma$ be a graph and let $G\leq\text{{\rm Aut}}(\Gamma)$. For $n\geq 1$
we say that a walk $\beta=(v_{1},\ldots,v_{n},v_{n+1})$ is a $G$-successor of
a walk $\alpha=(v_{0},\ldots,v_{n})$ provided that there exists an
automorphism $\sigma\in\text{{\rm Sh}}_{G}(\alpha)$ such that
$v_{n}^{g}=v_{n+1}$. We denote the set of all $G$-successors of the walk
$\alpha$ with $\text{{\rm Succ}}_{G}(\alpha)$.

######  Lemma 2.3.

Let $\Gamma$ be a graph, let $G\leq\text{{\rm Aut}}(\Gamma)$ and let
$\alpha=(v_{0},\ldots,v_{n})$ be a $G$-consistent walk with a shunt
$g\in\text{{\rm Sh}}_{G}(\alpha)$. Then $gG_{(v_{1},\ldots,v_{n})}=\text{{\rm
Sh}}_{G}(\alpha)=G_{(v_{0},\ldots,v_{n-1})}g$.

######  Lemma 2.4.

Let $\Gamma$ be a graph, let $G\leq\text{{\rm Aut}}(\Gamma)$, let
$\alpha=(v_{0},\ldots,v_{n})$ be a $G$-consistent walk with a shunt
$g\in\text{{\rm Sh}}_{G}(\alpha)$ and let $v_{n+1}=v_{n}^{g}$. Then the walk
$\beta=\alpha^{g}=(v_{1},\ldots,v_{n+1})$ is also $G$-consistent with a shunt
$g$ and

$\displaystyle\text{{\rm Succ}}_{G}({\alpha})$
$\displaystyle={\alpha}^{\text{{\rm Sh}}_{G}({\alpha})}$
$\displaystyle=\beta^{G_{(v_{1},\ldots,v_{n})}}.$

######  Lemma 2.5.

Let $\Gamma$ be a graph, let $G$ be a vertex-transitive subgroup of
$\text{{\rm Aut}}(\Gamma)$, and let $\alpha=(v_{0},\ldots,v_{n})$ be a
$G$-consistent walk. Then $|G_{\hat{\alpha}}|=|G_{\alpha}||\text{{\rm
Succ}}_{G}({\alpha})|$.

###### Proof.

Take $g\in\text{{\rm Sh}}_{G}(\alpha)$ and let $v_{n+1}=v_{n}^{g}$. Now
observe that

$|\alpha^{G_{\hat{\alpha}}}|=|\alpha^{g(G_{\hat{\alpha}})^{g}g^{-1}}|=|(v_{1},\ldots,v_{n+1})^{G_{(v_{1},\ldots,v_{n})}g^{-1}}|=|(v_{1},\ldots,v_{n+1})^{G_{(v_{1},\ldots,v_{n})}}|=|\text{{\rm
Succ}}_{G}({\alpha})|,$

by Lemma 2.4. Since the stabilizer of $\alpha$ in $G_{\hat{\alpha}}$ is
$G_{\alpha}$, the result follows from the Orbit-Stabilizer Lemma. ∎

##  3\. Some conditions for a $G$-consistent walk to have a trivial stabilizer

######  Definition 3.1.

Let $\Gamma$ be a graph and let $G\leq\text{{\rm Aut}}(\Gamma)$. Fix a
$G$-consistent walk $\alpha=(v_{0},\ldots,v_{n})$ of length $n\geq 2$. For two
walks $\beta=(b_{0},\ldots,b_{n-1}),\
\gamma=(c_{0},\ldots,c_{n-1})\in\hat{\alpha}^{G}$ we write
$\beta\sim_{\alpha}\gamma$ with respect to $G$ provided that there exists a
sequence of walks $\beta_{0},\ldots,\beta_{m}\in\alpha^{G}$ such that
$\hat{\beta_{0}}=\beta,\ \hat{\beta_{m}}=\gamma$ and that for every
$i\in\\{0,\ldots,m-1\\}$ the walk $\beta_{i+1}$ is a $G$-successor of the walk
$\beta_{i}$.

We will just say that $\beta\sim_{\alpha}\gamma$ and omit $G$ when $G$ is
clear from context. The next result appears without proof in [18], we will
prove it here for the convenience of the reader. The rest of the results in
this section are also inspired by [18].

######  Lemma 3.2.

Let $G$ be a finite group that acts transitively on a set $X$. If $R$ is a
transitive nonempty binary relation on the set $X$ that is preserved by $G$,
it is an equivalence relation.

###### Proof.

Let $\Gamma$ be a not neccessarily simple digraph with vertex set
$V(\Gamma)=X$ and arc set $A(\Gamma)=\\{(x,y)\mid xRy\\}$. Since the group $G$
preserves the relation $R$, it acts on the digraph $\Gamma$ as a group of
automorphisms, this action is vertex-transitive. Suppose that $R$ is not a
symmetric relation. Since $G$ is transitive, this implies that for every
vertex $u_{0}$ there exists an arc $(u_{0},u_{1})\in A(\Gamma)$, such that
$(u_{1},u_{0})\notin A(\Gamma)$. Since $X$ is finite, there exists a cycle
$(v_{0},v_{1},\ldots,v_{n},v_{0})$ in $\Gamma$, such that $(v_{i},v_{i+1})\in
A(\Gamma)$ and $(v_{i+1},v_{i})\notin A(\Gamma)$ for all
$i\in\\{0,\ldots,n\\}$, where indices are computed modulo $n$. However, by
transitivity of the relation $R$ we see that $(v_{1},v_{0})\in A(\Gamma)$,
which is a contradiction, implying that $R$ is a symmetric relation. Since
$R\neq\emptyset$, transitivity of $G$ implies that for every $u\in X$ there
exists $v\in X$ such that $uRv$. Then $vRu$, and by transitivity of $R$, also
$uRu$. This shows that $R$ is reflexive and thus an equivalence relation. ∎

######  Lemma 3.3.

Let $\Gamma$ be a graph, let $G\leq\text{{\rm Aut}}(\Gamma)$ and let
$\alpha=(v_{0},\ldots,v_{n})$ be a $G$-consistent walk. Then the relation
$\sim_{\alpha}$ is an equivalence relation.

###### Proof.

Througout this proof we will use the symbol $\sim$ to denote the relation
$\sim_{\alpha}$ defined on the set $\hat{\alpha}^{G}$. The relation is
nonempty, since $\hat{\alpha}\sim\hat{\alpha}$.

Let us now show that the relation $\sim$ is transitive. Let
$\beta,\gamma,\delta\in\hat{\alpha}^{G}$ such that $\beta\sim\gamma$ and
$\gamma\sim\delta$. Then there exist sequences of walks
$\beta_{0},\ldots,\beta_{m}$, and $\gamma_{0},\ldots,\gamma_{k}$, where
$\beta_{i},\gamma_{i}\in\alpha^{G}$, such that
$\hat{\beta_{0}}=\beta,\hat{\beta_{m}}=\gamma$,
$\hat{\gamma_{0}}=\gamma,\hat{\gamma_{k}}=\delta$, and that every walk in each
of these two sequences is a $G$-successor of the previous walk in the
sequence. If $\beta=\gamma$, then $\beta\sim\delta$. If $\beta\neq\gamma$,
then $m\geq 1$. Note that since $\hat{\gamma_{0}}=\hat{\beta_{m}}$ and since
$\gamma_{0},\ \beta_{m-1}\in\alpha^{G}$, the walk $\gamma_{0}$ is a
$G$-successor of the walk $\beta_{m-1}$. In the sequence of walks
$\beta_{0},\ldots,\beta_{m-1},\gamma_{0},\ldots,\gamma_{k}$, every walk is a
$G$-successor of the previous walk, thus $\beta\sim\delta$. This proves that
the relation $\sim$ is transitive.

Let us now prove that the relation $\sim$ is preserved by $G$. Let $g\in G$
and suppose that $\beta\sim\gamma$ for two walks
$\beta,\gamma\in\hat{\alpha}^{G}$. Let $\beta_{0},\ldots,\beta_{m}$ be the
required walk from the definition of $\sim$. Then
$\beta_{0}^{g},\ldots,\beta_{m}^{g}$ is a sequence of walks in $\alpha^{G}$
that shows that $\beta^{g}\sim\gamma^{g}$. Hence $G$ preserves the relation
$\sim$. Since $G$ acts transitively on its orbit $\hat{\alpha}^{G}$, Lemma 3.2
$\sim$ implies that $\sim$ is an equivalence relation. ∎

The following property of consistent walks will play a crucial role in the
forthcoming analysis. Intuitively a $G$-consistent walk $\alpha$ has this
property if every vertex of the graph can be reached from $\alpha$ by a
sequence of $G$-successors. Hence we shall call it _reachability property_ or
(R) for short.

######  Property (R).

Let $\Gamma$ be a graph and let $G$ be an arc-transitive subgroup of
$\text{{\rm Aut}}(\Gamma)$. We say that a $G$-consistent walk $\alpha$ has
Property (R) with respect to $G$, provided that for every $v\in V(\Gamma)$
there exists a sequence of walks $\beta_{0},\ldots,\beta_{m}$ such that
$\beta_{0}=\alpha$, the last vertex of the walk $\beta_{m}$ is $v$, and
$\beta_{i+1}\in\text{{\rm Succ}}_{G}(\beta_{i})$ for all
$i\in\\{0,\ldots,m-1\\}$.

We will again omit $G$ when it is clear from context, and just say that a walk
has Property (R).

######  Lemma 3.4.

Let $\Gamma$ be a graph, let $G\leq\text{{\rm Aut}}(\Gamma)$ and let $\alpha$
be a $G$-consistent walk. Then $\alpha$ has Property (R) with respect to $G$
if and only if the group $\langle\text{{\rm Sh}}_{G}(\alpha)\rangle$ generated
by all the shunts of $\alpha$ contained in $G$ acts transitively on
$V(\Gamma)$.

###### Proof.

Let $\alpha=(v_{0},\ldots,v_{n})$. Suppose first that $\langle\text{{\rm
Sh}}_{G}(\alpha)\rangle$ acts transitively on $V(\Gamma)$. Let $v\in
V(\Gamma)$. If $v=v_{n}$, then there is nothing to prove. Henceforth assume
$v\neq v_{n}$. By transitivity of $\langle\text{{\rm Sh}}_{G}(\alpha)\rangle$
there exists an automorphism $g=g_{1}\cdots g_{\ell}\in\langle\text{{\rm
Sh}}_{G}(\alpha)\rangle$, where $g_{i}\in\text{{\rm Sh}}_{G}(\alpha)$ for all
$i\in\\{1,\ldots,\ell\\}$, such that $v_{n}^{g}=v$. Let $\beta_{0}=\alpha$ and
for every $i\in\\{1,\ldots,\ell\\}$ recursively define
$h_{i}=g_{\ell-i+1}^{h_{1}\cdots h_{i-1}}$ and $\beta_{i}=\alpha^{h_{1}\cdots
h_{i}}$. We will prove that for every $i\in\\{1,\ldots,\ell\\}$

  1. $($a$)$

$h_{1}\cdots h_{i}=g_{\ell-i+1}\cdots g_{\ell}$,

  2. $($b$)$

$h_{i}\in\text{{\rm Sh}}_{G}(\beta_{i-1})$.

In case when $i=1$ the claims $($a$)$ and $($b$)$ follow directly from the
fact that $h_{1}=g_{\ell}\in\text{{\rm Sh}}_{G}(\alpha)=\text{{\rm
Sh}}_{G}(\beta_{0})$. Suppose that $i\geq 2$ and that $($a$)$ and $($b$)$ hold
for all smaller $i$. Then $h_{1}\cdots h_{i-1}h_{i}=h_{1}\cdots
h_{i-1}g_{\ell-i+1}^{h_{1}\cdots h_{i-1}}=g_{\ell-i+1}h_{1}\ldots
h_{i-1}=g_{\ell-i+1}g_{\ell-i+2}\cdots g_{\ell}$, so Claim $($a$)$ is true.
For any $G$-consistent walk $\gamma$ and an automorphism $f\in G$ note that
$\text{{\rm Sh}}_{G}(\gamma^{f})=\text{{\rm Sh}}_{G}(\gamma)^{f}$. Since
$g_{\ell-i+1}\in\text{{\rm Sh}}_{G}(\alpha)$ and $h_{1}\cdots h_{i-1}$ maps
$\alpha$ to $\beta_{i-1}$, it follows that $h_{i}=g_{\ell-i+1}^{h_{1}\cdots
h_{i-1}}\in\text{{\rm Sh}}_{G}(\beta_{i-1})$, which proves Claim $($b$)$. We
proved that for all $i\in\\{1,\ldots\ell\\}$ the walk
$\beta_{i}=\alpha^{h_{1}\cdots h_{i}}=\beta_{i-1}^{h_{i}}$ is a $G$-successor
of the walk $\beta_{i-1}$ and that $h_{1}\cdots h_{\ell}=g$, thus the last
vertex of the walk $\beta_{\ell}$ is $v_{n}^{h_{1}\cdots
h_{\ell}}=v_{n}^{g}=v$. Therefore $\alpha$ has Property (R).

Suppose now that the walk $\alpha$ has Property (R). Let $v\neq v_{n}$ be a
vertex in $\Gamma$. We will show that there exists $h\in\langle\text{{\rm
Sh}}_{G}(\alpha)\rangle$ such that $v_{n}^{h}=v$. Let
$\beta_{0},\ldots,\beta_{\ell}$ be a sequence of walks such that
$\beta_{0}=\alpha$, the last vertex of the walk $\beta_{\ell}$ is $v$, and
$\beta_{i}=\beta_{i-1}^{h_{i}}$; $h_{i}\in\text{{\rm Sh}}_{G}(\beta_{i-1})$
for all $i\in\\{1,\ldots,\ell\\}$. Let $h=h_{1}\cdots h_{\ell}$. Then
$v_{n}^{h}=v$. For all $i\in\\{1,\ldots,\ell\\}$ note that $\text{{\rm
Sh}}_{G}(\beta_{i})=\text{{\rm Sh}}_{G}(\beta_{i-1})^{h_{i}}$, and
$\langle\text{{\rm Sh}}_{G}(\beta_{i})\rangle=\langle\text{{\rm
Sh}}_{G}(\beta_{i-1})^{h_{i}}\rangle=\langle\text{{\rm
Sh}}_{G}(\beta_{i-1})\rangle$. Thus $\langle\text{{\rm
Sh}}_{G}(\beta_{0})\rangle=\ldots=\langle\text{{\rm
Sh}}_{G}(\beta_{\ell})\rangle$. It now follows that $h\in\langle\text{{\rm
Sh}}_{G}(\beta_{0})\rangle=\langle\text{{\rm Sh}}_{G}(\alpha)\rangle$, hence
the group $\langle\text{{\rm Sh}}_{G}(\alpha)\rangle$ is vertex-transitive. ∎

######  Remark 3.5.

Observe that by Lemma 2.3, $\langle\text{{\rm Sh}}_{G}(\alpha)\rangle=\langle
G_{\hat{\alpha}},g\rangle$, where $g$ is an arbitrary element of $\text{{\rm
Sh}}_{G}(\alpha)$. Therefore the lemma above is equivalent to saying that for
a consistent cycle $\alpha$ with a shunt $g\in G$, the group $\langle
G_{\hat{a}},g\rangle$ is transitive on $V(\Gamma)$ if and only if $\alpha$ has
Property (R).

######  Lemma 3.6.

Let $\Gamma$ be a graph, let $G\leq\text{{\rm Aut}}(\Gamma)$ and let
$\alpha=(v_{0},\ldots,v_{n})$ be a $G$-consistent walk of length $n\geq 2$
with a shunt $g\in\text{{\rm Sh}}_{G}(\alpha)$. Suppose that the walk
$\hat{\alpha}$ has Property (R). Denote $\ell=|\text{{\rm
Succ}}_{G}(\alpha)|$, $k=|\text{{\rm Succ}}_{G}(\hat{\alpha})|$ and $X=\langle
G_{\hat{\alpha}},G_{\hat{\alpha}^{g}}\rangle$. If any of the Conditions
$(a)-(c)$ hold, then the walk $\alpha$ has Property (R) :

  1. (a)

there is no integer $i$, such that $\ell\leq i<k$ and $i|k$,

  2. (b)

the group $X$ acts transitively on the set $\text{{\rm
Succ}}_{G}(\hat{\alpha})$,

  3. (c)

$X=G_{(\hat{\alpha}\cap\hat{\alpha}^{g})}$, where
$\hat{\alpha}\cap\hat{\alpha}^{g}=(v_{1},\ldots,v_{n-1})$.

###### Proof.

Denote $\rho=\hat{\alpha}$, $\tau=(v_{1},\ldots,v_{n})$, and $S=\text{{\rm
Succ}}_{G}(\rho)$. Note that $S=\tau^{G_{\rho\cap\tau}}$ by Lemma 2.4. Let
$R=\tau^{G_{\rho}}$. Then $R\subseteq S\subseteq\tau^{G}=\rho^{G}$.

For the sequence $\alpha,\alpha^{g}$ observe that
$\alpha,\alpha^{g}\in\alpha^{G}$, $\alpha^{g}\in\text{{\rm
Succ}}_{G}(\alpha)$, and $\hat{\alpha^{g}}=\hat{\alpha}^{g}=\tau$, thus by
definition

(1) $\displaystyle\rho\sim_{\alpha}\tau.$

Now take any walk in $R$. By the definition of $R$ we can write it as
$\tau^{h}$ for some $h\in G_{\rho}$. Since $G$ preserves the relation
$\sim_{\alpha}$, it follows from (1) that
$\rho=\rho^{h}\sim_{\alpha}\tau^{h}$. Therefore
$R\subseteq[\rho]_{\sim_{\alpha}}$ (where $[\chi]_{\sim_{\alpha}}$ denotes the
equivalence class of $\chi$ with respect to $\sim_{\alpha}$). Since
$R\subseteq S$, we see that

(2) $\displaystyle R\subseteq S\cap[\rho]_{\sim_{\alpha}}.$

On the other hand, $G_{\rho}$ acts on $S$ and preserves the relation
$\sim_{\alpha}$, hence $S\cap[\rho]_{\sim_{\alpha}}$ is a block for the action
of $G_{\rho}$ on $S$. In particular

(3) $\displaystyle|S\cap[\rho]_{\sim_{\alpha}}|\mathrel{|}|S|.$

Claim 1: $S\cap[\rho]_{\sim_{\alpha}}=S.$

Suppose first that the Condition a holds. Recall that $|S|=k$ and that
$G_{\rho}g=\text{{\rm Sh}}_{G}(\alpha)$ by Lemma 2.3. It follows that
$|R|=|\tau^{G_{\rho}}|=|\alpha^{G_{\rho}}|=|\alpha^{G_{\rho}g}|=|\alpha^{\text{{\rm
Sh}}_{G}(\alpha)}|=|\text{{\rm Succ}}_{G}(\alpha)|=\ell$. If we let
$i=|S\cap[\rho]_{\sim_{\alpha}}|$, we see that $i|k$ by (3), and by (2),
$\ell\leq i$, which implies $i=k$, as claimed.

Suppose now that the Condition b holds. Note that since $G_{\rho}$ preserves
the relation $\sim_{\alpha}$, $G_{\rho}$ fixes $[\rho]_{\sim_{\alpha}}$
setwise. Similarly $G_{\tau}$ fixes $[\tau]_{\sim_{\alpha}}$ setwise. Since
$[\rho]_{\sim_{\alpha}}=[\tau]_{\sim_{\alpha}}$ by (1), it now follows that
$X$ preserves $[\rho]_{\sim_{\alpha}}$ setwise. By assumption $X$ acts
transitively on $S$. Since $\rho\sim_{\alpha}\tau\in S$, we see that
$S\subseteq[\rho]_{\sim_{\alpha}}$, as claimed.

Suppose that the Condition c holds. The group $X=G_{(\rho\cap\tau)}$ acts
transitively on the set $\text{{\rm Succ}}_{G}(\rho)$, hence c implies b and
$S\subseteq[\rho]_{\sim_{\alpha}}$, as claimed. This completes the proof of
Claim 1.

We showed that $\rho\sim_{\alpha}\nu$ for all $\nu\in\text{{\rm
Succ}}_{G}(\rho)$. Hence for every $\beta\in\rho^{G}$ and every
$\gamma\in\text{{\rm Succ}}_{G}(\beta)$, we see that
$\gamma\sim_{\alpha}\beta$.

Let $v\in V(\Gamma)$. By assumption, the walk $\rho$ has Property (R), and
hence $\tau$ has Property (R). Thus by definition there exists a sequence of
walks $\beta_{0},\ldots,\beta_{m}$, such that $\beta_{0}=\tau$,
$\beta_{i+1}\in\text{{\rm Succ}}_{G}(\beta_{i})$ for all
$i\in\\{0,\ldots,m-1\\}$, and the last vertex of the walk $\beta_{m}$ is $v$.
We need to show that there exists a sequence of walks (that are for $1$ longer
than $\beta_{i}$) starting with $\alpha$ such that every walk in the sequence
is a $G$-successor of the previous walk, and that the last vertex of the last
walk in the sequence is $v$. If $v=v_{n}$, there is nothing to prove. Assume
now that $v\neq v_{n}$. Then $m\geq 1$. Let $j\in\\{0,\ldots,m-1\\}$. By
definition of the relation $\sim_{\alpha}$, there exists a sequence of walks
$\gamma_{j,0},\ldots,\gamma_{j,t_{j}}$, where $\gamma_{j,s}\in\alpha^{G}$ for
all $s\in\\{0,\ldots,t_{j}\\}$, $\hat{\gamma_{j,0}}=\beta_{j}$,
$\hat{\gamma_{j,t_{j}}}=\beta_{j+1}$ and every walk in the sequence is a
$G$-successor of the previous walk in the sequence. Since
$\beta_{j+1}\in\text{{\rm Succ}}_{G}(\beta_{j})$, it follows that
$\beta_{j+1}\neq\beta_{j}$, and therefore $t_{j}\geq 1$ for all
$j\in\\{0,\ldots,m-1\\}$.

Observe that the sequence of walks

$\alpha,\gamma_{0,0},\ldots,\gamma_{0,t_{1}-1},\gamma_{2,0},\ldots,\gamma_{2,t_{2}-1},\ldots,\gamma_{m-1,0},\ldots,\gamma_{m-1,t_{m-1}-1}$

is such that the first walk in the sequence is $\alpha$, the last vertex of
the last walk is $v$, and every walk is a $G$-successor of the previous one,
which proves that $\alpha$ has Property (R). ∎

######  Remark 3.7.

In the above proof we proved that Condition c implies Condition b. However,
using the permutation group version of the Frattini argument, one can easily
see that Conditions b c from Lemma 3.6 are equivalent.

######  Lemma 3.8.

Let $G$ be a subgroup of $Aut(\Gamma)$ for a graph $\Gamma$. Suppose that
$\alpha$ has Property (R) and that $G_{\alpha}$ fixes $\text{{\rm
Succ}}_{G}(\alpha)$ pointwise. Then $G_{\alpha}=1$.

###### Proof.

Let $g\in\text{{\rm Sh}}_{G}(\alpha)$. Then $\alpha^{g}\in\text{{\rm
Succ}}_{G}(\alpha)$, thus by assumption $G_{\alpha}\subseteq
G_{\alpha^{g}}=G_{\alpha}^{g}$. Since $|G_{\alpha}|=|G_{\alpha}^{g}|$, observe
that $G_{\alpha}=G_{\alpha}^{g}$, thus $\langle\text{{\rm
Sh}}_{G}(\alpha)\rangle$ normalizes the group $G_{\alpha}$. But by Theorem 3.4
the group $\langle\text{{\rm Sh}}_{G}(\alpha)\rangle$ acts transitively on
$V(\Gamma)$, therefore $G_{\alpha}=1$. ∎

######  Corollary 3.9.

Let $\Gamma$ be a connected graph, let $G$ be an arc-transitive subgroup of
$\text{{\rm Aut}}(\Gamma)$, and let $r\geq 1$. Let
$\alpha=(v_{0},\ldots,v_{r})$ be a $G$-consistent walk with a shunt
$g\in\text{{\rm Sh}}_{G}(\alpha)$. For every $n\in\\{1,\ldots,r\\}$ let
$\alpha_{n}=(v_{0},\ldots,v_{n})$ and $k_{n}=|\text{{\rm
Succ}}_{G}(\alpha_{n})|$. If $G_{\alpha}$ fixes all elements of the set
$\text{{\rm Succ}}_{G}(\alpha)$ and if for every $n\in\\{1,\ldots,r-1\\}$ at
least one of the following Conditions $(a)-(c)$ holds, then $G_{\alpha}=1$.

  1. (a)

There is no integer $i$ such that $k_{n+1}\leq i<k_{n}$ and that $i|k_{n}$

  2. (b)

The group $\langle G_{\alpha_{n}},G_{\alpha_{n}^{g}}\rangle$ acts transitively
on the set $\text{{\rm Succ}}_{G}(\alpha_{n})$

  3. (c)

$\langle
G_{\alpha_{n}},G_{\alpha_{n}^{g}}\rangle=G_{({\alpha_{n}}\cap{\alpha_{n}}^{g})}$,
where $\alpha_{n}\cap{\alpha_{n}}^{g}=(v_{1},\ldots,v_{n})$.

###### Proof.

The group $G$ acts arc-transitively on $\Gamma$, thus for an arc
$(u_{0},u_{1})$ every arc of the form $(u_{1},u_{2})$ is its $G$-successor.
Since $\Gamma$ is a connected graph, the arc $(v_{0},v_{1})$ has Property (R).
By induction it then follows from Lemma 3.6 that $\alpha$ has Property (R),
hence $G_{\alpha}=1$ by Lemma 3.8. ∎

The following lemma provides an equivalent condition for a $G$-successor of a
walk $\alpha$ to be fixed by $G_{\alpha}$, we will use it in Sections 4 and 5.

######  Lemma 3.10.

Let $\Gamma$ be a graph and let $G\leq\text{{\rm Aut}}(\Gamma)$. Suppose that
$\alpha=(v_{0},\ldots,v_{r})$ is a $G$-consistent walk and that
$\beta=(v_{1},\ldots,v_{r+1})$ is a $G$-successor of $\alpha$. Then
$G_{\alpha}$ fixes $\beta$ if and only if $|\text{{\rm
Succ}}_{G}(v_{0},\ldots,v_{r},v_{r+1})|=1$.

###### Proof.

Since the walk $(v_{0},\ldots,v_{r},v_{r+1})$ is $G$-consistent, there exists
an automorphism $g\in\text{{\rm Sh}}_{G}(v_{0},\ldots,v_{r},v_{r+1})$. By
Lemma 2.3, $|\text{{\rm
Succ}}_{G}(v_{0},\ldots,v_{r},v_{r+1})|=|(v_{0},\ldots,v_{r},v_{r+1})^{G_{(}v_{0},\ldots,v_{r})g}|=|(v_{0},\ldots,v_{r},v_{r+1})^{G_{(}v_{0},\ldots,v_{r})}|$.
Observe that $|(v_{0},\ldots,v_{r},v_{r+1})^{G_{(}v_{0},\ldots,v_{r})}|=1$ if
and only if $G_{\alpha}$ fixes the walk $\beta$, hence $G_{\alpha}$ fixes the
walk $\beta$ if and only if $|\text{{\rm
Succ}}_{G}(v_{0},\ldots,v_{r},v_{r+1})|=1$. ∎

##  4\. Graphs with locally weakly $p$-subregular group actions

In this section we will consider $G$-arc-transitive graphs where the local
group $G_{v}^{\Gamma(v)}$, that is the subgroup of $\text{Sym}(\Gamma(v))$
induced by the action of vertex a stabilizer of $G_{v}$ on the set
$\Gamma(v)$, belongs to a class of _weakly $p$-subregular_ permutation groups,
first defined in [19]. As we prove in Theorem 4.3 one can then always find a
$G$-consistent walk with a trivial $G$-stabilizer.

######  Definition 4.1.

Let $p$ be a prime number. A transitive permutation group $L$ is weakly
$p$-subregular on the set $\Omega$, if there exist $x,y\in\Omega$ such that
$|L_{x}|=p$ and $x^{\overline{L}}\cup y^{\overline{L}}=\Omega$, where
$\overline{L}=\langle L_{x},L_{y}\rangle$.

Some examples of weakly $p$-subregular permutation groups include the dihedral
groups in their natural actions (for $p=2$), the wreath product $C_{p}\wr
C_{2}$ in its natural imprimitive action on $\\{1,\ldots,p\\}\times\\{1,2\\}$
as well as $\text{SL}(2,p)$ on $\mathbb{Z}_{p}^{2}\setminus\\{0\\}$, see [18,
19] for further examples.

The following lemma was proved as Claim 1 in the proof of Theorem 2.2 in [19].
Note that the formulation here is equivalent to formulation in [19], since
$\langle\text{{\rm Sh}}_{G}((x,v,y))\rangle=\langle G_{(x,v)},g\rangle$, where
$g\in G$ is any such automorphism that $(x,v)^{g}=(v,y)$.

######  Lemma 4.2.

Let $\Gamma$ be a connected graph, let $G$ be an arc-transitive subgroup of
$\text{{\rm Aut}}(\Gamma)$, let $v\in V(\Gamma)$ and let $L=G_{v}$. Suppose
that there exist $x,y\in\Gamma(v)$, such that $x^{\overline{L}}\cup
y^{\overline{L}}=\Gamma(v)$, where $\overline{L}=\langle L_{x},L_{y}\rangle$.
Then $\langle\text{{\rm Sh}}_{G}((x,v,y))\rangle$ is transitive on
$V(\Gamma)$.

######  Theorem 4.3.

let $G$ be an arc-transitive subgroup of the automorphism group of a graph
$\Gamma$ of valence at least $3$ and let $v\in V(\Gamma)$. Suppose that
$G_{v}^{\Gamma(v)}$ is weakly $p$-subregular for a prime $p$. Then there
exists a $G$-consistent walk $\alpha$ with $G_{\alpha}=1$.

###### Proof.

Let $L=G_{v}^{\Gamma(v)}$. Then by assumptions there exist vertices $x,y\in
V(\Gamma)$ such that $|L_{x}|=|L_{y}|=p$ and $x^{\overline{L}}\cup
y^{\overline{L}}=\Gamma(v)$, where $\overline{L}=\langle L_{x},L_{y}\rangle$.

Let $\alpha$ be a maximal $G$-consistent walk that begins with the sequence
$(x,v,y)$ and for which $|\text{{\rm Succ}}_{G}(\alpha)|>1$. We first need to
show that such walks exist; we will show that $(x,v,y)$ satisfies the
conditions. Since $G$ is arc-transitive, the walk $(x,v,y)$ is $G$-consistent.
Recall that $|\text{{\rm Succ}}_{G}(x,v,y)|={|G_{(x,v)}|}/{|G_{(x,v,y)}|}$ by
Lemma 2.5. The definition of a weakly $p$ subregular group implies that
$L_{x,y}=1$, and thus
${|G_{(x,v)}^{\Gamma(v)}|}/{|G_{(x,v,y)}^{\Gamma(v)}|}=|{L_{x}}|/|{L_{x,y}}|=p$.
Hence $|G_{(x,v)}|\neq|G_{(x,v,y)}|$, it now follows that $|\text{{\rm
Succ}}_{G}(x,v,y)|>1$. Let $\alpha=(v_{0},\ldots,v_{n})$, where $v_{0}=x,\
v_{1}=v$ and $v_{2}=y$, and let $g\in\text{{\rm Sh}}_{G}(\alpha)$. Denote also
$v_{n+1}=v_{n}^{g}$, $\alpha_{i}=(v_{0},\ldots,v_{i})$ and $k_{i}=|\text{{\rm
Succ}}_{G}(\alpha_{i})|$ for all $i\in\\{2,\ldots,n\\}$. We will show that for
an arbitrary $i\in\\{2,\ldots,n\\}$, the walk $\alpha_{i}$ has Property (R).
Note that

$k_{i}=|\text{{\rm
Succ}}_{G}(\alpha_{i})|=|\alpha_{i}^{gG_{(v_{1},\ldots,v_{i})}}|=|(v_{1},\ldots,v_{i+1})^{G_{(v_{1},\ldots,v_{i})}}|=|v_{i+1}^{G_{(v_{1},\ldots,v_{i})}}|=|v_{i+1}^{G_{(v_{1},\ldots,v_{i})}^{\Gamma(v_{i})}}|.$

The second equality follows from Lemma 2.3, the last equality holds because
$G_{(v_{1},\ldots,v_{i})}$ acts on the set $\Gamma(v_{i})$. Now since
$(v_{0},v_{1},v_{2})^{g^{i-1}}=(v_{i-1},v_{i},v_{i+1})$, observe that
$G_{(v_{1},\ldots,v_{i})}^{\Gamma(v_{i})}\leq
G_{(v_{i-1},v_{i})}^{\Gamma(v_{i})}=L_{x}^{g^{i-1}}$. Hence
$|G_{(v_{1},\ldots,v_{i})}^{\Gamma(v_{i})}|$ is either $1$ or $p$ and $k_{i}$
is either $1$ or $p$. By the definition of $\alpha$, the parameter $k_{i}$ can
not be $1$, so $k_{i}=p$ for every $i\in\\{2,\ldots,n\\}$. The walk $(x,v,y)$
has Property (R) by Lemma 4.2. It then follows by repeated application of
Lemma 3.6 (using Condition a), that $\alpha_{i}$ has Property (R) for all
$i\in\\{2,\ldots,n\\}$, as claimed. In particular $\alpha$ has Property (R).

Let $\beta\in\text{{\rm Succ}}_{G}(\alpha)$, then
$\beta=\alpha^{h}=(v_{1},\ldots,v_{n},u)$ for some $h\in\text{{\rm
Sh}}_{G}(\alpha)$ and $u\in V(\Gamma)$. The walk $(v_{0},\ldots v_{n},u)$ is
$G$-consistent with a shunt $h\in\text{{\rm Sh}}_{G}(\beta)$, and begins with
the vertices $x,v,y$. But since $\alpha$ is maximal such walk with
$|\text{{\rm Succ}}_{G}(\alpha)|>1$, it follows that $|\text{{\rm
Succ}}_{G}((v_{0},\ldots,v_{n},u))|=1$. By Lemma 3.10, the stabilizer
$G_{\alpha}$ fixes $\beta$ for an arbitrary $\beta\in\text{{\rm
Succ}}_{G}(\alpha)$. Hence $G_{\alpha}=1$ by Lemma 3.8. ∎

##  5\. Stabilizers of $G$-consistent walks in $4$-valent graphs

As the second application of Corollary 3.9 we show the existence of a
$G$-consistent walk with a trivial $G$-stabilizer for an arbitrary $4$-valent
graph and an arc transitive $G\leq\text{{\rm Aut}}(\Gamma)$, in particular we
prove the following theorem.

######  Theorem 5.1.

Let $\Gamma$ be a connected $4$-valent graph and let $G$ be an arc-transitive
subgroup of $\text{{\rm Aut}}(\Gamma)$. Then there exists a $G$-consistent
walk $\alpha$ with $G_{\alpha}=1$.

###### Proof.

Let $v\in V(\Gamma)$ and $u\in\Gamma(v)$. Then $G_{(u,v)}$ acts on the set
$\Omega=\Gamma(v)\setminus\\{u\\}$, the local group $H=G_{(u,v)}^{\Omega}$ is
either trivial, $C_{2}$, $C_{3}$ or $S_{3}$.

If $H$ is the trivial group, we take $(u,v)$ as $\alpha$. The walk $\alpha$
has Property (R) , since $\Gamma$ is connected and $G$ acts transitively on
the set of arcs of $\Gamma$. The stabilizer $G_{\alpha}$ fixes the set
$\text{{\rm Succ}}_{G}(\alpha)$ pointwise, hence $G_{\alpha}=1$ by Corollary
3.9.

If $H$ is permutation isomorphic to $C_{2}$, then $G_{v}^{\Gamma(v)}$ is
permutation isomorphic to $D_{4}$, so it is weakly $p$-subregular on
$\Gamma(v)$. A $G$-consistent walk $\alpha$ with $G_{\alpha}=1$ then exists by
Theorem 4.3.

In case when $H$ is permutation isomorphic to $C_{3}$ or $S_{3}$, $G$ acts
$2$-arc transitively on $\Gamma$, hence an arbitrary $2$-arc $(u,v,w)$ is a
$G$-consistent walk. Let $\alpha=(v_{0},\ldots,v_{r})$ be the longest
$G$-consistent walk such that $|\text{{\rm Succ}}_{G}(\alpha)|>1$,
$v_{0}=u,v_{1}=v$ and $v_{2}=w$. We will show that then $\alpha$ satisfies the
conditions from Corollary 3.9. For all $z\in\Gamma(v)$ the walk $(v,z)$ is a
$G$-successor of $(u,v)$, since $G$ acts arc-transitively on $\Gamma$. Hence
$|\text{{\rm Succ}}_{G}(v,u)|=4$. Similarly the $G$-successors of the walk
$(u,v,w)$ are the walks $(v,w,z)$ for $z\in\Gamma(u)\setminus\\{v\\}$, since
$G$ acts $2$-arc-transitively on $\Gamma$. Hence $|\text{{\rm
Succ}}_{G}(v,u,w)|=3$.

Let $\alpha_{i}=(v_{0},\ldots,v_{i})$ for all $i=\\{1,\ldots,r\\}$ . For all
$i,j<r$, $i\leq j$, the walks $\alpha_{i}$ and $\alpha_{j}$ are $G$-conistent
and $|\text{{\rm Succ}}_{G}(\alpha_{j})|\leq|\text{{\rm
Succ}}_{G}(\alpha_{i})|$. Since there is no divisor $k$ of $3$ or $\ell$ of
$2$ such that $1<k<3$ or $1<\ell<2$, each $\alpha_{i}$ is $G$-consistent and
satisfies Condition a in Corollary 3.9. By the definition of $\alpha$ we know
that $|\text{{\rm Succ}}_{G}(\beta)|=1$ for any $G$-consistent walk
$\beta=(v_{0},\ldots,v_{r},x)$ and $x\in V(\Gamma)$. Hence the stabilizer
$G_{\alpha}$ fixes all elements of the set $\text{{\rm Succ}}_{G}(\alpha)$ by
Lemma 3.10. It follows that $G_{\alpha}=1$ By corollary 3.9. ∎

######  Remark 5.2.

Theorems 2.1, 5.1 and the Orbit-Stabilizer Lemma imply that for a connected
$4$-valent graph $\Gamma$, an arc-transitive $G\leq\text{{\rm Aut}}(\Gamma)$
and $v\in V(\Gamma)$ with $|G_{v}|=3^{s}2^{t}$, there exist $4$ orbits
consistent cycles. One of the orbits contains all trivial cycles, which all
have $3^{s}2^{t-2}$ shunts. For two of the remaining orbits, every cycle has a
unique shunt, while any cycle in the last orbit has $2^{t-2}$ distinct shunts.

##  6\. Examples of graphs for which there exists no $G$-consistent walk with
a trivial stabilizer

For a non-prime integer $d\geq 6$ there always exist connected arc-transitive
$d$-valent graphs in which no consistent cycle has a trivial stabilizer. If
$d=a\cdot b$ with $a,b\neq 1$ and $a\geq 3$, we can start with any connected
arc-transitive $a$-valent graph $\Gamma$ that has no twin vertices and is not
isomorphic to $\text{Cay}(\mathbb{Z}_{n},S)$ with $\pm 1\in S$, for example
the hypercube $Q_{a}$ (see [7] for the classification of arc-transitive and
[1] for the classification of $2$-arc transitive circulants). As we prove
below, the graph $\Gamma[\overline{K_{b}}]$, where $\overline{K_{b}}$ denotes
the empty graph on $b$ vertices, is then an arc-transitive $d$-valent graph in
which no cycle has a trivial stabilizer.

As noted in [10], a $G$-consistent walk $\alpha=(v_{0},\ldots,v_{n})$ and a
shunt $g\in\text{{\rm Sh}}_{G}(\alpha)$ induce a unique $G$-consistent cycle
$\beta$. If no vertices in $\alpha$ repeat, then
$\beta=(v_{0},\ldots,v_{n},v_{n}^{g},v_{n}^{g^{2}},\ldots v_{n}^{g^{i}})$
where $i$ is the first integer for which $v_{n}^{g^{i}}=v$ for some vertex $v$
in $\alpha$, clearly $v$ must then be $v_{0}$. If $v_{k}$ is the first vertex
in $\alpha$ that is the same as one of the previous vertices, then
$v_{k}=v_{0}$ and $v_{x}=v_{x\mod k}$ for all $x\in\\{0,\ldots,n\\}$. In this
case the induced cycle $\beta$ is $(v_{0},\ldots,v_{k})$.

######  Lemma 6.1.

Let $\Gamma$ be a connected vertex-transitive graph that has no twin vertices
and is not isomorphic to $\text{Cay}(\mathbb{Z}_{n},S)$ with $\pm 1\in S$ for
any $n\in\mathbb{N}$. Let $m\geq 2$. Then
$\tilde{\Gamma}=\Gamma[\overline{K_{m}}]$ contains no consistent walk with a
trivial stabilizer.

###### Proof.

Every consistent walk induces a consistent cycle, whose stabilizer is a
subgroup of the stabilizer of the consistent walk. Hence it is enough to show
that $\tilde{\Gamma}$ contains no consistent cycle with a trivial stabilizer.
If a consistent cycle in $\Gamma$ contains all the vertices of $\Gamma$, then
its shunt generates a cyclic vertex-regular subgroup of $\text{{\rm
Aut}}(\Gamma)$, which contradicts the assumption that $\Gamma$ is not
isomorphic to $\text{Cay}(\mathbb{Z}_{n},S)$ with $\pm 1\in S$ for some
$n\in\mathbb{N}$. Hence there exists no consistent cycle in $\Gamma$ that
constains all the vertices of $\Gamma$.

Suppose that $\Gamma$ is a $d$-valent graph. By Theorem 2.1, there exist $d$
orbits of consistent cycles in $\Gamma$. We denote their representatives by
$\alpha_{1},\ldots,\alpha_{d}$ (note that one of them is the trivial cycle
that only contains two distinct vertices). For every $i\in\\{1,\ldots,d\\}$ we
can build $m$ consistent cycles $\beta_{i,1},\beta_{i,2}\ldots\beta_{i,m}$ in
$\tilde{\Gamma}$. Let $\alpha_{i}=(v_{0},v_{1},\ldots,v_{k-1},v_{k},v_{0})$,
let $g_{i}$ be a shunt for $\alpha_{i}$ and let
$V(\overline{K_{m}})=\\{0,\ldots,m-1\\}$. Then, define

$\displaystyle\beta_{i,1}$
$\displaystyle=((v_{0},0),(v_{1},0),\ldots,(v_{k-1},0)(v_{k},0),(v_{0},0)),$
$\displaystyle\beta_{i,2}$
$\displaystyle=((v_{0},0),(v_{1},0),\ldots,(v_{k-1},0)(v_{k},0),(v_{0},1),(v_{1},1),\ldots,(v_{k-1},1)(v_{k},0)),$
$\displaystyle\vdots$ $\displaystyle\beta_{i,m}$
$\displaystyle=((v_{0},0),(v_{1},0),\ldots,(v_{k-1},0)(v_{k},0),(v_{0},1),(v_{1},1),\ldots,(v_{k-1},1)(v_{k},2),\ldots$
$\displaystyle\ldots,(v_{0},m-1),(v_{1},m-1),\ldots,(v_{k-1},m-1)(v_{k},0)).$

Note that all the sequences $\beta_{i,1},\beta_{i,2},\ldots,\beta_{i,m}$ are
cycles in $\tilde{\Gamma}$. They are consistent, since $S_{m}\wr\text{{\rm
Aut}}(\Gamma)$ (where $S_{m}$ acts naturally on $\\{0,1,\ldots,n-1\\}$) is a
subgroup of the automorphism group of $\tilde{\Gamma}$, and $(((0\ 1\ \ldots\
j),\text{id},\ldots,\text{id}),g_{i})\in S_{m}\wr\text{{\rm Aut}}(\Gamma)$ is
a shunt for $\beta_{i,j}$.

We claim that the cycles $\beta_{i,j}$ are representatives of different
$\text{{\rm Aut}}(\tilde{\Gamma})$-orbits of consistent cycles in
$\tilde{\Gamma}$. Observe that for all $i,j_{1},j_{2}$, the cycles
$\beta_{i,j_{1}}$ and $\beta_{i,j_{2}}$ have different length, hence they are
included in different $\text{{\rm Aut}}(\tilde{\Gamma})$-orbit of consistent
cycles.

We are left with the case $i_{1}\neq i_{2}$. Suppose there exist
$j_{1},j_{2}\in\\{1,\ldots,m\\}$ and $g\in\text{{\rm Aut}}(\tilde{\Gamma})$
such that $\beta_{i_{1},j_{1}}^{g}=\beta_{i_{2},j_{2}}$. Since $\Gamma$ has no
twin vertices, the sets $\\{v_{i}\\}\times\\{0,\ldots,m-1\\}$ for $v_{i}\in
V(\Gamma)$ are a block system for the action of $\text{{\rm
Aut}}(\tilde{\Gamma})$. Thus $g$ determines an automorphism
$g^{\prime}\in\text{{\rm Aut}}(\Gamma)$, where $g^{\prime}(v_{i})$ is the
first component of $g(v_{i},0)$. But
$\alpha_{i_{1}}^{g^{\prime}}=\alpha_{i_{2}}$, which is a contradiction with
the fact that $\alpha_{i_{1}}$ and $\alpha_{i_{2}}$ are representatives of
different $\text{{\rm Aut}}(\Gamma)$-orbits of consistent cycles in $\Gamma$.
This concludes the proof of the claim.

For every $\beta_{i,j}$, let $v_{i}\in V(\Gamma)$ be a vertex that is not
included in $\alpha_{i}$. Then every permutation $k$ that exchanges
$(v_{i},0)$ and $(v_{i},1)$ while fixing all other vertices of
$\tilde{\Gamma}$ is an automorphism of $\tilde{\Gamma}$ that fixes
$\beta_{i,j}$. Hence $\beta_{i,j}$ does not have a trivial stabilizer.

Since $\tilde{\Gamma}$ is a vertex-transitive $dm$-valent graph, there exists
$dm$ $\text{{\rm Aut}}(\tilde{\Gamma})$-orbits of consistent cycles by Theorem
2.1. There are $dm$ many cycles $\beta_{i,j}$, it follows that must include
one representative from each $\text{{\rm Aut}}(\tilde{\Gamma})$-orbit of
consistent cycles. Therefore no consistent cycle in $\tilde{\Gamma}$, and
hence no consistent walk in $\tilde{\Gamma}$, has a trivial stabilizer. ∎

##  7\. Consistent cycles and group generators

Let $\Gamma$ be a connected $d$-valent graph and let $G$ be a vertex-
transitive subgroup of $\text{{\rm Aut}}(\Gamma)$. Recall, that by a result of
Conway [4, 10] there exist $d$ $G$-orbits of $G$-consistent cycles in
$\Gamma$. Moreover, as proved in [11, Lemma 3.5], one can choose one
representative from each of the orbits so that the representatives of any two
orbits share as many initial vertices as is possible for any two cycles from
those orbits. Let us make this more precise.

######  Definition 7.1 ([11]).

Let $\alpha=(a_{0},\ldots,a_{k})$ and $\beta=(b_{0},\ldots,b_{\ell})$ be two
walks. Then their overlap $m(\alpha,\beta)=-1$ if $a_{0}\neq b_{0}$, and, if
$a_{0}=b_{0}$,

$m(\alpha,\beta)=\text{max}\\{t\mid a_{i}=b_{i}\hbox{ for }i=0,1,2,...,t\\}.$

Similarly, if $A=\alpha^{G}$ and $B=\beta^{G}$ are two distinct $G$-orbits of
$G$-consistent walks, then

$m(A,B)=\max\\{m(\alpha,\beta):\alpha\in A,\beta\in B\\}.$

######  Lemma 7.2 ([11, Lemma 3.5]).

If $G\leq\text{{\rm Aut}}(\Gamma)$, then there exists a complete set of
representatives $\beta_{1},\ldots,\beta_{d}$ of the $G$-orbits of
$G$-consistent cycles such that
$m(\beta_{i},\beta_{j})=m(\beta_{i}^{G},\beta_{j}^{G})$ for every pair $i,j$,
$i\not=j$.

Let $\mathcal{C}=\\{\beta_{1},\ldots,\beta_{d}\\}$ be such a set of
representatives of $G$-orbits of $G$-conistent cycles and let
$g_{1},\ldots,g_{d}\in G$ be one shunt for each of
$\beta_{1},\ldots,\beta_{d}$ respectively. Let $S=\langle
g_{1},\ldots,g_{d}\rangle$. We will prove that if there exists a
$G$-consistent cycle $\alpha$ such that $G_{\alpha}=1$, then $S=G$. In
particular $\mathbf{d}(G)\leq\text{val}(G)$, where $\mathbf{d}(G)$ denotes the
size of the smallest generating set of $G$.

######  Theorem 7.3.

Let $\Gamma$ be a connected graph, let $G$ be a vertex-transitive subgroup of
$\text{{\rm Aut}}(\Gamma)$ and let $\tau$ be a $G$-consistent walk. Suppose
that $H\leq G$ is such that $G_{\tau}\leq H$ and that $S\subseteq H$. Then
$H=G$.

###### Proof.

Let $g\in\text{{\rm Sh}}_{G}(\tau)$ and let $\alpha=(v_{0},\ldots,v_{n})$ be
the $G$-consistent cycle induced by $g$ and $\tau$. We can assume that
$\alpha=\beta_{1}$ and $g=g_{1}$. For $i\in\\{1,\ldots,n\\}$ let
$\alpha_{i}=(v_{0},\ldots,v_{i})$. Since $G$ acts on the set of all
$G$-consistent walks of length $i-1$, note that for every
$i\in\\{2,\ldots,n\\}$ (see Lemma 2.3):

(4) $\displaystyle G_{\alpha_{i-1}}=\text{{\rm Sh}}_{G}(\alpha_{i})g^{-1}.$

We will inductively prove that for every $i\in\\{1,\ldots,n\\}$:

  1. (i)

$G_{\alpha_{i-1}}\leq H$,

  2. (ii)

$\text{{\rm Sh}}_{G}(\gamma)\subseteq H$ for every $G$-consistent cycle
$\gamma$ for which $m(\gamma,\alpha)\geq i$.

First let $i=n$. Then the walks $\alpha=\alpha_{n}$ and $\alpha_{n-1}$ contain
the same vertices, hence $G_{\alpha_{n-1}}=G_{\alpha_{n}}\leq G_{\tau}\leq H$.
The only $G$-consistent cycle that has overlap at least $n$ with $\alpha$ is
$\gamma=\alpha$. Since $\text{{\rm Sh}}_{G}(\alpha)=G_{\alpha_{n-1}}g$ by (4),
and since $g\in H$, it follows that $\text{{\rm Sh}}_{G}(\gamma)\subseteq H$.

Suppose now that the claim is true for $i+1$, we will prove that it is then
true for $i$. Let $\gamma$ be a $G$-consistent cycle such that
$m(\gamma,\alpha)\geq i$. There exist $\beta\in\mathcal{C}$ and $h\in G$ such
that $\beta^{h}=\gamma$. Let $g_{\beta}\in S\subseteq H$ be a shunt for
$\beta$. Then $s=(g_{\beta})^{h}\in\text{{\rm Sh}}_{G}(\gamma)$. Since $\beta$
has the largest possible overlap with $\alpha$ of any cycle in its orbit, it
follows that $m(\beta,\alpha)\geq m(\gamma,\alpha)\geq i$, hence $h\in
G_{\alpha_{i}}\leq H$. Therefore $s\in H$. Let
$\gamma_{i+1}=(c_{0},\ldots,c_{i},c_{i+1})$ be the subwalk of $\gamma$ that
contains the first $i+2$ vertices of $\gamma$. Then $\text{{\rm
Sh}}_{G}(\gamma)\subseteq\text{{\rm Sh}}_{G}(\gamma_{i+1})$. Since the overlap
of $\gamma$ and $\alpha$ is at least $i$, it follows that $v_{k}=c_{k}$ for
all $i\in\\{0,\ldots,i\\}$. By Lemma 2.3, $\text{{\rm
Sh}}_{G}(\gamma_{i+1})=G_{\alpha_{i}}s$, hence $\text{{\rm
Sh}}_{G}(\gamma)\subseteq H$, which proves part ii of the claim.

To prove part i of the claim note that

$\text{{\rm Sh}}_{G}(\alpha_{i})=\bigcup_{\begin{subarray}{c}\text{$\delta$;
$\delta$ is a $G$-consistent cycle}\\\ \text{and }\ m(\delta,\alpha)\geq
i\end{subarray}}\text{{\rm Sh}}_{G}(\delta),$

since for every element of $t\in\text{{\rm Sh}}_{G}(\alpha_{i})$ there exists
a $G$-consistent cycle with a shunt $t$ that begins with $\alpha_{i}$. Hence
by part ii it follows that $\text{{\rm Sh}}_{G}(\alpha_{i})\leq H$. Since
$G_{\alpha_{i-1}}=\text{{\rm Sh}}_{G}(\alpha_{i})g^{-1}$ by (4), it follows
that $G_{\alpha_{i-1}}\leq H$, which proves the claim.

We proved that $G_{v_{0}}\leq H$. Let $u\in\Gamma(v_{0})$, we will show that
there exists $s_{u}\in H$ such that $v_{0}^{s_{u}}=u$. Since $G$ is vertex-
transitive, there exists an automorphism that maps $v_{0}$ to $u$. This
induces a $G$-consistent cycle $\delta$ that begins with the vertices
$v_{0},u$. There exist $\beta\in\mathcal{C}$ and $h_{u}\in G_{v}$ such that
$\beta^{h_{u}}=\delta$. Let $g_{\beta}\in S$ be a shunt for $\beta$. Then
$s_{u}=(g_{\beta})^{h_{u}}$ is a shunt for $\delta$. Since $h_{u}\in
G_{v_{0}}\leq H$ and $g_{\beta}\in S\subseteq H$, it follows that $s_{u}\in
H$. Hence there exists an element of $H$ that maps $v_{0}$ to $u$. By a
connectedness argument it follows that $H$ is vertex-transitive. On the other
hand, $G_{v_{0}}\leq H$, hence $G=H$ by the Frattini argument. ∎

######  Corollary 7.4.

Let $G$ be a vertex-transitive group of automorphisms of a connected
$d$-valent graph $\Gamma$, and let $\alpha$ be a $G$-consistent walk. Then

$\mathbf{d}(G)\leq d+\mathbf{d}(G_{\alpha}).$

In particular, if $\Gamma$ contains a $G$-consistent cycle $\alpha$ such that
$G_{\alpha}=1$, then $\mathbf{d}(G)\leq d$.

To conclude, Corollary 7.4 can be refined for specific local actions to give a
partial solution to [3, Problem 4]. Indeed, in Theorem 4.3, we have proved
that the stabilizer of a consistent cycle is trivial whenever the local group
is weakly $p$-subregular.

######  Corollary 7.5.

Let $G$ be a vertex transitive group of automorphisms of a connected
$d$-valent graph $\Gamma$. Suppose that the local group is weakly
$p$-subregular for some primes $p$. Then $\mathbf{d}(G)\leq d$.

## Acknowledgement

This paper was written as a part of a doctoral thesis at the University of
Ljubljana. The author is grateful to her supervisor Primož Potočnik for all of
his help and guidance.

## References

  * [1] B. Alspach, M. Conder, D. Marušič, and M.-Y. Xu, A family of cubical graphs, J. Algebraic Combin., 5 (1996), 83–86.
  * [2] I. Antončič and P. Šparl, On tetravalent half-arc-transitive graphs of girth 5, Discrete Mathematics, 346 (2023), 113577.
  * [3] M. Barbieri and P. Spiga, On the number of generators of groups acting arc-transitively on graphs, arXiv:2405.13603
  * [4] J. H. Conway, Public lecture given at the Second British Combinatorial Conference, Royal Holloway College, (1971).
  * [5] I. Hubard, A. Ramos-Rivera and P. Šparl, Arc-transitive maps with underlying Rose Window graphs, J. Graph Theory, 96 (2020), 203-230.
  * [6] W. M. Kantor, Cycles in Graphs and Groups, The American Mathematical Monthly, 115 (2008), 559-562.
  * [7] I. Kovács, Classifying arc-transitive circulants, J. Algebraic Combin., 20 (2004), 353–358.
  * [8] K. Kutnar, D. Marusič, Š. Miklavič, and P. Šparl, On the structure of consistent cycles in cubic symmetric graphs, J. Graph Theory, 105 (2023), 337-356.
  * [9] K. Kutnar, D. Marusič, Š. Miklavič, and P. Šparl, On the structure of consistent cycles in cubic symmetric graphs, J. Graph Theory, 105 (2023), 337-356.
  * [10] Š. Miklavič, P. Potočnik, and S. Wilson, Consistent cycles in graphs and digraphs, Graphs and Combinatorics, 23 (2007), 205-216.
  * [11] Š. Miklavič, P. Potočnik, and S. Wilson, Overlap in consistent cycles, J. Graph Theory, 55 (2007), 55–71.
  * [12] P. Potočnik, P. Spiga, and G. Verret, On graph-restrictive permutation groups, J. Combin. Theory, Ser. B., 102 (2012), 820–831.
  * [13] P. Potočnik, P. Spiga, and G. Verret, On the order of arc-stabilisers in arc-transitive graphs with prescribed local group, Trans. Amer. Math. Soc., 366 (2014), 37293745.
  * [14] P. Spiga, An application of the Local C(G,T) Theorem to a conjecture of Weiss, Bull. Lond. Math. Soc., 48(1), 2016, 12–18,
  * [15] P. Spiga and G. Verret, On the order of vertex-stabilisers in vertex-transitive graphs with local group $C_{p}\times C_{p}$ or $C_{p}\wr C_{2}$, J. Algebra, 448 (2016), 174-209.
  * [16] W. T. Tutte, A family of cubical graphs, Proc. Cambridge Philos. Soc., 43 (1947), 459–474.
  * [17] W. T. Tutte, On the symmetry of cubic graphs, Canad. J. Math., 11 (1959), 621–624.
  * [18] G. Verret, On the order of arc-stabilizers in arc-transitive graphs, Bull. Aust. Math. Soc., 80 (2009), 498–505.
  * [19] G. Verret, On the order of arc-stabilizers in arc-transitive graphs, II, Bull. Aust. Math. Soc., 87 (2013), 441–447.
  * [20] R. Weiss, The nonexistence of 8-transitive graphs, Combinatorica, 1 (1981), 309-311.