TOPICS
Search

Harary Graph


HararyGraph

The Harary graph H_(k,n) is a particular example of a k-connected graph with n graph vertices having the smallest possible number of edges. The smallest number of edges possible, as achieved by the Harary graph H_(k,m), is [kn/2], where [x] is the ceiling function (Harary 1962; Skiena 1990, p. 179; West 2000, p. 151).

Harary graphs are implemented in the Wolfram Language as HararyGraph[k, n].

When n or k is even, H_(k,n) is a circulant graph. H_(n-1,n) is the complete graph K_n (Skiena 1990, p. 180).


See also

k-Connected Graph

Explore with Wolfram|Alpha

References

Baudon, O.; Bensmail, J.; and Sopena, E. "Partitioning Harary Graphs Into Connected Subgraphs Containing Prescribed Vertices." Preprint. 20 Apr 2012. http://hal.inria.fr/docs/00/68/99/34/PDF/bbs2012.pdf.Bondy, J. A. and Murty, U. S. R. Graph Theory with Applications. New York: North Holland, 1976.Harary, F. "The Maximum Connectivity of a Graph." Proc. Nat. Acad. Sci. USA 48, 1142-1146, 1962.Skiena, S. "Harary Graphs." §5.1.6 in Implementing Discrete Mathematics: Combinatorics and Graph Theory with Mathematica. Reading, MA: Addison-Wesley, pp. 179-180, 1990.West, D. B. Introduction to Graph Theory, 2nd ed. Englewood Cliffs, NJ: Prentice-Hall, pp. 150-151, 2000.

Referenced on Wolfram|Alpha

Harary Graph

Cite this as:

Weisstein, Eric W. "Harary Graph." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/HararyGraph.html

Subject classifications