A Haar graph 
is a bipartite regular
indexed by a positive integer and obtained by
a simple binary encoding of cyclically adjacent
vertices. Haar graphs may be connected or
disconnected.
For example, consider the Haar graph 
, which is isomorphic
to the Heawood graph. In binary, 
, which has 7 binary digits, so the encoded bipartite
graph has seven "black" (
, ..., 
) vertices and seven "white"
vertices (
, ..., 
). Since the positions of 1's in the binary representation
(taking the first digit as position 0) are 0, 4, and 6, 
is taken to be adjacent to vertices 
, 
, and 
for 
to 6 where addition is taken mod 7 (Pisanski and Randić
2000). This gives edges
 |
(1)
|
resulting in the graph illustrated above.
By definition, Haar graphs appear to be both vertex-transitive and triangle-free.
The smallest index of a Haar graph on 
vertices is 
and there are 
(possibly isomorphic)
Haar graphs on 
vertices. More specifically, the vertex
count of 
is
 |  |  |
(2)
|
 |  |  |
(3)
|
A graph with at least one graph edge and 
vertices is a Haar graph iff
it admits an automorphism with precisely two group orbits
of equal size (and no other orbit), both of which are independent
vertex sets (Hladnik et al. 2002). Equivalently, among graphs
with at least one graph edge and more than two vertices,
Haar graphs are precisely the bicirculant graphs
whose two cyclic orbits are independent vertex
sets.
The number of 1's in the binary representation of 
in a Haar graph 
equals the vertex degree
of the corresponding (regular) graph.
A (non-empty) circulant graph is a Haar graph iff it is bipartite. The
only Haar graphs that are generalized Petersen
graphs are even prism graphs 
and the Möbius-Kantor
graph 
(Hladnik et al. 2002).
with odd 
is Hamiltonian
(Hladnik et al. 2002).
Special cases are summarized in the following table.
 | graph |
| 1 | 2-path graph |
| 3 | square graph |
| 7 | utility graph |
| 11 | cubical graph |
| 37 | Franklin graph |
| 43 | quartic transitive graph 23 |
| 69 | Heawood graph |
| 75 | quartic transitive graph 31 |
| 133 | Möbius-Kantor graph |
| 139 | quartic transitive graph 40 |
| 141 | quartic transitive graph 48 |
| 171 | 16-quintic graph 1 |
| 261 | cubic transitive graph 20 |
| 267 | quartic transitive graph 57 |
| 293 | quartic transitive graph 67 |
| 517 | cubic transitive graph 25 |
| 525 | Bouwer
graph  |
| 1029 | cubic transitive graph 32 |
| 1099 | incidence graph (11,5,2) |
| 2053 | cubic transitive graph 36 |
| 2057 | cubic transitive graph 35 |
| 2065 | cubic transitive graph 38 |
| 4101 | cubic transitive graph 47 |
| 4105 | Foster graph 026A |
| 4137 | (4,6)-cage |
| 8197 | cubic transitive graph 52 |
| 8201 | cubic transitive graph 51 |
| 16389 | cubic transitive graph 59 |
| 16393 | cubic transitive graph 60 |
| 16401 | cubic transitive graph 62 |
| 16402 | cubic transitive graph 58 |
| 17051 | incidence graph (15,7,3) |
| 32773 | cubic transitive graph 68 |
| 32777 | cubic transitive graph 67 |
| 32786 | (16,7)-generalized Petersen graph |
Families of graphs that are Haar graphs include bipartite non-empty circular graphs, complete
bipartite graphs 
,
crossed prism graphs, crown
graphs 
,
even cycle graphs 
, disjoint graph unions
of even cycles 
, Knödel graphs,
ladder rung graphs 
, odd Möbius ladders 
, and even prism
graphs 
.
Special classes are summarized in the following table.
| graph class | OEIS | Haar index |
complete
bipartite graph  | A000225 |  |
 -crossed
prism graph |  | |
 -crown graph | A055010 |  |
 -cycle graph | A000051 |  |
 | A007582 |  |
 | A081342 |  |
 -ladder rung graph | A000079 |  |
 -Möbius ladder |  | |
 -prism graph |  |
In general, the graph union of 
copies of the cycle graph 
has Haar index 
.
The smallest indices giving a unique nonisomorphic graph are given by 1, 2, 3, 4, 5, 7, 8, 9, 10, 11, 15, 16,
17, 19, ... (OEIS A137706). These indices all
correspond to values of 
such that the 
th
composition in standard order is a co-necklace (cf. eis333764). The following table
summarizes all possible Haar numbers for some small graphs.
| graph | Haar numbers |
| 6-cycle graph | 5, 6 |
| 8-cycle graph | 9, 12 |
| cubical graph | 11, 13, 14 |
| 10-cycle graph | 17, 18, 20, 24 |
| 5-Möbius ladder | 19, 21, 22, 25, 26, 28 |
| 5-crown graph | 23, 27, 29, 30 |
| 12-cycle graph | 33, 48 |
 | 34, 40 |
| 6-prism graph | 35, 49, 56 |
| Franklin graph | 37, 38, 41, 44, 50, 52 |
The numbers of nonisomorphic Haar graphs on 
, 4, ... nodes
are 1, 2, 3, 5, 5, 12, 9, 22, 21, 44, 29, 157, 73, ... (OEIS A357000).
Haar graphs for small and special values of 
are implemented in the Wolfram
Language as GraphData[
"Haar", n
].
