NAUTY-CUBHAMG
Section: Nauty Manual (1)
Updated: January 2023
Index
Return to Main Contents
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
Index
- NAME
-
- SYNOPSIS
-
- DESCRIPTION
-
This document was created by
man2html,
using the manual pages.
Time: 12:53:33 GMT, April 28, 2024