Publications

On [formula omitted]-supereulerian graphs with linear degree bounds.

Faculty Author(s): Zhan, Mingquan
Student Author(s): -
Department: MATH
Publication: Discrete Mathematics
Year: 2021
Abstract: 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 [J. Graph Theory, 3 (1979) 309-310] showed that determining whether a graph is (0 , 0) -supereulerian, even when restricted to planar graphs, is NP-complete. Settling an open problem of Bauer, Catlin in [J. Graph Theory, 12 (1988) 29–45] showed that every simple graph G on n vertices with δ (G) ≥ n 5 − 1 , when n is sufficiently large, is (0 , 0) -supereulerian or is contractible to K 2 , 3. We prove the following for any nonnegative integers s and t. (i) For any real numbers a and b with 0 < a < 1 , there exists a family of finitely many graphs F (a , b ; s , t) such that if G is a simple graph on n vertices with κ ′ (G) ≥ t + 2 and δ (G) ≥ a n + b , then either G is (s , t) -supereulerian, or G is contractible to a member in F (a , b ; s , t). (ii) Let ℓ K 2 denote the connected loopless graph with two vertices and ℓ parallel edges. If G is a simple graph on n vertices with κ ′ (G) ≥ t + 2 and δ (G) ≥ n 2 − 1 , then when n is sufficiently large, either G is (s , t) -supereulerian, or for some integer j with t + 2 ≤ j ≤ s + t , G is contractible to a j K 2 . [ABSTRACT FROM AUTHOR] Copyright of Discrete Mathematics is the property of Elsevier B.V. and its content may not be copied or emailed to multiple sites or posted to a listserv without the copyright holder's express written permission. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)
Link: On [formula omitted]-supereulerian graphs with linear degree bounds.