Generator of graphs

This repository contains tools and resources for generating, drawing and exporting diverse families of graphs in several formats (DIMACS, LaTeX, etc).

Usage

./graphs.py name parameters [options]

Options:

• -o path | -output path: exports the graph to a file. Default: standard output.
• -f name | -format name: selects the format of the graph: c, dimacs, haskell, javascript, prolog, python, numpy. Default: numpy.

Families

• Complete graphs
• Friendship graphs
• Generalized Petersen graphs
• Johnson graphs
• Windmill graphs

Complete graphs

A complete graph is an undirected graph in which every pair of distinct vertices is connected by a unique edge.

./graphs.py complete n

where:

• n > 0

K(10)	K(11)	K(12)

The file complete.tex defines a LaTeX command \complete{n} for drawing any complete graph with TikZ.

Friendship graphs

A friendship graph F(n) is a planar undirected graph with 2n+1 vertices and 3n edges, constructed by joining n copies of the cycle graph C(3) with a common vertex.

./graphs.py friendship n

where:

• n > 0

F(3)	F(4)	F(5)

The file friendship.tex defines a LaTeX command \friendship{n} for drawing any friendship graph (for n > 1) with TikZ.

Generalized Petersen graphs

The generalized Petersen graphs are a family of cubic graphs formed by connecting the vertices of a regular polygon to the corresponding vertices of a star polygon. They include the Petersen graph and generalize one of the ways of constructing the Petersen graph.

./graphs.py petersen n k

where:

• n > 0
• k > 0
• k < n/2

GP(5, 1)	GP(5, 2)	GP(7, 1)

The file petersen.tex defines a LaTeX command \petersen{n}{k} for drawing any generalized Petersen graph with TikZ.

Johnson graphs

Johnson graphs are a special class of undirected graphs defined from systems of sets. The vertices of the Johnson graph J(n, k) are the k-element subsets of an n-element set, where two vertices are adjacent when the intersection of the two vertices (subsets) contains (k-1)-elements.

./graphs.py johnson n k

where:

• n > 0
• k > 0
• k < n

J(4, 1)	J(4, 2)

Windmill graphs

The windmill graph Wd(k,n) is an undirected graph constructed for k > 1 and n > 1 by joining n copies of the complete graph K(k) at a shared universal vertex.

./graphs.py windmill k n

where:

• k > 1
• n > 1

Wd(4, 6)	Wd(9, 5)

The file windmill.tex defines a LaTeX command \windmill{k}{n} for drawing any windmill graph with TikZ.