Man page - nauty-cubhamg(1)

Packages contains this manual

Package:  nauty
apt-get install nauty

Manuals in package:
• nauty-biplabg(1)
• nauty-delptg(1)
• nauty-productg(1)
• nauty-dretodot(1)
• nauty-newedgeg(1)
• nauty-listg(1)
• nauty-countg(1)
• nauty-underlyingg(1)
• nauty-ranlabg(1)
• nauty-addptg(1)
• nauty-pickg(1)
• nauty-directg(1)
• nauty-genrang(1)
• nauty-dimacs2g(1)
• nauty-dretog(1)
• nauty-hamheuristic(1)
• nauty-genktreeg(1)
• nauty-labelg(1)
• nauty-assembleg(1)
• nauty-gentourng(1)
• nauty-amtog(1)
• nauty-genquarticg(1)
• nauty-subdivideg(1)
• nauty-multig(1)
• dreadnaut(1)
• nauty-addedgeg(1)
• nauty-converseg(1)
• nauty-copyg(1)
• nauty-nbrhoodg(1)
• nauty-complg(1)
• nauty-uniqg(1)
• nauty-deledgeg(1)
• nauty-ancestorg(1)
• nauty-linegraphg(1)
• nauty-vcolg(1)
• nauty-sumlines(1)
• nauty-genposetg(1)
• nauty-catg(1)
• nauty-genspecialg(1)
• nauty-genbg(1)
• nauty-shortg(1)
• nauty-cubhamg(1)
• nauty-geng(1)
• nauty-edgetransg(1)
• nauty-watercluster2(1)
• nauty-checks6(1)
• nauty-countneg(1)
• nauty-showg(1)
• nauty-gentreeg(1)
• nauty-bliss2dre(1)
• nauty-twohamg(1)
• nauty-planarg(1)
• nauty-ransubg(1)
Documentations in package:
• nauty

Manual

NAUTY-CUBHAMG

NAME
SYNOPSIS
DESCRIPTION

---

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

Graphs that are not hamiltonian, or not solved, are written out 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

---