哈尔图

哈尔图 是一个 二分 正则 图，由 正整数 索引，并通过循环相邻顶点的简单 二进制 编码获得。哈尔图可能是 连通 或 非连通 的。

例如，考虑哈尔图 ，它同构于 Heawood 图。在二进制中，，它有 7 个二进制数字，因此编码的 二分图 有七个“黑色”（, ..., ）顶点和七个“白色”顶点（, ..., ）。由于二进制表示中 1 的位置（将第一个数字作为位置 0）是 0、4 和 6， 被认为与顶点 , , 和 相邻，对于 到 6，其中加法是模 7 运算（Pisanski 和 Randić 2000）。 这给出了边

(1)

从而得到上面图示的图。

根据定义，哈尔图似乎既是 顶点传递 的，也是 无三角形 的。

在 个顶点上的哈尔图的最小索引是 ，并且在 个顶点上有 个（可能同构的）哈尔图。更具体地说， 的 顶点计数 是

			(2)
			(3)

一个图（在 个顶点上，）是哈尔图 当且仅当 它允许一个自同构，该自同构恰好有两个大小相等的轨道（且没有其他轨道），这两个轨道都是 独立顶点集（Hladnik等人 2002）。

哈尔图 中 的 二进制 表示中 1 的数量等于相应（正则）图的 顶点度。

（非空）循环图 是哈尔图 当且仅当 它是 二分图。 唯一作为 广义 Petersen 图 的哈尔图是偶数 棱柱图 和 Möbius-Kantor 图 （Hladnik等人 2002）。

奇数 的 是 哈密顿图（Hladnik等人 2002）。

特殊情况总结在下表中。

	图
1	2-路径图
3	方图
7	效用图
11	立方图
37	富兰克林图
43	四次传递图 23
69	Heawood 图
75	四次传递图 31
133	Möbius-Kantor 图
139	四次传递图 40
141	四次传递图 48
171	16-五次图 1
261	三次传递图 20
267	四次传递图 57
293	四次传递图 67
517	三次传递图 25
525	Bouwer 图
1029	三次传递图 32
1099	关联图 (11,5,2)
2053	三次传递图 36
2057	三次传递图 35
2065	三次传递图 38
4101	三次传递图 47
4105	Foster 图 026A
4137	(4,6)-笼
8197	三次传递图 52
8201	三次传递图 51
16389	三次传递图 59
16393	三次传递图 60
16401	三次传递图 62
16402	三次传递图 58
17051	关联图 (15,7,3)
32773	三次传递图 68
32777	三次传递图 67
32786	(16,7)-广义 Petersen 图

作为哈尔图的图族包括二分非空循环图，完全二分图 , 交叉棱柱图, 冠图 , 偶数 圈图 , 偶数 圈 的不相交图并集 , Knödel 图, 梯子图 , 奇数 Möbius 梯子 , 和偶数 棱柱图 。特殊类总结在下表中。

图类	OEIS	哈尔指数
完全二分图	A000225
-交叉棱柱图	A000000
-冠图	A055010
-圈图	A000051
	A007582
	A081342
-梯子图	A000079
-Möbius 梯子	A000000
-棱柱图	A000000

一般来说，图并集 的 个 圈图 副本具有哈尔指数 。

给出唯一非同构图的最小索引由 1、2、3、4、5、7、8、9、10、11、15、16、17、19、...（OEIS A137706）给出。 这些索引都对应于 的值，使得标准顺序中的第 个组合是一个共项链（参见 eis333764）。 下表总结了一些小图的所有可能的哈尔数。

图	哈尔数
6-圈图	5, 6
8-圈图	9, 12
立方图	11, 13, 14
10-圈图	17, 18, 20, 24
5-Möbius 梯子	19, 21, 22, 25, 26, 28
5-冠图	23, 27, 29, 30
12-圈图	33, 48
	34, 40
6-棱柱图	35, 49, 56
富兰克林图	37, 38, 41, 44, 50, 52

在 、4、... 个节点上的非同构哈尔图的数量是 1、2、3、5、5、12、9、22、21、44、29、157、73、...（OEIS A357000）。

在 Wolfram Language 中，小而特殊值的 的哈尔图实现为GraphData["Haar", n].