DMGT

ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

https://doi.org/10.7151/dmgt

Discussiones Mathematicae Graph Theory

IMPACT FACTOR 2018: 0.741

SCImago Journal Rank (SJR) 2018: 0.763

Rejection Rate (2017-2018): c. 84%

Discussiones Mathematicae Graph Theory

Article in press


Authors:

M. Kano, Z. Yan

Title:

Strong Tutte type conditions and factors of graphs

Source:

Discussiones Mathematicae Graph Theory

Received: 2017-10-26, Revised: 2018-06-26, Accepted: 2018-06-26, https://doi.org/10.7151/dmgt.2158

Abstract:

Let $odd(G)$ denote the number of odd components of a graph $G$ and $k\ge 2$ be an integer. We give sufficient conditions using $odd(G-S)$ for a graph $G$ to have an even factor. Moreover, we show that if a graph $G$ satisfies $odd(G-S) \le \max\{1, (1/k) |S|\}$ for all $S\subset V(G)$, then $G$ has a $(k-1)$-regular factor for $k\ge 3$ or an $\mathbf{H}$-factor for $k=2$, where we say that $G$ has an $\mathbf{H}$-factor if for every labeling $h:V(G)\to \{\mbox{red, blue}\}$ with $#\{v\in V(G):f(v)=\mbox{red}\}$ even, $G$ has a spanning subgraph $F$ such that $\deg_F(x)=1$ if $h(x)=\mbox{red}$ and $\deg_F(x)\in \{0,2\}$ otherwise.

Keywords:

factor of graph, even factor, regular factor, Tutte type condition

PDF
Close