HararyGraph

The minimum-edge k-connected graph on n vertices (Harary, 1962).

✓ checked against that system · ! checked, with disagreements (hover a chip)Wolfram LanguageHararyGraph!↗

HararyGraph(k, n)EdgeCount = ceil(k n / 2), minimum vertex degree >= k.

SageMathenumeratio_graph(graphs.HararyGraph(k, n))

Typed signatures

Type	Package	Applies
(integer, integer) -> value	combinatorics	always

Domain: Collections

Details

• k even: the circulant CirculantGraph(n, {1, …, k/2}). k odd, n even: that circulant plus the n/2 diametrically-opposite edges. k odd, n odd: that circulant plus vertex 1 joined to BOTH floor(n/2)+1 and ceil(n/2)+1 (1 alone ends up with degree k + 1 -- the one vertex n*k being odd forces to take the remainder), plus i <-> i + ceil(n/2) (1-based) giving everyone else their kth edge.
• Kernel-verified against Wolfram 15 for the odd/odd case: HararyGraph(3, 7) gives exactly the 7-cycle plus {1-4, 1-5, 2-6, 3-7}. The even-k and (odd-k, even-n) cases follow the standard, unambiguous Harary construction and were not separately kernel-checked.

Examples

Basic #

live ↗

In$\mathrm{EdgeCount}(\mathrm{HararyGraph}(4, 7))$Out$14$

The 7-cycle plus {1-4, 1-5, 2-6, 3-7} -- kernel-verified

live ↗

In$\mathrm{EdgeList}(\mathrm{HararyGraph}(3, 7))$Out$\bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(2, 3), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(4, 5), \mathrm{UndirectedEdge}(5, 6), \mathrm{UndirectedEdge}(6, 7), \mathrm{UndirectedEdge}(7, 1), \mathrm{UndirectedEdge}(1, 4), \mathrm{UndirectedEdge}(1, 5), \mathrm{UndirectedEdge}(2, 6), \mathrm{UndirectedEdge}(3, 7)\bigr\rbrack$

Scope #

A 3-connected Harary graph on five vertices, with the fewest edges that connectivity allows

live ↗

In$\mathrm{HararyGraph}(3, 5)$Out$\mathrm{Graph}(\bigl\lbrack1, 2, 3, 4, 5\bigr\rbrack, \bigl\lbrack\mathrm{UndirectedEdge}(1, 2), \mathrm{UndirectedEdge}(2, 3), \mathrm{UndirectedEdge}(3, 4), \mathrm{UndirectedEdge}(4, 5), \mathrm{UndirectedEdge}(5, 1), \mathrm{UndirectedEdge}(1, 3), \mathrm{UndirectedEdge}(1, 4), \mathrm{UndirectedEdge}(2, 5)\bigr\rbrack)$

Applications #

Every vertex of this 4-connected graph on six vertices sits within distance 2 of all others

live ↗

In$\mathrm{Map}(\operatorname{\_1}↦\mathrm{VertexEccentricity}(\mathrm{HararyGraph}(4, 6), \operatorname{\_1}), \mathrm{VertexList}(\mathrm{HararyGraph}(4, 6)))$Out$\bigl\lbrack2, 2, 2, 2, 2, 2\bigr\rbrack$

About

Examples	4
Checked against	Wolfram Language 3 agree1 differSageMath 1 agree1 differ
Crosswalk	Wolfram LanguageSageMath

Implementation

mappedsagepackages/oracle/src/mappings.ts

See also: CirculantGraph, IsConnectedGraph