Sharp conditions for the existence of an even $[a,b]$-factor in a graph
1
조회
0
다운로드
2
인용
0
참고문헌
키워드
초록
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.
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.
참고문헌 (19)
- B. Bollobás, "Regular factors of regular graphs", Journal of Graph Theory, 9(1), pp.97~103 (1985), Wiley[DOI]
- Y. Egawa, "Recent studies in graph theory", pp.96~105 (1989), Vishwa
- Xiaofeng Gu, "Regular factors and eigenvalues of regular graphs", European Journal of Combinatorics, 42, pp.15~25 (2014), Elsevier BV[DOI]
- Tadashi Iida, "An ore-type condition for the existence ofk-factors in graphs", Graphs and Combinatorics, 7(4), pp.353~361 (1991), Springer Science and Business Media LLC[DOI]
- P Katerinis, "Minimum degree of a graph and the existence ofk-factors", Proceedings of the Indian Academy of Sciences - Section A, 94(2-3), pp.123~127 (1985), Springer Science and Business Media LLC[DOI]
- -factor in regular graphs from eigenvalues, "Discrete Mathematics", 2020, 111906~, pp.Elsevier BV, 10.1016[DOI]
- -Factor in Graph, "Graphs and Combinatorics", 2013, 1051~1057, pp.Springer Science and Business Media LLC, 10.1007[DOI]
- -factors in graphs, "Australas. J. Combin", 2003, 139~147
- -factors in graphs, "Discussiones Mathematicae Graph Theory", 2004, 431~441, pp.Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Gora, 10.7151[DOI]
- L. Lovász, "The factorization of graphs. II", Acta Mathematica Academiae Scientiarum Hungaricae, 23(1-2), pp.223~246 (1972), Springer Science and Business Media LLC[DOI]
- H. Lu, "Regular factors of regular graphs from eigenvalues", Electron. J. Combin, 17 (2010)
- Hongliang Lu, "Regular Graphs, Eigenvalues and Regular Factors", Journal of Graph Theory, 69(4), pp.349~355 (2012), Wiley[DOI]
- -odd factors, "Linear Algebra Appl", 2010, 750~757, 10.1016[DOI]
- -factors in graphs, "Discrete Math", 2005, 51~61, pp.Elsevier BV, 10.1016[DOI]
- -factors in regular graphs, "Submitted"
- -factors in graphs, "Discussiones Mathematicae Graph Theory", 2017, 797~809, pp.Faculty of Mathematics, Computer Science and Econometrics, University of Zielona Gora, 10.7151[DOI]
- W. T. Tutte, "The factors of graphs", Canad. J. Math, 4, pp.314~328 (1952)[DOI]
- "Graph factors", Combinatorica, 1(1), pp.79~97 (1981), Springer Science and Business Media LLC[DOI]
- O. Veblen, "An application of modular equations in analysis situs", Ann. of Math, 14(1-4), pp.86~94 (1912)[DOI]