nauty-cubhamg - find hamiltonian cycles in subcubic graphs
cubhamg [-#] [-v|-V]
[-n#-#|-y#-#|-i|-I|-o|-O|-x|-e|-E] [-b|-t] [infile
[outfile]]
- cubhamg : Find hamiltonian cycles in sub-cubic graphs
- infile is the name of the input file in graph6/sparse6 format outfile is
the name of the output file in the same format
- stdin and stdout are the defaults for infile and outfile
- The output file will have a header if and only if the input file
does.
- Optional switches:
- -#
- A parameter useful for tuning (default 100)
- -v
- Report nonhamiltonian graphs and noncubic graphs
- -V
- .. in addition give a cycle for the hamiltonian ones
- (with -c, give count for each input)
- -n#-#
- If the two numbers are v and i, then the i-th edge
- out of vertex v is required to be not in the cycle. It must be that i=1..3
and v=0..n-1.
- -y#-#
- If the two numbers are v and i, then the i-th edge
- out of vertex v is required to be in the cycle. It must be that i=1..3 and
v=0..n-1.
- You can use any number of -n/-y switches to force edges. Out of
range first arguments are ignored. If -y and -n specify the
same edge, -y wins.
- -i
- Test + property: for each edge e, there is a hamiltonian
- cycle using e.
- -I
- Test ++ property: for each pair of edges e,e', there is
- a hamiltonian cycle which uses both e and e'.
- -o
- Test - property: for each edge e, there is a hamiltonian
- cycle avoiding e
- -O
- Test -- property: for each pair of nonadjacent edges e,e's,
- there is a hamiltonian cycle
avoiding both.
- Note that
- this is trivial unless the girth is at least 5.
- -x
- Test +- property: for each pair of edges e,e', there is
- a hamiltonian cycle which uses e but avoids e'.
- -e
- Test 3/4 property: for each edge e, at least 3 of the 4
- paths of length 3 passing through e lie on hamiltonian cycles.
- -E
- Test 3/4+ property: for each edge e failing the 3/4 property,
- all three ways of joining e to the rest of the graph are hamiltonian
avoiding e.
-T# Specify a timeout, being a limit on how many search
tree
- nodes are made.
- If the timeout occurs, the graph is
- written to the output as if it is nonhamiltonian.
-R# Specify the number of repeat attempts for each
stage.
- -F
- Analyze covering paths from 2 or 4 vertices of degree 2.
- -b
- Require biconnectivity
- -t
- Require triconnectivity (note: quadratic algorithm)
- -c
- Count hamiltonian cycles, output count for each graph.
- -V, -n and -y can also be used. No graphs are
output.
-y, -n, -#, -R and -T are ignored
for -i, -I, -x, -o, -e, -E,
-F