## table of contents

NAUTY-CUBHAMG(1) | Nauty Manual | NAUTY-CUBHAMG(1) |

# NAME¶

nauty-cubhamg - find hamiltonian cycles in subcubic graphs

# SYNOPSIS¶

**cubhamg** [*-#*] [*-v|-V*]
[*-n#-#|-y#-#|-i|-I|-o|-O|-x|-e|-E*] [*-b|-t*] [*infile
*[*outfile*]]

# DESCRIPTION¶

- 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**

November 2022 | nauty 2.8.6 |