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
See also
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.