Trivalent graph isomorphism problem

This article describes a decision problem from or related to graph theory. The problem is mentioned in this wiki due to its close relation with computational and decision problems in computational group theory

Description

Given data

We are given two graphs $X_{1}=(V_{1},E_{1})$ and $X_{2}=(V_{2},E_{2})$, with the promise that both of them are trivalent (viz the degree of every $v\in V_{i}$ is bounded by 3).

Goal

We are required to determine whether $X_{1}$ and $X_{2}$ are isomorphic as graphs.

Solution

Variant for which we solve the problem

The variant of the trivalent graph isomorphism problem that we solve here is the following: Given a trivalent graph $X$, and an edge $e$ of $X$, find a small generating set for $Aut_{e}(X)$, viz the graph automorphisms of $X$ which fix the edge $e$.

Here's how the trivalent graph isomorphism problem reduces to the edge-fixing trivalent graph automorphism problem. Take the two graphs $X_{1}$ and $X_{2}$. Fix a $v\in V(X_{1})$. For each $w\in V(X_{2})$, consider the graph

PLACEHOLDER FOR INFORMATION TO BE FILLED IN: [SHOW MORE]

One of the people editing this page intended to fill in this information at a later stage, but hasn't gotten around to doing it yet. If you see this placeholder for a long time, file an error report at the error reporting page.