Sharp Ore-type conditions for the existence of an even $[4,b]$-factor in a graph
2
조회
0
다운로드
0
인용
0
참고문헌
키워드
초록
Let $a$ and $b$ be positive even integers. 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$. Let $\kappa(G)$ be the minimum size of a vertex set $S$ such that $G-S$ is disconnected or one vertex, and let $\sigma_2(G)=\min_{uv \notin E(G)}(d(u)+d(v))$. In 2005, Matsuda proved an Ore-type condition for an $n$-vertex graph satisfying certain properties to guarantee the existence of an even $[2,b]$-factor. In this paper, we prove that for an even positive integer $b$ with $b \ge 6$, if $G$ is an $n$-vertex graph such that $n \ge b+5$, $\kappa(G) \ge 4$, and $\sigma_2(G) \ge \frac{8n}{b+4}$, then $G$ contains an even $[4,b]$-factor; each condition on $n$, $\kappa(G)$, and $\sigma_2(G)$ is sharp.
Abstract
Let $a$ and $b$ be positive even integers. 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$. Let $\kappa(G)$ be the minimum size of a vertex set $S$ such that $G-S$ is disconnected or one vertex, and let $\sigma_2(G)=\min_{uv \notin E(G)}(d(u)+d(v))$. In 2005, Matsuda proved an Ore-type condition for an $n$-vertex graph satisfying certain properties to guarantee the existence of an even $[2,b]$-factor. In this paper, we prove that for an even positive integer $b$ with $b \ge 6$, if $G$ is an $n$-vertex graph such that $n \ge b+5$, $\kappa(G) \ge 4$, and $\sigma_2(G) \ge \frac{8n}{b+4}$, then $G$ contains an even $[4,b]$-factor; each condition on $n$, $\kappa(G)$, and $\sigma_2(G)$ is sharp.
참고문헌 (18)
- B. Bollobás, "Regular factors of regular graphs", J. Graph Theory, 9(1), pp.97~103 (1985)[DOI]
- $-factor in a graph, "대한수학회보", 2021, 31~46, pp.대한수학회, 10.4134[DOI]
- H. Fleischner, "Spanning Eulerian subgraphs, the splitting lemma, and Petersen’s the-orem", Discrete Math, 101(1-3), pp.33~37 (1992)[DOI]
- T. Gallai, "On factorisation of graphs", Acta Math. Acad. Sci. Hungar, 1, pp.133~153 (1950)[DOI]
- X. Gu, "Regular factors and eigenvalues of regular graphs", European J. Combin, 42, pp.15~25 (2014)[DOI]
- D. Kim, "Eigenvalues and parity factors in graphs", ~
- -factor in regular graphs from eigenvalues, "Discrete Math", 2020, 111906~, https:
- -factors in graphs, "Australas. J. Com-bin", 2003, 139~147
- -factors in graphs, "Discuss. Math. Graph Theory", 2004, 431~441, https:
- H. Liu, "A degree condition for a graph to have (a, b)-parity factors", Discrete Math, 341(1), pp.244~252 (2018)[DOI]
- L. Lovász, "The factorization of graphs. II", Acta Math. Acad. Sci. Hungar, 23(1-2), pp.223~246 (1972)
- H. Lu, "Regular graphs, eigenvalues and regular factors", J. Graph Theory, 69(4), pp.349~355 (2012)[DOI]
- -odd factors, "Linear Algebra Appl", 2010, 750~757, https:
- -factors in graphs, "Dis-crete Math", 2005, 51~61, https:
- ‐factors in regular graphs, "Journal of Graph Theory", 2021, 458~469, pp.Wiley, https:
- S. O, "Matching and edge-connectivity in regular graphs", European J. Combin, 32(2), pp.324~329 (2011)[DOI]
- O. Ore, "Note on Hamilton circuits", Amer. Math. Monthly, 67, pp.55~ (1960)[DOI]
- D. B. West, "Introduction to Graph Theory" (1996), Prentice Hall, Inc