Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I am reading "Algebraic Graph Theory" by Norman Biggs (1974). On page 119, there is a proposition which says the following:

Proposition 18.1: Let $[\alpha]$ be a $t$-arc in a cubic $t$-transitive graph $X$. Then an automorphism of $X$ which fixes $[\alpha]$ must be the identity automorphism.

To understand the Proposition, and the proof, some definitions and lemmas are needed. A $t$-arc is defined as follows:

A $t$-arc in a graph $X$ is an ordered set $[\alpha] = (\alpha_0,\ldots, \alpha_t)$ of $t+1$ vertices in $V(X)$, such that $\alpha_i \alpha_{i+1} \in E(X)$ and $\alpha_{i-1} \neq \alpha_{i+1}$ for $1 \leq i \leq t-1$.

We can concatenate such arcs by the following definition

If $[\alpha]$ is a $t$-arc in a graph $X$ and $[\beta]$ is a $s$-arc in $X$, then we use $[\alpha . \beta]$ to denote the $(t+s+1)$-arc $(\alpha_0,\ldots,\alpha_t,\beta_0,\ldots,\beta_s)$, provided that $\alpha_t \beta_0 \in E(X)$, $\alpha_{t-1} \neq \beta_0$ and $\alpha_{t} \neq \beta_1$.

We also need the term succesive arcs

Let $[\alpha]$ and $[\beta]$ be any two $s$-arcs in a graph $X$. We say that $[\beta]$ is a successor of $[\alpha]$ if $\beta_i = \alpha_{i+1}$ $(0 \leq i \leq s-1)$.

We also need a Lemma which states

Lemma 17.4: Let $X$ be a connected graph in which the degree of each vertex is at least three. If $s \geq 1$ and $[\alpha],[\beta]$ are any two $s$-arcs in $X$, then there is a finite sequence $[\alpha^{(i)}]$ $(1 \leq i \leq l)$ of $s$-arcs in $X$ such that $[\alpha^{(1)}] = [\alpha]$, and $[\alpha^{(l)}] = [\beta]$, and $[\alpha^{(i+1)}]$ is a successor of $[\alpha^{(i)}]$ for $1 \leq i \leq s-1$.

and at last a Theorem which says

Theorem 17.5: Let $X$ be a connected graph, where all vertices in $V(X)$ are at least 3 and let $[\alpha]$ be a $t$-arc in $X$. Suppose the vertices adjacent to $\alpha_t$ are $\alpha_{t-1}$ and $v_1,v_2,\ldots,v_l$, and let $[\beta^{(i)}]$ denote the $t$-arc $(\alpha_1,\alpha_2,\ldots,\alpha_t,v_i)$ for $1 \leq i \leq l$, so that each $[\beta^{(i)}]$ is a successor of $[\alpha]$. Now $Aut(X)$ is transitive on $t$-arcs if and only if there are automorphisms $g_1,g_2,\ldots,g_l$ in $Aut(X)$ such that $g_i[\alpha] = [\beta^{(i)}] (1 \leq i \leq l)$.

The proof of the proposition goes as follows:

Proof of Proposition 18.1: Suppose $f$ is an automorphism fixing $\alpha_0,\alpha_1,\ldots,\alpha_t$; if $f$is not the identity, then $f$ does not fix all $t$-arcs in $X$. Thus, it follows from Lemma 17.4 that there is some $t$-arc $[\beta]$ such that $f$ fixes $[\beta]$, but $f$ does not fix both successors of $[\beta]$. In fact, if $\beta_{t-1},u_1,u_2$ are the vertices adjacent to $\beta_t$, then $f$ must interchange $u_1$ and $u_2$. Let $w \neq \beta_1$ be a vertex adjacent to $\beta_0$. Since $X$ is $t$-transitive there is an automorphism $h \in Aut(X)$ taking the $t$-arc $(w,\beta_0,\ldots,\beta_{t-1})$ to $[\beta]$, and we may suppose the notation chosen so that $h(\beta_t) = u_1$. Then $h$ and $fh$ are automorphisms of $X$ taking the $(t+1)$-arc $[w.\beta]$ to its two successors, and by Theorem 17.5, $Aut(X)$ is transitive on $(t+1)$-arcs. This contradicts our hypothesis, and so we must have $f = 1$.

I have some problem understanding parts of the proof. The first thing, which is not really essential for proving the proposition, is the part:

In fact, if $\beta_{t-1},u_1,u_2$ are the vertices adjacent to $\beta_t$, then $f$ must interchange $u_1$ and $u_2$

The other problem, which is quite essential to the proof, is the part:

Since $X$ is $t$-transitive there is an automorphism $h \in Aut(X)$ taking the $t$-arc $(w,\beta_0,\ldots,\beta_{t-1})$ to $[\beta]$, and we may suppose the notation chosen so that $h(\beta_t) = u_1$. Then $h$ and $fh$ are automorphisms of $X$ taking the $(t+1)$-arc $[w.\beta]$ to its two successors

I get why there must be such a $h$, taking $(w,\beta_0,\ldots,\beta_{t-1})$ to $[\beta]$. But I do not get, why we can (without loss of generality) assume that $h(\beta_t)$ is a neighbor of $\beta_t$. Thus, I do not see how the other part; that

$h$ and $fh$ are automorphisms of $X$ taking the $(t+1)$-arc $[w.\beta]$ to its two successors

is true.

This question has become rather long, and I have surely missed a definition of something. Everything in gray, can be found in Biggs 1974, on pages 112-115. I have understood the proof of Theorem 17.5, but the proof of Proposition 18.1 uses some arguments, which are non-obvious to me.

share|improve this question

1 Answer 1

up vote 1 down vote accepted

In the end, I found the missing argument. It is a rather simple one, but I did not see it at first. In fact, both of the questions I raised about the proof, needed the same argument, and I found out, that the statement:

In fact, if $\beta_{t-1},u_1,u_2$ are the vertices adjacent to $\beta_t$, then $f$ must interchange $u_1$ and $u_2$

is essential to the proof. The reason that the above statement is correct, is that an automorphism on a graph, preserves neighbors. That is, for a graph $X$; then if $v,u \in V(X)$ are neighbors, and $\pi$ is an automorphism on $X$, then $\pi(v),\pi(u)$ are also neighbors.

Using this knowledge of automorphisms on graphs, we can see, that if $f$ fixes $\beta_t$, but does not fix both of the successors of $[\beta]$ $u_1$ and $u_2$, then $f$ has to interchange $u_1$ and $u_2$ to preserve the neighborhood of $\beta_t$.

The same argument applies for the part:

Since $X$ is $t$-transitive there is an automorphism $h \in Aut(X)$ taking the $t$-arc $(w,\beta_0,\ldots,\beta_{t-1})$ to $[\beta]$, and we may suppose the notation chosen so that $h(\beta_t) = u_1$. Then $h$ and $fh$ are automorphisms of $X$ taking the $(t+1)$-arc $[w.\beta]$ to its two successors

since we now know that $u_1$ is a neighbor of $\beta_t$, even after applying $h$.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.