Polynomially determine if a graph is (s, 3)-supereulerian
Polynomially determine if a graph is (s, 3)-supereulerian
复制标题
多项式确定图是否是 (s, 3)-超欧拉图
DOI：
10.1016/j.disc.2021.112601
复制
发表时间：
2021-12
影响因子：
0.8
通讯作者：
Hong-Jian Lai
中科院分区：
文献类型：
--
作者：
Wei Xiong;Sulin Song;Hong-Jian Lai
对整数s≥ 0和t≥ 0，图G是（s，t）-超欧勒图，如果对任意不交边集X，Y ∈ E（G），|X| ≤ s且|Y| ≤ t，G有一个包含X且避开Y的生成闭迹。Pulleyblank在1979年证明了判定一个图是否是（0，0）-超欧勒图，即使是平面图，也是NP-完全的。本文研究了使得每个j（s，t）-边连通图都是（s，t）-超欧莱雅图的最小整数j（s，t）的值，证明了当0≤ s≤ 1时，j（s，t）={max <${4，t+ 2};当（s，t）∈ {（2，2），（3，1）}时，j（s，t）∈{（2，0），（2，1），（3，0）}，5，s+ t+ 1−（− 1）s 2，如果s≥ 2且s+ t≥ 5。作为应用，我们得到了当t≥ 3时（s，t）-超欧勒图的边连通性的一个刻画，并证明了当t≥ 3时，存在一个多项式时间算法来判定一个图是否是（s，t）-超欧勒图.
For integers s≥ 0 and t≥ 0, a graph G is (s, t)-supereulerian if for any disjoint edge sets X, Y⊆ E (G) with| X|≤ s and| Y|≤ t, G has a spanning closed trail that contains X and avoids Y. Pulleyblank in 1979 showed that determining whether a graph is (0, 0)-supereulerian, even when restricted to planar graphs, is NP-complete. We investigate the value of the smallest integer j (s, t) such that every j (s, t)-edge-connected graph is (s, t)-supereulerian, and show that j (s, t)={max{4, t+ 2} if 0≤ s≤ 1, or (s, t)∈{(2, 0),(2, 1),(3, 0)}, 5 if (s, t)∈{(2, 2),(3, 1)}, s+ t+ 1−(− 1) s 2 if s≥ 2 and s+ t≥ 5. As applications, we obtain a characterization of (s, t)-supereulerian graphs when t≥ 3 in terms of edge-connectivities, and show that when t≥ 3, there exists a polynomial time algorithm to determine if a graph is (s, t)-supereulerian.
登录
查看更多内容
4 边连通图的可折叠子图
影响因子：
1.1
作者：
Ran Gu;Hong-Jian Lai;Yanting Liang;Zhengke Miao;Meng Zhang
通讯作者：
Meng Zhang
DOI：
10.1016/j.dam.2013.08.041
发表时间：
2014
期刊：
Discret. Appl. Math.
影响因子：
--
作者：
Jinquan Xu;Zhi-Hong Chen;H. Lai;Meng Zhang
通讯作者：
Jinquan Xu;Zhi-Hong Chen;H. Lai;Meng Zhang
DOI：
--
发表时间：
2013
期刊：
--
影响因子：
--
作者：
H. Lai;Yehong Shao
通讯作者：
H. Lai;Yehong Shao
DOI：
10.1016/s0012-365x(00)00070-4
发表时间：
2001-03
期刊：
Discret. Math.
影响因子：
--
作者：
H. Lai
通讯作者：
H. Lai
DOI：
10.1002/jgt.3190010115
发表时间：
1977-03
期刊：
J. Graph Theory
影响因子：
--
作者：
F. Boesch;C. Suffel;R. Tindell
通讯作者：
F. Boesch;C. Suffel;R. Tindell