hnm_harary_graph

hnm_harary_graph(n, m, create_using=None)

Return the Harary graph with given numbers of nodes and edges.

The Harary graph \(H_{n, m}\) is the graph that maximizes node connectivity with \(n\) nodes and \(m\) edges.

This maximum node connectivity is known to be \(\lfloor 2m/n \rfloor\). [1]

Parameters:

n: integer

The number of nodes the generated graph is to contain.

m: integer

The number of edges 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_{n, m}\).

See also

hkn_harary_graph

Notes

This algorithm runs in \(O(m)\) time. The implementation follows [2].

References

[1]

F. T. Boesch, A. Satyanarayana, and C. L. Suffel, “A Survey of Some Network Reliability Analysis and Synthesis Results,” Networks, pp. 99-107, 2009.

[2]

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