<p><strong>Notation:</strong>
Let <span class="math-container">$X = (V,E)$</span> be graph, <span class="math-container">$e = (v_1, v_2) $</span> an edge of <span class="math-container">$X$</span>.
The vertex set <span class="math-container">$V_k$</span> be the set of vertices of distance <span class="math-container">$k$</span> from <span class="math-container">$e$</span>, and let <span class="math-container">$h$</span> be the height of <span class="math-container">$X$</span>.</p>
<p>According to definition of <span class="math-container">$V_k$</span>,
<span class="math-container">$V= V_0 \cup V_1\cup \dots \cup V_h$</span> and <span class="math-container">$V_{(h+1)}= \emptyset$</span>. Let,  subset <span class="math-container">$E_k$</span> of edges of <span class="math-container">$X(0 \leq k \leq h)$</span> is defined as-</p>
<p><span class="math-container">$E_k = \{ (u,w) | u \in  V_k, w \in  V_ k \cup V_{(k+1)} \}.$</span></p>
<p>The subgraph <span class="math-container">$X_i$</span> is defined as-</p>
<p><span class="math-container">$X_k= (V_0 \cup V_1 \cup \dots  \cup V_k,  E_0 \cup E_1\cup  \dots \cup  E_{(k-1)})$</span></p>
<p>For example,  <span class="math-container">$X_2 =(V_0 \cup V_1 \cup V_2,  E_0 \cup E_1)$</span></p>
<p><span class="math-container">$\text{Aut}_e(X)$</span> is the automorphism group of  graph <span class="math-container">$X$</span> where <span class="math-container">$e$</span> is fixed. If <span class="math-container">$B$</span> is a generating set of <span class="math-container">$\text{Aut}_e(X_k)$</span> , we write <span class="math-container">$\langle B \rangle = \text{Aut}_e(X_k)$</span>, for example,   it is clear that  <span class="math-container">$\text{Aut}_e(X_0)=\langle(v_1,v_2)\rangle$</span> where <span class="math-container">$ (v_1,v_2)$</span> is a permutation of vertices <span class="math-container">$v_1,  v_2$</span> of <span class="math-container">$X$</span>.</p>
<p><strong>Principle</strong>
Constructing generating set of automorphism group of <span class="math-container">$X$</span> is a <strong>GI</strong> (graph isomorphism) complete problem [1]. So, if we can compute generating set of automorphism group of <span class="math-container">$X$</span> (which has bounded valance in polynomial time), we can solve GI in polynomial time. So, we wish to determine <span class="math-container">$\text{Aut}_e(X)$</span>.</p>
<p><strong>Technique:</strong></p>
<p>We will construct <span class="math-container">$X_0, X_1..... X_h$</span>. For each, <span class="math-container">$X_k$</span> we will construct <span class="math-container">$\text{Aut}_e(X_{(k)})$</span></p>
<p>Note that, a permutation of <span class="math-container">$\text{Aut}_e(X_{(k) })$</span>may be
extended to an automorphism of <span class="math-container">$\text{Aut}_e(X_{(k+1)})$</span>.</p>
<p>So, generators of  <span class="math-container">$\text{Aut}_e(X_{(k+1)})$</span> can be obtained from generators for <span class="math-container">$\text{Aut}_e(X_{k})$</span>.</p>
<p>To construct  generator, structure-type of <span class="math-container">$E_k$</span>  is manipulated. The structure-type of <span class="math-container">$E_k$</span>   can be divided into finite classes.  For example, in the trivalent case, there are only six type  (only five of those cases can actually occur).</p>
<p>We will classify the edges in <span class="math-container">$E_k$</span>  into types and will group them into families . This helps to create a number of unique labels.</p>
<p>For a fixed valence,  the number of labels is small. At this point, we use the concept of setwise-stabilizers  to find  permutations which acts on particular label. In the process, we find the generator of <span class="math-container">$\text{Aut}_e(X_{(k) })$</span>. Then, we use  the generator of<span class="math-container">$\text{Aut}_e(X_{(k) })$</span> to find the generator of <span class="math-container">$\text{Aut}_e(X_{(k+1) })$</span>, as stated earlier. Proceeding in this manner, we obtain, <span class="math-container">$\text{Aut}_e(X)$</span>.</p>

CC BY-SA 3.0
2016-06-01T18:35:58.627Z
[1]Mathon, Rudolf. ,A note on the graph isomorphism counting problem, Inform. Process. Lett. 8 (1979), no. 3, 131–132.
Michael
CC BY-SA 4.0
2024-06-13T21:56:05.880Z
Thanks for this amazing answer ^_^
Daniel Donnelly
CC BY-SA 4.0
2024-06-13T22:05:03.447Z
Question.  $\text{Aut}_e(X)$ is the set of all automorphisms that happen to fix the two endpoints of $e$ and thus $e$ itself?
Daniel Donnelly
CC BY-SA 4.0
2024-06-13T22:43:32.177Z
You mentioned "unique labels" - can this algorithm be adapted to output a canonical form for a bounded-valence multidigraph?
Daniel Donnelly
CC BY-SA 4.0
2016-06-01T18:35:24.863Z
2024-06-17T08:00:38.870Z
2024-06-17T08:00:38.870Z
Michael
<p>The algorithm for bounded-degree graph isomorphism is so closely tied to (permutation) group theory that I doubt there is an introduction that uses groups "only gently." However, you might consult <a href="http://people.cs.uchicago.edu/~laci/students/codenotti.pdf" rel="nofollow">Paolo Codenotti's Ph.D. thesis</a> for more complete background. He doesn't cover bounded-degree graph isomorphism exactly, but covers the tools needed for it (and the rest of the thesis is about bounded-rank hypergraphs, extending the best known algorithm for general graph isomorphism to the bounded-rank hypergraph case).</p>

<p>You may also find the book <a href="http://dx.doi.org/10.1007/3-540-11493-9" rel="nofollow">Group-Theoretic Algorithms and Graph Isomorphism</a> useful, as it covers most of the background necessary (Chapter 2, "Basic Concepts", is 47 pages) and is a much more leisurely exposition than most of the published papers on the topic.</p>

CC BY-SA 3.0
2012-08-23T04:00:43.573Z
2015-12-24T14:30:21.030Z
2015-12-24T14:30:21.030Z
Joshua Grochow
<p>I am reading about classes of graphs for which Graph Isomorphism ($GI$) is in $P$. One of such case is graphs of bounded valence (maximum over degree of each vertex) as explained <a href="http://www.sciencedirect.com/science/article/pii/0022000082900095" rel="nofollow">here</a>. But I found it too abstract. I would be thankful if anybody can suggest me some references of expository nature. I do not have strong background in group theory, so I would prefer papers which use group theory in a gentle way (my background is in CS).</p>

CC BY-SA 3.0
2012-08-21T17:56:09.823Z
I do not have the book (unfortunately), but _The Graph Isomorphism Problem: Its Structural Complexity_ by Johannes Köbler, Uwe Schöning, and Jacobo Torán may contain a proof for the case of bounded degree.  You might want to check it.
Tsuyoshi Ito
CC BY-SA 3.0
2012-08-23T02:05:42.500Z
@TsuyoshiIto: While that's an excellent book that gives a good introduction to GI and to a fair bit of general structural complexity, it does not contain much (if anything) about the bounded degree case. I do not know of a gentle introduction to the bounded degree case, but it is so intimately tied with group theoretic methods that I doubt there is an exposition that uses group theory "only gently" (as requested by the OP).
Joshua Grochow
CC BY-SA 3.0
2016-02-15T16:54:08.107Z
I am keen to give an Overview, I will do that soon!
Michael
CC BY-SA 4.0
2024-06-13T22:07:11.453Z
I am also interested in this bounded-degree isomoprhism for bounded degree subgraph isomorphism searching of a small query graph in a large graph database, all of bounded degree.
Daniel Donnelly
<ds.algorithms><reference-request><graph-theory><graph-isomorphism>
Gentle introduction to graph isomorphism for bounded valance graphs
DurgaDatta
# Gentle introduction to graph isomorphism for bounded valance graphs

(Asked by: username_0 on 2012-08-21)

I am reading about classes of graphs for which Graph Isomorphism ($GI$) is in $P$. One of such case is graphs of bounded valence (maximum over degree of each vertex) as explained [here](http://www.sciencedirect.com/science/article/pii/0022000082900095). But I found it too abstract. I would be thankful if anybody can suggest me some references of expository nature. I do not have strong background in group theory, so I would prefer papers which use group theory in a gentle way (my background is in CS).

**Tags:** ds.algorithms, reference-request, graph-theory, graph-isomorphism
> **Comments:**
> **username_1**: I do not have the book (unfortunately), but _The Graph Isomorphism Problem: Its Structural Complexity_ by Johannes Köbler, Uwe Schöning, and Jacobo Torán may contain a proof for the case of bounded degree.  You might want to check it.  
> **username_2**: @TsuyoshiIto: While that's an excellent book that gives a good introduction to GI and to a fair bit of general structural complexity, it does not contain much (if anything) about the bounded degree case. I do not know of a gentle introduction to the bounded degree case, but it is so intimately tied with group theoretic methods that I doubt there is an exposition that uses group theory "only gently" (as requested by the OP).  
> **username_3**: I am keen to give an Overview, I will do that soon!  
> **username_4**: I am also interested in this bounded-degree isomoprhism for bounded degree subgraph isomorphism searching of a small query graph in a large graph database, all of bounded degree.  

---

## 2 answers

### Answer by username_2 on 2012-08-23. Score: 15 | Accepted answer

The algorithm for bounded-degree graph isomorphism is so closely tied to (permutation) group theory that I doubt there is an introduction that uses groups "only gently." However, you might consult [Paolo Codenotti's Ph.D. thesis](http://people.cs.uchicago.edu/~laci/students/codenotti.pdf) for more complete background. He doesn't cover bounded-degree graph isomorphism exactly, but covers the tools needed for it (and the rest of the thesis is about bounded-rank hypergraphs, extending the best known algorithm for general graph isomorphism to the bounded-rank hypergraph case).

You may also find the book [Group-Theoretic Algorithms and Graph Isomorphism](http://dx.doi.org/10.1007/3-540-11493-9) useful, as it covers most of the background necessary (Chapter 2, "Basic Concepts", is 47 pages) and is a much more leisurely exposition than most of the published papers on the topic.


---

### Answer by username_3 on 2016-06-01. Score: 3

**Notation:**
Let $X = (V,E)$ be graph, $e = (v\_1, v\_2) $ an edge of $X$.
The vertex set $V\_k$ be the set of vertices of distance $k$ from $e$, and let $h$ be the height of $X$.

According to definition of $V\_k$,
$V= V\_0 \cup V\_1\cup \dots \cup V\_h$ and $V\_{(h+1)}= \emptyset$. Let, subset $E\_k$ of edges of $X(0 \leq k \leq h)$ is defined as-

$E\_k = \{ (u,w) | u \in V\_k, w \in V\_ k \cup V\_{(k+1)} \}.$

The subgraph $X\_i$ is defined as-

$X\_k= (V\_0 \cup V\_1 \cup \dots \cup V\_k, E\_0 \cup E\_1\cup \dots \cup E\_{(k-1)})$

For example, $X\_2 =(V\_0 \cup V\_1 \cup V\_2, E\_0 \cup E\_1)$

$\text{Aut}\_e(X)$ is the automorphism group of graph $X$ where $e$ is fixed. If $B$ is a generating set of $\text{Aut}\_e(X\_k)$ , we write $\langle B \rangle = \text{Aut}\_e(X\_k)$, for example, it is clear that $\text{Aut}\_e(X\_0)=\langle(v\_1,v\_2)\rangle$ where $ (v\_1,v\_2)$ is a permutation of vertices $v\_1, v\_2$ of $X$.

**Principle**
Constructing generating set of automorphism group of $X$ is a **GI** (graph isomorphism) complete problem [1]. So, if we can compute generating set of automorphism group of $X$ (which has bounded valance in polynomial time), we can solve GI in polynomial time. So, we wish to determine $\text{Aut}\_e(X)$.

**Technique:**

We will construct $X\_0, X\_1..... X\_h$. For each, $X\_k$ we will construct $\text{Aut}\_e(X\_{(k)})$

Note that, a permutation of $\text{Aut}\_e(X\_{(k) })$may be
extended to an automorphism of $\text{Aut}\_e(X\_{(k+1)})$.

So, generators of $\text{Aut}\_e(X\_{(k+1)})$ can be obtained from generators for $\text{Aut}\_e(X\_{k})$.

To construct generator, structure-type of $E\_k$ is manipulated. The structure-type of $E\_k$ can be divided into finite classes. For example, in the trivalent case, there are only six type (only five of those cases can actually occur).

We will classify the edges in $E\_k$ into types and will group them into families . This helps to create a number of unique labels.

For a fixed valence, the number of labels is small. At this point, we use the concept of setwise-stabilizers to find permutations which acts on particular label. In the process, we find the generator of $\text{Aut}\_e(X\_{(k) })$. Then, we use the generator of$\text{Aut}\_e(X\_{(k) })$ to find the generator of $\text{Aut}\_e(X\_{(k+1) })$, as stated earlier. Proceeding in this manner, we obtain, $\text{Aut}\_e(X)$.

> **Comments:**
> **username_3**: [1]Mathon, Rudolf. ,A note on the graph isomorphism counting problem, Inform. Process. Lett. 8 (1979), no. 3, 131–132.  
> **username_4**: Thanks for this amazing answer ^_^  
> **username_4**: Question.  $\text{Aut}_e(X)$ is the set of all automorphisms that happen to fix the two endpoints of $e$ and thus $e$ itself?  
> **username_4**: You mentioned "unique labels" - can this algorithm be adapted to output a canonical form for a bounded-valence multidigraph?  

---

