Bulletin of the
Korean Mathematical Society
BKMS

ISSN(Print) 1015-8634 ISSN(Online) 2234-3016

Article

HOME ALL ARTICLES View

Bull. Korean Math. Soc. 2021; 58(1): 31-46

Online first article January 7, 2021      Printed January 31, 2021

https://doi.org/10.4134/BKMS.b191050

Copyright © The Korean Mathematical Society.

Sharp conditions for the existence of an even $[a,b]$-factor in a graph

Eun-Kyung Cho, Jong Yoon Hyun, Suil O, Jeong Rye Park

Hankuk University of Foreign Studies; Konkuk University; The State University of New York, Korea; Pusan National University

Abstract

Let $a$ and $b$ be positive integers, and let $V(G)$, $\delta(G)$, and $\sigma_2(G)$ be the vertex set of a graph $G$, the minimum degree of $G$, and the minimum degree sum of two non-adjacent vertices in $V(G)$, respectively. An even $[a,b]$-factor of a graph $G$ is a spanning subgraph $H$ such that for every vertex $v \in V(G)$, $d_H(v)$ is even and $a \le d_H(v) \le b$, where $d_H(v)$ is the degree of $v$ in $H$. Matsuda conjectured that if $G$ is an $n$-vertex 2-edge-connected graph such that $n \ge 2a+b+\frac{a^2-3a}b - 2$, $\delta(G) \ge a$, and $\sigma_2(G) \ge \frac{2an}{a+b}$, then $G$ has an even $[a,b]$-factor. In this paper, we provide counterexamples, which are highly connected. Furthermore, we give sharp sufficient conditions for a graph to have an even $[a,b]$-factor. For even $an$, we conjecture a lower bound for the largest eigenvalue in an $n$-vertex graph to have an $[a,b]$-factor.

Keywords: Even $[a,b]$-factor, edge-connectivity, vertex-connectivity, spectral radius

MSC numbers: Primary 05C70, 05C40, 05C50

Supported by: Eun-Kyung Cho was supported by NRF-2020R1I1A1A0105858711. Jong Yoon Hyun was supported by supported by NRF-2017R1D1A1B05030707. Suil O was supported by NRF-2020R1F1A1A01048226 and NRF-2018K2A9A2A06020345. Jeong Rye Park was supported by NRF-2018R1D1A1B07048197