Regular Honest Graphs, Isoperimetric Numbers, and Bisection of Weighted Graphs
Regular Honest Graphs, Isoperimetric Numbers, and Bisection of Weighted Graphs
复制标题
DOI：
10.1006/eujc.1998.0295
复制
发表时间：
1999-08
期刊：
影响因子：
--
通讯作者：
N. Alon;P. Hamburger;A. Kostochka
中科院分区：
文献类型：
--
作者：
N. Alon;P. Hamburger;A. Kostochka
图G的边完整性？(G)：=min{|S|+m(G？S)：S？e}，其中m(H)表示H的分支的最大阶数，如果图G的边完整性是最大可能的，即等于图的阶数，则称图G为诚实图。唯一诚实的2-正则图是3-、4-和5-圈。利普曼13证明了恰好存在20个诚实的三次图。本文利用Bollobas8.9，9的技巧证明了对于任意的k？6，几乎所有的k-正则图都是诚实的。另一方面，我们证明了只有有限多个4-正则诚实图。为了证明这一点，我们使用由Alon1引起的等周数的上界的加权版本。我们认为这个版本本身就很有趣。
The edge-integrity of a graph G isI? (G) :=min{| S | +m(G?S) : S?E }, where m(H) denotes the maximum order of a component of H. A graph G is calledhonest if its edge-integrity is the maximum possible; that is, equals the order of the graph. The only honest 2-regular graphs are the 3-, 4-, and 5-cycles. Lipman13proved that there are exactly twenty honest cubic graphs. In this paper we exploit a technique of Bollobas8,9to prove that for every k? 6, almost all k -regular graphs are honest. On the other hand, we show that there are only finitely many 4-regular honest graphs. To prove this, we use a weighted version of the upper bound on the isoperimetric number due to Alon1. We believe that this version is of interest by itself.