Harary Graph

The Harary graph is a particular example of a k-connected graph with graph vertices having the smallest possible number of edges. The smallest number of edges possible, as achieved by the Harary graph , is , where 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 or is even, is a circulant graph. is the complete graph (Skiena 1990, p. 180).

Explore with Wolfram|Alpha

More things to try:

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

Harary Graph

See also

Explore with Wolfram|Alpha

References

Referenced on Wolfram|Alpha

Cite this as:

Subject classifications