Supereulerian Graphs with Constraints on the Matching Number and Minimum Degree
- PDF / 317,673 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 100 Downloads / 222 Views
(0123456789().,-volV)(0123456789().,-volV)
ORIGINAL PAPER
Supereulerian Graphs with Constraints on the Matching Number and Minimum Degree Mansour J. Algefari1 • Hong-Jian Lai2 Received: 20 January 2020 / Revised: 20 January 2020 / Accepted: 17 August 2020 Ó Springer Japan KK, part of Springer Nature 2020
Abstract A graph is supereulerian if it has a spanning eulerian subgraph. We show that a connected simple graph G with n ¼ jVðGÞj 2 and dðGÞ a0 ðGÞ is supereulerian if and only if G 6¼ K1;n1 if n is even or G 6¼ K2;n2 if n is odd. Consequently, every connected simple graph G with dðGÞ a0 ðGÞ has a hamiltonian line graph. Keywords Supereulerian graph Hamiltonian line graph Matching Minimum degree Contraction
1 Introduction We follow Bondy and Murty [5] for terms and notation, unless otherwise stated. Graphs considered in this paper are finite and loopless, but multiple edges are allowed. As in [5], jðGÞ; j0 ðGÞ, dðGÞ, aðGÞ and a0 ðGÞ denote the connectivity, the edge connectivity, the minimum degree, the stability number (also called the independence number), and the matching number of a graph G, respectively. Let G be a graph and let O(G) denote the set of odd degree vertices of G. If G is connected and OðGÞ ¼ ;, then G is an Eulerian graph. Thus a graph G is Eulerian if and only if G has a closed trail traversing every edge exactly once. A graph is supereulerian if it has a spanning eulerian subgraph. In particular, K1 is both eulerian and supereulerian. The study of supereulerian graphs was initiated in [4]. Pulleyblank [15] showed that, even within planar graphs, it is NP-complete to determine if a & Hong-Jian Lai [email protected] Mansour J. Algefari [email protected] 1
Department of Management and Humanities Sciences, Community College, Qassim University, Buraydah, Kingdom of Saudi Arabia
2
Department of Mathematics, West Virginia University, Morgantown, WV 26506, USA
123
Graphs and Combinatorics
graph is supereulerian. For the literature on supereulerian graphs, see the survey of Catlin [7] and its updates in [8, 14]. If X EðGÞ, the contraction G/X is the graph obtained from G by identifying the two ends of each edge in X and then deleting the resulting loops. If H is a subgraph of G, we write G/H for G/E(H). We define G=; ¼ G=K1 ¼ G. Chva´tal and Erdo¨s proved a classic result on hamiltonian graph, revealing an interesting property of using a relationship between connectivity and independence number of a graph to predict the hamiltonicity of the graph. Theorem 1.1 (Chva´tal and Erdo¨s, [9]) If jðGÞ aðGÞ, then G is hamiltonian. There have been results following Theorem 1.1 and using similar relations involving edge-connectivity, stability number or matching number to predict supereulerianicity of a graph, as seen in [1, 10, 13, 16] and [17], among others. The theorem below presents some of these results. Theorem 1.2 Each of the following holds. (i)
(ii) (iii)
(iv)
([13]) Let G be a graph with j0 ðGÞ 2 and a0 ðGÞ 2. Then G is supereulerian if and only if G is not contrac
Data Loading...
