TOPICS
Search

Haar Graph

DOWNLOAD Mathematica NotebookDownload Wolfram Notebook
HaarGraphs

A Haar graph H(n) 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.

HaarGraph69

For example, consider the Haar graph H(69), which is isomorphic to the Heawood graph. In binary, 69=1000101_2, which has 7 binary digits, so the encoded bipartite graph has seven "black" (u_0, ..., u_6) vertices and seven "white" vertices (v_0, ..., v_6). Since the positions of 1's in the binary representation (taking the first digit as position 0) are 0, 4, and 6, v_i is taken to be adjacent to vertices u_(0+i), u_(4+i), and u_(6+i) for i=0 to 6 where addition is taken mod 7 (Pisanski and Randić 2000). This gives edges

(u_0,v_0),(u_4,v_0),(u_6,v_0) (u_1,v_1),(u_5,v_1),(u_0,v_1) (u_2,v_2),(u_6,v_2),(u_1,v_2) (u_3,v_3),(u_0,v_3),(u_2,v_3) (u_4,v_4),(u_1,v_4),(u_3,v_4) (u_5,v_5),(u_2,v_5),(u_4,v_5) (u_6,v_6),(u_3,v_6),(u_5,v_6),
(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 2k vertices is 2^(k-1) and there are 2^(k-1) (possibly isomorphic) Haar graphs on 2k vertices. More specifically, the vertex count of H(n) is

|H(n)|=2(1+|_log_2n_|)
(2)
=2|_1+log_2n_|.
(3)

A graph (on n>2 vertices) is a Haar graph iff it admits an automorphism with precisely two orbits of equal size (and no other orbit), both of which are independent vertex sets (Hladnik et al. 2002).

The number of 1's in the binary representation of n in a Haar graph H(n) 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 Y_(2n) and the Möbius-Kantor graph GP(8,3) (Hladnik et al. 2002).

H(n) with odd n is Hamiltonian (Hladnik et al. 2002).

Special cases are summarized in the following table.

ngraph
12-path graph
3square graph
7utility graph
11cubical graph
37Franklin graph
43quartic transitive graph 23
69Heawood graph
75quartic transitive graph 31
133Möbius-Kantor graph
139quartic transitive graph 40
141quartic transitive graph 48
17116-quintic graph 1
261cubic transitive graph 20
267quartic transitive graph 57
293quartic transitive graph 67
517cubic transitive graph 25
525Bouwer graph B(2,4,5)
1029cubic transitive graph 32
1099incidence graph (11,5,2)
2053cubic transitive graph 36
2057cubic transitive graph 35
2065cubic transitive graph 38
4101cubic transitive graph 47
4105Foster graph 026A
4137(4,6)-cage
8197cubic transitive graph 52
8201cubic transitive graph 51
16389cubic transitive graph 59
16393cubic transitive graph 60
16401cubic transitive graph 62
16402cubic transitive graph 58
17051incidence graph (15,7,3)
32773cubic transitive graph 68
32777cubic 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 K_(n,n), crossed prism graphs, crown graphs K_2 square K_n^_, even cycle graphs C_(2n), disjoint graph unions of even cycles kC_(2n), Knödel graphsKnoedel graphsKnoedel Graph, ladder rung graphs nP_2, odd Möbius ladders M_(2n+1), and even prism graphs Y_(2n). Special classes are summarized in the following table.

graph classOEISHaar index
complete bipartite graph K_(n,n)A0002252^n-1
2n-crossed prism graphA0000002^(2n+1)+2^n+1
n-crown graphA0550103·2^(n-2)-1
2n-cycle graphA0000512^(n-1)+1
nC_4A0075821/2(2^n+4^n)
nC_6A0813421/2(2^n+8^n)
n-ladder rung graphA0000792^(n-1)
(2n+1)-Möbius ladderA0000002^(2n)+3
2n-prism graphA0000002^(2n-1)+3

In general, the graph union of k copies of the cycle graph C_(2n) has Haar index (2^n+2^(kn))/2.

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 n such that the nth composition in standard order is a co-necklace (cf. eis333764). The following table summarizes all possible Haar numbers for some small graphs.

graphHaar numbers
6-cycle graph5, 6
8-cycle graph9, 12
cubical graph11, 13, 14
10-cycle graph17, 18, 20, 24
5-Möbius ladder19, 21, 22, 25, 26, 28
5-crown graph23, 27, 29, 30
12-cycle graph33, 48
2C_634, 40
6-prism graph35, 49, 56
Franklin graph37, 38, 41, 44, 50, 52

The numbers of nonisomorphic Haar graphs on n=2, 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 n are implemented in the Wolfram Language as GraphData[{"Haar", n}].

See also

Bipartite Graph, Knödel Graph, Regular Graph, Zero-Symmetric Graph

Explore with Wolfram|Alpha

References

Hladnik, M.; Marušič, D.; and Pisanski, T. "Cyclic Haar Graphs." Disc. Math. 244, 137-153, 2002.Pisanski, T. and Randić, M. "Bridges between Geometry and Graph Theory." In Geometry at Work: A Collection of Papers Showing Applications of Geometry (Ed. C. A. Gorini). Washington, DC: Math. Assoc. Amer., pp. 174-194, 2000.Sloane, N. J. A. Sequences A000079/M1129, A000225/M2655, A000051/M0717, A007582/M2849, A055010, A081342, A137706, A333764, and A357000 in "The On-Line Encyclopedia of Integer Sequences."

Referenced on Wolfram|Alpha

Haar Graph

Cite this as:

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

Subject classifications