Hofman Graph

Hofman graphs are parameterized by two integers and are typically denoted

${\displaystyle H(n,k)}$

where:

• ${\displaystyle n}$ denotes the number of vertices in the outer structure of an associated outline graph,
• ${\displaystyle k}$ denotes the step size (distance) controlling how outer vertices connect to inner components.

The construction is inspired by generalized Petersen graphs, but differs in that the inner structure may consist of multiple disconnected components and that outer–inner connections are mediated by special connector subgraphs called H-connections.

The first stage of the construction produces smaller graphs called outline Hofman graphs, denoted

${\displaystyle oH(n,k)}$

Outline graphs consist of:

• an outer cycle-like structure,
• one or more inner components (often odd cycles such as triangles),
• connector vertices between outer and inner parts.

Instead of connecting the outer and inner parts directly, Hofman introduced a connector vertex that forces any Hamiltonian traversal to alternate between outer and inner regions. This alternation constraint can prevent the existence of Hamiltonian paths or cycles depending on the parity and number of inner components.

Examples of outline Hofman graphs:

More information Graph image, Description ...

Graph image	Description
	Hamiltonian path follows vertices: 17, 11, 5, 0, 6, 12, 14, 8, 2, 1, 7, 13, 15, 9, 3, 4, 10, 16
	After third triangle is added to the inner structure the Hamiltonian path requires at leas one edge to be added to the graph
	The inner structure consists of three squares, therefore a Hamiltonian cycle may be constructed
	In this case the inner structure has a form of a star, it is possible to construct a Hamiltonian path connecting all vertices but not Hamiltonian cycle
	The inner structure consists of four triangles, therefore the graph requires at least two edges to be added to construct a Hamiltonian path

Close

To obtain large benchmark graphs with uniform degree and connectivity, Hofman introduced a balanced H-connection replacing the simple connector.

In the balanced construction, each H-connection is replaced by a fixed 15-vertex subgraph that preserves the Hamiltonian alternation constraint while ensuring that the resulting graph is regular. In the resulting graphs, every vertex has degree 4.

The comparison between H-connectors of the outline graph and full graph:

More information H-connection for outline graph, H-connection for full graph ...

H-connection for outline graph	H-connection for full graph

Close

The connector has the same properties from the perspective of a Hamilton path construction - if the flow does not alternate between the inner and outer structure, the middle vertice will be impossible to connect.

When the balanced connector is used throughout the outline, the resulting Hofman graphs are typically:

• 4-regular (all vertices have degree 4),
• 4-connected (in the intended construction),
• scalable to arbitrarily large size.

For example, the graph ${\displaystyle H(12,4)}$ contains ${\displaystyle 12\cdot 15=180}$ vertices.

A central purpose of the Hofman graph family is that Hamiltonian properties are controlled by construction. Depending on the parameters and the chosen inner components, a Hofman graph may:

• contain a Hamiltonian cycle,
• contain a Hamiltonian path but no Hamiltonian cycle,
• contain neither a Hamiltonian path spanning all vertices nor a Hamiltonian cycle.

In addition, for many instances the construction yields the minimum number of edges required to be added to obtain Hamiltonicity.

For example:

• ${\displaystyle H(12,3)}$ contains a Hamiltonian cycle,
• ${\displaystyle H(12,5)}$ contains a Hamiltonian path but no Hamiltonian cycle,
• ${\displaystyle H(12,4)}$ contains neither a Hamiltonian path spanning all vertices nor a Hamiltonian cycle.

Hofman introduced a scaling method for constructing large TSP benchmark instances from Hofman graphs by embedding them into a weighted complete graph.

The method adds two external vertices:

• a designated start vertex, and
• a designated end vertex,

and assigns low cost to edges inside the Hofman subgraph and very high cost to all other edges. This forces optimal tours to traverse the Hofman subgraph in a prescribed manner. Because the number of required "expensive" edges can be derived from the Hamiltonicity properties of the underlying Hofman graph, the optimal tour value can be computed analytically for large instances.^[1]

This technique can be extended by concatenating multiple Hofman graphs into layered structures, producing instances with hundreds or thousands of vertices while preserving known optimal costs.

The Hofman graph family was introduced as part of a counterexample to a proposed polynomial-size linear programming formulation for the TSP by Diaby et al.

Diaby's approach attempted to model valid TSP tours using flow-like variables and constraints. Hofman constructed a Hofman-based benchmark instance for which the true optimal TSP cost is known, while the LP relaxation yields a strictly smaller objective value. This demonstrates the existence of feasible LP solutions that do not correspond to valid tours ("phantom solutions").^[1]

This use case supports broader concerns that polynomial-size linear programs cannot fully characterize the TSP polytope without additional proof, consistent with earlier arguments in the literature.^[2]

The following table lists example instances described by Hofman.

More information , ...

Selected Hofman graphs and their Hamiltonian properties

Graph	Outline vertices	Total vertices	Hamiltonian cycle	Hamiltonian path
${\displaystyle H(6,2)}$	18	90	No (1 edge needed)	Yes
${\displaystyle H(9,3)}$	27	135	No (2 edges needed)	No (1 edge needed)
${\displaystyle H(12,4)}$	36	180	No (3 edges needed)	No (2 edges needed)
${\displaystyle H(8,2)}$	24	150	Yes	Yes
${\displaystyle H(12,2)}$	36	180	Yes	Yes
${\displaystyle H(12,3)}$	36	180	Yes	Yes
${\displaystyle H(8,3)}$	24	120	No (1 edge needed)	Yes
${\displaystyle H(12,5)}$	36	180	No (1 edge needed)	Yes
${\displaystyle H(15,5)}$	45	225	No (4 edges needed)	No (3 edges needed)
${\displaystyle H(18,6)}$	54	270	No (5 edges needed)	No (4 edges needed)

Close

The Hofman graph family is inspired by generalized Petersen graphs such as the classical Petersen graph, but differs in several ways:

• The inner structure may consist of multiple disconnected components.
• Outer–inner links are mediated by H-connections rather than direct edges.
• Hamiltonian properties are controlled explicitly rather than being incidental.
• Large balanced instances are obtained by systematic substitution of connectors.

Unlike the Petersen graph, which is a well-known hypohamiltonian graph, Hofman graphs can be constructed to be Hamiltonian, non-Hamiltonian, or to lack Hamiltonian paths.

• Hamiltonian path
• Hamiltonian cycle
• Travelling salesman problem
• NP-completeness
• Generalized Petersen graph
• Petersen graph
• Meredith graph