hkn_harary_graph

hkn_harary_graph(k, n, create_using=None)

Return 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 \(\lceil kn/2 \rceil\) [1].

Parameters:

k: integer

The node connectivity of the generated graph.

n: integer

The number of nodes the generated graph is to contain.

create_usingNetworkX graph constructor, optional (default=nx.Graph)

Graph type to create. If graph instance, then cleared before populated.

Returns:

NetworkX graph

The Harary graph \(H_{k, n}\).

See also

hnm_harary_graph

Notes

This algorithm runs in \(O(kn)\) time. The implementation follows [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.