<abstract xmlns="http://www.w3.org/1999/xhtml">Let <italic>G</italic> be a graph, and let <italic>k, r</italic> be nonnegative integers with <italic>k</italic> ≥ 2. A <italic>k</italic>-factor of <italic>G</italic> is a spanning subgraph <italic>F</italic> of <italic>G</italic> such that <italic>dF</italic>(<italic>x</italic>) = <italic>k</italic> for each <italic>x</italic> ∈ <italic>V</italic> (<italic>G</italic>), where <italic>dF</italic>(<italic>x</italic>) denotes the degree of <italic>x</italic> in <italic>F</italic>. For <italic>S</italic> ⊆ <italic>V</italic> (<italic>G</italic>), <italic>NG</italic>(<italic>S</italic>) = ∪<italic>x</italic>∊<italic>S</italic><italic>NG</italic>(<italic>x</italic>). The binding number of <italic>G</italic> is defined by <italic>bind</italic><inline-formula><alternatives><math xmlns:mml="http://www.w3.org/1998/Math/MathML"><mrow><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>=</mo><mtext>min</mtext><mo>{</mo><mfrac><mrow><mo>|</mo><mstyle><mrow><msub><mrow><mi>N</mi></mrow><mrow><mi>G</mi></mrow></msub></mrow></mstyle><mo>(</mo><mi>S</mi><mo>)</mo><mo>|</mo></mrow><mstyle><mrow><mo>|</mo><mi>S</mi><mo>|</mo></mrow></mstyle></mfrac><mo>:</mo><mi>∅</mi><mo>≠</mo><mi>S</mi><mo>⊂</mo><mi>V</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>,</mo><msub><mrow><mi>N</mi></mrow><mrow><mi>G</mi></mrow></msub><mrow><mo>(</mo><mi>S</mi><mo>)</mo></mrow><mo>≠</mo><mi>V</mi><mrow><mo>(</mo><mi>G</mi><mo>)</mo></mrow><mo>}</mo></mrow></math><tex-math>$\begin{array}{}
(G) = {\rm{min }}\{ \frac{{|{N_G}(S)|}}{{|S|}}:\emptyset \ne S \subset V(G),{N_G}(S) \ne V(G)\}
\end{array}$</tex-math></alternatives></inline-formula>. In this paper, we obtain a binding number and neighborhood condition for a graph to have a <italic>k</italic>-factor excluding a given <italic>r</italic>-factor. This result is an extension of the previous results.</abstract>

Let G be a graph, and let k, r be nonnegative integers with k ≥ 2. A k-factor of G is a spanning subgraph F of G such that dF(x) = k for each x ∈ V (G), where dF(x) denotes the degree of x in F. For S ⊆ V (G), NG(S) = ∪x∊SNG(x). The binding number of G is defined by bind(G)=min{|NG(S)||S|:∅≠S⊂V(G),NG(S)≠V(G)}$\begin{array}{}
(G) = {\rm{min }}\{ \frac{{|{N_G}(S)|}}{{|S|}}:\emptyset  \ne S \subset V(G),{N_G}(S) \ne V(G)\}
\end{array}$. In this paper, we obtain a binding number and neighborhood condition for a graph to have a k-factor excluding a given r-factor. This result is an extension of the previous results.

A sufficient condition for the existence of a <italic>k</italic>-factor excluding a given <italic>r</italic>-factor

Jiangsu University of Science and Technology

Applied Mathematics and Nonlinear Sciences

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

A sufficient condition for the existence of a -factor excluding a given -factor

Let G be a graph, and let k, r be nonnegative integers with k ≥ 2. A k-factor of G is a spanning subgraph F of G such that dF(x) = k for each x ∈ V (G), where...

A sufficient condition for the existence of a k-factor excluding a given r-factor

Pubblicato online: 10 gen 2017

Pagine: 13 - 20

Ricevuto: 04 nov 2016

Accettato: 10 gen 2017

DOI: https://doi.org/10.21042/AMNS.2017.1.00002

Parole chiave
graph, binding number, neighborhood, -factor

© 2017 Sizhong Zhou, Lan Xu and Yang Xu, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

A sufficient condition for the existence of a k-factor excluding a given r-factor

Pubblicato online: 10 gen 2017

Pagine: 13 - 20

Ricevuto: 04 nov 2016

Accettato: 10 gen 2017

DOI: https://doi.org/10.21042/AMNS.2017.1.00002

Parole chiavegraph, binding number, neighborhood, -factor

© 2017 Sizhong Zhou, Lan Xu and Yang Xu, published by Sciendo

This work is licensed under the Creative Commons Attribution-NonCommercial-NoDerivatives 3.0 License.

Parole chiave
graph, binding number, neighborhood, -factor