Graph theory MOC

Graph automorphism

Let Γ be a general graph. A graph automorphism 𝜙 ∈Aut⁡(Γ) is a bijection V⁡(𝜙) :V⁡(Γ) →V⁡(Γ) which leaves the adjacency matrix of Γ fully invariant, graph i.e.

|Γ(𝑣,𝑤)|=|Γ(𝜙(𝑣),𝜙(𝑤))|

for all 𝑣,𝑤 ∈V⁡(Γ). Clearly Aut⁡(Γ) forms a group under composition, which in addition to an action on V⁡(Γ) has an action on A⁡(Γ). A digraph is called

• vertex-transitive iff Aut⁡(Γ) acts transitively on V⁡(Γ);
• arc-transitive iff Aut⁡(Γ) acts transitively on A⁡(Γ).

Results

• Every arc-transitive digraph is an orbital digraph

---

tidy | en | SemBr