Note

This documents the development version of NetworkX. Documentation for the current release can be found here.

# networkx.generators.harary_graph.hkn_harary_graph¶

hkn_harary_graph(k, n, create_using=None)[source]

Returns the Harary graph with given node connectivity and node number.

The Harary graph $$H_{k,n}$$ is the graph that minimizes the number of edges needed with given node connectivity $$k$$ and node number $$n$$.

This smallest number of edges is known to be ceil($$kn/2$$) 1.

Parameters
• k (integer) – The node connectivity of the generated graph

• n (integer) – The number of nodes the generated graph is to contain

• create_using (NetworkX graph constructor, optional Graph type) – to create (default=nx.Graph). If graph instance, then cleared before populated.

Returns

The Harary graph $$H_{k,n}$$.

Return type

NetworkX graph

Notes

This algorithm runs in $$O(kn)$$ time. It is implemented by following the Reference 2.

References

1

Weisstein, Eric W. “Harary Graph.” From MathWorld–A Wolfram Web Resource. http://mathworld.wolfram.com/HararyGraph.html.

2

Harary, F. “The Maximum Connectivity of a Graph.” Proc. Nat. Acad. Sci. USA 48, 1142-1146, 1962.