# relabelGraph -- applies a vertex invariant based refinement to a graph

## Synopsis

• Usage:
L' = relabelGraph(L, i, a)
L' = relabelGraph(L, i)
L' = relabelGraph L
T = relabelGraph(S, i, a)
T = relabelGraph(S, i)
T = relabelGraph S
H = relabelGraph(G, i, a)
H = relabelGraph(G, i)
H = relabelGraph G
• Inputs:
• L, a list, a list of graphs in various formats
• S, , a graph encoded in either Sparse6 or Graph6 format
• G, ,
• i, an integer, a choice of invariant to order by ($0 \leq i \leq 15$, default is $0$)
• a, an integer, a non-negative argument passed to nauty, (default is $3$)
• Outputs:
• L', a list, a list of graphs isomorphic to $S$
• T, , a graph isomorphic to $S$ encoded in either Sparse6 or Graph6 format
• H, , a graph isomorphic to $G$

## Description

This method applies one of sixteen vertex invariant based refinements to a graph. See the nauty documentation for a more complete description of each and how the argument $a$ is used.

The sixteen vertex invariants are: \break \ \ \ \ $i = 0$: none,
\ \ \ \ $i = 1$: twopaths,
\ \ \ \ $i = 2$: adjtriang(K),
\ \ \ \ $i = 3$: triples,
\ \ \ \ $i = 4$: quadruples,
\ \ \ \ $i = 5$: celltrips,
\ \ \ \ $i = 6$: cellquads,
\ \ \ \ $i = 7$: cellquins,
\ \ \ \ $i = 8$: distances(K),
\ \ \ \ $i = 9$: indsets(K),
\ \ \ \ $i = 10$: cliques(K),
\ \ \ \ $i = 11$: cellcliq(K),
\ \ \ \ $i = 12$: cellind(K),
\ \ \ \ $i = 13$: adjacencies,
\ \ \ \ $i = 14$: cellfano, and
\ \ \ \ $i = 15$: cellfano2.

 i1 : R = QQ[a..e]; i2 : G = graph {a*e, e*c, c*b, b*d, d*a}; i3 : relabelGraph G o3 = Graph{edges => {{a, b}, {a, c}, {b, d}, {c, e}, {d, e}}} ring => R vertices => {a, b, c, d, e} o3 : Graph

Note that on most small graphs, all sixteen orderings produce the same result.

• relabelBipartite -- relabels a bipartite graph so all vertices of a given class are contiguous

## Ways to use relabelGraph :

• "relabelGraph(Graph)"
• "relabelGraph(Graph,ZZ)"
• "relabelGraph(Graph,ZZ,ZZ)"
• "relabelGraph(List)"
• "relabelGraph(List,ZZ)"
• "relabelGraph(List,ZZ,ZZ)"
• "relabelGraph(String)"
• "relabelGraph(String,ZZ)"
• "relabelGraph(String,ZZ,ZZ)"

## For the programmer

The object relabelGraph is .