Binding Number and Fractional k-Factors of Graphs

Renying Chang

Business School, Shanghai Dianji University, Shanghai, China.

DOI: 10.4236/jamp.2024.127154                

Abstract

In this paper, we consider the relationship between the binding number and the existence of fractional k-factors of graphs. The binding number of G is defined by Woodall as $bind\left(G\right)=\min \left\{\frac{\left|N_G\left(X\right)\right|}{\left|X\right|}:\varnothing \ne X\subseteq V\left(G\right)\right\}$ . It is proved that a graph G has a fractional 1-factor if $bind\left(G\right)\ge 1$ and has a fractional k-factor if $bind\left(G\right)\ge k-\frac{1}{k}$ . Furthermore, it is showed that both results are best possible in some sense.

Keywords

Binding Number, Fractional k-Factor, Fractional Matching, Independent Set, Covering Set

1. Introduction

All graphs considered in this paper are assumed to be infinite and simple. We refer the readers to [1] for the terminologies not defined here. Let G be a graph with vertex set $V\left(G\right)$ and edge set $E\left(G\right)$ . For $x\in V\left(G\right)$ , the degree of x in G is denoted by $d_G\left(x\right)$ . The minimum vertex degree of G is denoted by $\delta \left(G\right)$ . For any $S\subseteq V\left(G\right)$ , we denote by $N_G\left(S\right)$ the neighborhood set of S in G and we use $G\left[S\right]$ and $G-S$ to denote the subgraph of G induced by S and $V\left(G\right)-S$ , respectively. A subset S of $V\left(G\right)$ is called an independent set (a covering set) of G if every edge of G is incident with at most (at least) one vertex of S.

Let g and f be two integer-valued functions defined on $V\left(G\right)$ with $g\left(x\right)\le f\left(x\right)$ for any $x\in V\left(G\right)$ . A spanning subgraph F of G is called a $\left(g,f\right)$ -factor if $g\left(x\right)\le d_F\left(x\right)\le f\left(x\right)$ holds for any vertex $x\in V\left(G\right)$ . A $\left(g,f\right)$ -factor is called an $\left[a,b\right]$ -factor if $g\left(x\right)=a$ and $f\left(x\right)=b$ for any $x\in V\left(G\right)$ . An $\left[a,b\right]$ -factor is called a k-factor if $a=b=k$ .

Let $h:E\left(G\right)\to \left[0,1\right]$ be a function, and let $k\ge 1$ be an integer. If ${\displaystyle {\sum }_{e\ni x}h\left(e\right)}=k$ holds for each vertex $x\in V\left(G\right)$ , we call $G\left[F_h\right]$ a fractionalk-factor of G with indicator function h where $F_h=\left\{e\in E\left(G\right)|h\left(e\right)>0\right\}$ . A fractional 1-factor is also called a fractional perfect matching [2].

The binding number of G is defined by Woodall [3] as

$bind\left(G\right)=\min \left\{\frac{\left|N_G\left(X\right)\right|}{\left|X\right|}:\varnothing \ne X\subseteq V\left(G\right)\right\}$ . It is trivial by the definition that $bind\left(G\right)\ge c$ implies that for every subset $X\subseteq V\left(G\right)$ , we have either $N_G\left(X\right)=V\left(G\right)$ or $\left|N_G\left(X\right)\right|\ge c\left|X\right|$ . It is also obvious that if $bind\left(G\right)>1$ , then G is connected. Many authors have investigated the relationship between binding number and the existence of factors in graphs. For more information, please refer to [4]-[6]. We begin with some known results.

Anderson gave a sufficient condition for the existence of 1-factors.

Theorem 1.1. ([7]) If a graph G has even order and $bind\left(G\right)\ge \frac{4}{3}$ , then G has a 1-factor.

Woodall showed the relationship of the binding number and the existence of a Hamiltonian cycle in a graph. In [8] obtained the binding number condition for restricted matching extension in graphs.

Katerinis and Woodal [9] and Katerinis [10] found the minimum degree and binding number conditions for a graph to have k-factors. Zhou obtained the binding number condition for a graph to be ID-k-factor-critical [11].

[12] considered binding number and the existence of f-factors in graphs. The researchers discussed binding number and the existence of $\left(g,f\right)$ -factors in graphs [13] and binding number and the existence of $\left(g,f\right)$ -factors with prescribed properties in graphs [14]. The authors studied binding number and the existence of fractional $\left(g,f\right)$ -factor-critical in graphs [15]. Recently, the researchers considered binding number conditions and various factors ([16]-[18]).

In this paper, we consider the relationship between the binding number and the existence of fractional k-factors in G. Our main results are the following two theorems.

Theorem 1.2. Let G be a connected graph with $\left|V\left(G\right)\right|\ge 2$ , then G has a fractional perfect matching if $bind\left(G\right)\ge 1$ .

Theorem 1.3. Let $k\ge 2$ be an integer. A Graph G with $\left|V\left(G\right)\right|\ge k+1$ has a fractional k-factor if $bind\left(G\right)\ge k-\frac{1}{k}$ .

2. Preliminary Lemmas

Liu and Zhang gave a necessary and sufficient condition for a graph to have a fractional k-factor in [19].

Lemma 2.1. ([19]) Let $k\ge 1$ be an integer. A graph G has a fractional k-factor if and only if for any subset S of $V\left(G\right)$ ,

$k\left|T\right|-d_{G-S}\left(T\right)\le k\left|S\right|$

where $T=\left\{x\in V\left(G\right)-S|d_{G-S}\left(x\right)\le k-1\right\}$ .

In particular, for $k=1$ , Scheinermman obtained the following result.

Lemma 2.2. A graph G has a fractional perfect matching if and only if for any subset S of $V\left(G\right)$ ,

$i\left(G-S\right)\le \left|S\right|$

where $i\left(G-S\right)=\left\{x\in V\left(G\right)-S|d_{G-S}\left(x\right)=0\right\}$ .

We obtained the following result in [20].

Lemma 2.3. ([20]) Let G be a graph and $H=G\left[T\right]$ such that $d_G\left(x\right)=k-1$ for every $x\in V\left(H\right)$ and no component of H is isomorphic to $K_k$ where $T\subseteq V\left(G\right)$ and $k\ge 2$ . Then H has a maximal independent set I and a covering set $C=V\left(G\right)-I$ satisfying

$\left|V\left(H\right)\right|\le \left(k-\frac{1}{k+1}\right)i^{\prime }+{\displaystyle \sum }_{j=0}^{k-2}\left(j+1\right){i^{″}}_j,\left|C\right|\le \left(k-1-\frac{1}{k+1}\right)i^{\prime }+{\displaystyle \sum }_{j=0}^{k-2}j{i^{″}}_j,$

where $i^{\prime }=\left|I^{\prime }\right|=\left|\left\{x|x\in I,d_H\left(x\right)=k-1=d_G\left(x\right)\right\}\right|$ , ${i^{″}}_j=\left|\left\{x|x\in I^{″}=I-I^{\prime },d_H\left(x\right)=j<d_G\left(x\right)\right\}\right|$ .

Lemma 2.4. ([21]) Let G be a graph and $H=G\left[T\right]$ such that $\delta \left(H\right)\ge 1$ and $1\le d_G\left(x\right)\le k-1$ for every $x\in V\left(H\right)$ where $T\subseteq V\left(G\right)$ and $k\ge 2$ . Let $T_1,\cdots ,T_{k-1}$ be a partition of the vertices of H satisfying $d_G\left(x\right)=j$ for each $x\in T_j$ where we allow some $T_j$ to be empty. If each component of H has a vertex of degree at most $k-2$ in G, then H has a maximal independent set I and a covering set $C=V\left(H\right)-I$ such that

${\displaystyle \sum }_{j=1}^{k-1}\left(k-j\right)c_j\le {\displaystyle \sum }_{j=1}^{k-1}\left(k-2\right)\left(k-j\right)i_j$

where $c_j=\left|C\cap T_j\right|$ and $i_j=\left|I\cap T_j\right|$ for $j=1,\cdots ,k-1$ .

3. Proof of Theorems

Suppose that G satisfies the conditions in Theorem 1.2, but G has no fractional perfect matching. By Lemma 2.2, there exists a subset S of $V\left(G\right)$ such that $i\left(G-S\right)>\left|S\right|$ . We choose X as the set of isolated vertices of $G-S$ , that is, $\left|X\right|=i\left(G-S\right)$ . Since G is connected, it follows that $S\ne \varnothing$ , and $\left|N_G\left(X\right)\right|\subseteq S\ne V\left(G\right)$ .

According to the definition of $bind\left(G\right)$ , we obtain $bind\left(G\right)\le \frac{\left|N_G\left(X\right)\right|}{\left|X\right|}\le \frac{\left|S\right|}{i\left(G-S\right)}<1$ , contradicting with $bind\left(G\right)\ge 1$ . $\square$

Proof of Theorem 1.3. Suppose that G satisfies the conditions in Theorem 1.3, but G has no fractional k-factors. From Lemma 2.1, there exists a subset S of $V\left(G\right)$ such that

$k\left|T\right|-d_{G-S}\left(T\right)>k\left|S\right|,$ (1)

where $T=\left\{x\in V\left(G\right)-S|d_{G-S}\left(x\right)\le k-1\right\}$ .

Let m be the number of the components of $H^{\prime }=G\left[T\right]$ which are isomorphic to $K_k$ , we may assume that $C_1,C_2,\cdots ,C_m$ are these components. Let $T_0=\left\{x\in V\left(H^{\prime }\right)|d_{G-S}\left(x\right)=0\right\}$ and $H=H^{\prime }-m{K}_k-T_0$ .

If $\left|V\left(H\right)\right|=0$ , by (1) we get $k\left|T_0\right|+mk>k\left|S\right|$ , that is, $\left|S\right|\le \left|T_0\right|+m-1$ .

If $m=0$ , $\left|S\right|<\left|T_0\right|$ . Set $X=T_0$ , then $\left|X\right|=\left|T_0\right|$ and $N_G\left(X\right)\subseteq S$ , $N_G\left(X\right)\ne V\left(G\right)$ . We obtain that $bind\left(G\right)\le \frac{\left|N_G\left(X\right)\right|}{\left|X\right|}\le \frac{\left|S\right|}{\left|T_0\right|}<1$ , a contradiction.

If $m\ge 1$ , let $X=C_1\cup \cdots \cup C_{m-1}\cup \left\{x\right\}\cup T_0$ where x is an arbitrary vertex of $C_m$ , then $\left|X\right|=\left(m-1\right)k+1+\left|T_0\right|$ and $N_G\left(X\right)\subseteq C_1\cup \cdots \cup C_{m-1}\cup \left(C_m-\left\{x\right\}\right)\cup S$ , $N_G\left(X\right)\ne V\left(G\right)$ . This follows that

$bind\left(G\right)\le \frac{\left|N_G\left(X\right)\right|}{\left|X\right|}\le \frac{mk-1+\left|S\right|}{\left(m-1\right)k+1+\left|T_0\right|}\le \frac{mk-1+m-1+\left|T_0\right|}{\left(m-1\right)k+1+\left|T_0\right|}.$

When $k\ge 2$ ,

$\begin{array}{l}\left(\left(m-1\right)k+1+\left|T_0\right|\right)\left(k-\frac{1}{k}\right)-\left(mk-1+m-1+\left|T_0\right|\right)\\ \ge \left(\left(m-1\right)k+1\right)\left(k-\frac{1}{k}\right)-\left(mk-1+m-1\right)=\left(m-1\right)\left(k^2-k-2\right)+1-\frac{1}{k}>0.\end{array}$

That is, $bind\left(G\right)<k-\frac{1}{k}$ , a contradiction.

Now we consider that $\left|V\left(H\right)\right|>0$ . Let $H=H_1\cup H_2$ where H₁ is the union of components of H which satisfies that $d_{G-S}\left(x\right)=k-1$ for any vertex $x\in V\left(H_1\right)$ and $H_2=H-H_1$ . By Lemma 2.3, H₁ has a maximal independent set I₁ and the covering set $C_1=V\left(H_1\right)-I_1$ such that

$\left|V\left(H_1\right)\right|\le \left(k-\frac{1}{k+1}\right)i^{\prime }+{\displaystyle \sum }_{j=0}^{k-2}\left(j+1\right){i^{″}}_j,\left|C_1\right|\le \left(k-1-\frac{1}{k+1}\right)i^{\prime }+{\displaystyle \sum }_{j=0}^{k-2}j{i^{″}}_j,$

where $i^{\prime }=\left|I^{\prime }\right|=\left|\left\{x|x\in I_1,d_{H_1}\left(x\right)=k-1=d_{G-S}\left(x\right)\right\}\right|$ , ${i^{″}}_j=\left|\left\{x|x\in I^{″}=I_1-{I^{\prime }}_1,d_{H_1}\left(x\right)=j<d_{G-S}\left(x\right)\right\}\right|$ .

On the other hand, we may assume that $\delta \left(H_2\right)\ge 1$ . Since $\text{Δ}\left(H_2\right)\le k-1$ , let $T_j=\left\{x\in {V\left(H_2\right)|}_{G-S}\left(x\right)=j\right\}$ for $1\le j\le k-1$ . By the definition of H₂ we know that there exists one vertex with degree at most $k-2$ in $G-S$ from each component of H₂. According to Lemma 2.4, H₂ has a maximal independent set I₂ and the covering set $C_2=V\left(H_2\right)-I_2$ such that

${\displaystyle \sum }_{j=1}^{k-1}\left(k-j\right)c_j\le {\displaystyle \sum }_{j=1}^{k-1}\left(k-2\right)\left(k-j\right)i_j$ (2)

where $c_j=\left|C_2\cap T_j\right|$ and $i_j=\left|I_2\cap T_j\right|$ for $j=1,\cdots ,k-1$ .

Set $W=V\left(G\right)-S-T$ and $U=S\cup C_1\cup \left(N_G\left({I^{″}}_1\right)\cap W\right)\cup C_2\cup \left(N_G\left(I_2\right)\cap W\right)$ . Then

$\left|U\right|\le \left|S\right|+\left|C_1\right|+{\displaystyle \sum }_{j=0}^{k-2}\left(k-1-j\right){i^{″}}_j+{\displaystyle \sum }_{j=0}^{k-1}j{i}_j.$

Let $X^{\prime }$ be the set of isolated vertices of $G-U$ , then . Set $X=X^{\prime }\cup C_1\cup \cdots \cup C_m$ , then and $N_G\left(X\right)\subseteq U\cup C_1\cup \cdots \cup C_m$ , $N_G\left(X\right)\ne V\left(G\right)$ . By the definition of $bind\left(G\right)$ we have $\left|U\right|+mk\ge \left|N_G\left(X\right)\right|\ge bind\left(G\right)\left|X\right|$ . Therefore

(3)

From (1) we have $k\left(t_0+m\right)+\left|V\left(H_1\right)\right|+{\displaystyle \sum }_{j=1}^{k-1}\left(k-j\right)i_j+{\displaystyle \sum }_{j=1}^{k-1}\left(k-j\right)c_j\ge k\left|S\right|$ .

Combined with (3),

$\begin{array}{l}k\left(t_0+m\right)+\left|V\left(H_1\right)\right|+k\left|C_1\right|+{\displaystyle \sum }_{j=0}^{k-2}k\left(k-1-j\right){i^{″}}_j+{\displaystyle \sum }_{j=1}^{k-1}\left(k-j\right)c_j\\ >kbind\left(G\right)\left(t_0+mk+{i^{\prime }}_1+{\displaystyle \sum }_{j=0}^{k-2}{i^{″}}_j\right)+{\displaystyle \sum }_{j=1}^{k-1}\left(kbind\left(G\right)-kj-k+j\right)i_j-m{k}^2.\end{array}$

By the notation of $bind\left(G\right)$ , we have

$\begin{array}{l}\left|V\left(H_1\right)\right|+k\left|C_1\right|+{\displaystyle \sum }_{j=0}^{k-2}k\left(k-1-j\right){i^{″}}_j+{\displaystyle \sum }_{j=1}^{k-1}\left(k-j\right)c_j\\ >kbind\left(G\right)\left({i^{\prime }}_1+{\displaystyle \sum }_{j=0}^{k-2}{i^{″}}_j\right)+{\displaystyle \sum }_{j=1}^{k-1}\left(kbind\left(G\right)-kj-k+j\right)i_j.\end{array}$

By Lemma 2.3, we get that

$\begin{array}{l}\left|V\left(H_1\right)\right|+k\left|C_1\right|+{\displaystyle \sum }_{j=0}^{k-2}k\left(k-1-j\right){i^{″}}_j\\ \le \left(k-\frac{1}{k+1}+k\left(k-1-\frac{1}{k+1}\right)\right){i^{\prime }}_1+{\displaystyle \sum }_{j=0}^{k-2}\left(j+1+kj\right){i^{″}}_j+{\displaystyle \sum }_{j=0}^{k-2}k\left(k-1-j\right){i^{″}}_j\\ =\left(k^2-1\right){i^{\prime }}_1+{\displaystyle \sum }_{j=0}^{k-2}\left(k^2-k+j+1\right){i^{″}}_j.\end{array}$

Combined with (2),

$\begin{array}{l}{\displaystyle \sum }_{j=1}^{k-1}\left(k-2\right)\left(k-j\right)i_j+\left(k^2-1\right){i^{\prime }}_1+{\displaystyle \sum }_{j=0}^{k-2}\left(k^2-k+j+1\right){i^{″}}_j\\ >kbind\left(G\right)\left({i^{\prime }}_1+{\displaystyle \sum }_{j=0}^{k-2}{i^{″}}_j\right)+{\displaystyle \sum }_{j=1}^{k-1}\left(kbind\left(G\right)-kj-k+j\right)i_j\\ \ge \left(k^2-1\right){i^{\prime }}_1+kbind\left(G\right){\displaystyle \sum }_{j=0}^{k-2}{i^{″}}_j+{\displaystyle \sum }_{j=1}^{k-1}\left(kbind\left(G\right)-kj-k+j\right)i_j.\end{array}$

We have

Thus at least one of the following two cases must hold.

Case 1. There exists at least one j satisfying $\left(k-2\right)\left(k-j\right)>kbind\left(G\right)-kj-k+j$ . It follows that $bind\left(G\right)<\frac{k^2-k+j}{k}\le k-\frac{1}{k}$ ($j\le k-1$ ), a contradiction.

Case 2. $k^2-1>kbind\left(G\right)$ . In this case we have $bind\left(G\right)<k-\frac{1}{k}$ , a contradiction.

The proof of Theorem 1.3 is complete. $\square$

Remark. The result in Theorem 1.2 is sharp. To see this, consider the graph $G_1=K_n\vee \left(n+1\right)K_1$ where n is an arbitrary positive integer. We can immediately obtain that $bind\left(G_1\right)=\frac{n}{n+1}<1$ and $bind\left(G_1\right)$ is arbitrary close to 1 when n is enough. If we choose $S=V\left(K_n\right)$ , then $i\left(G-S\right)=n+1>\left|S\right|$ . It follows that G₁ has no fractional perfect matching by Lemma 2.2.

To see Theorem 1.3 is also sharp, we construct the following graph G₂: If $k=2$ , let $V\left(G_2\right)=V\left(A\right)\cup V\left(B\right)\cup V\left(C\right)$ where $A=K_{\left(nk+1\right)\left(k-1\right)}=K_{2n+1}$ , $B=\left(nk+1\right)K_1=\left(2n+1\right)K_1$ and $C=K_{n\left(k-1\right)}=K_n$ . Set other edges in G₂ are a perfect matching between A and B and all the pairs between B and C. This follows that $bind\left(G_2\right)=\frac{\left(nk+1\right)\left(k-1\right)+n\left(k-1\right)}{nk+1}\left(k=2\right)$ . It is easy to see that $bind\left(G_2\right)<k-\frac{1}{k}$ and $bind\left(G_2\right)$ can be made arbitrary close to $k-\frac{1}{k}$ when n is large enough ($k=2$ ). Let $S=C$ , by Lemma 2.1 G₂ has no fractional k-factor ($k=2$ ).

4. Conclusion

Therefore, we conclude that a graph G has a fractional 1-factor if $bind\left(G\right)\ge 1$ and has a fractional k-factor if $bind\left(G\right)\ge k-\frac{1}{k}$ . Furthermore, it is showed that both results are best possible in some sense.

Conflicts of Interest

The author declares no conflicts of interest regarding the publication of this paper.

References

[1]	Bondy, J. and Murty, U. (1976) Graph Theory with Applicatins. American Elsevier.
[2]	Scheinermman, E. and Ullman, D. (1997) Fractional Graph Theory. John and Wiley and Sons, Inc.
[3]	Woodall, D.R. (1973) The Binding Number of a Graph and Its Anderson Number. Journal of Combinatorial Theory, Series B, 15, 225-255. https://doi.org/10.1016/0095-8956(73)90038-5
[4]	Huilgol, M.I. and Divya, B. (2022) Geodetic Number and Geo-Chromatic Number of 2-Cartesian Product of Some Graphs. Open Journal of Discrete Mathematics, 12, 1-16. https://doi.org/10.4236/ojdm.2022.121001
[5]	Burchett, P.A. (2020) The Number of Minimum Roman and Minimum Total Dominating Sets for Some Chessboard Graphs. Open Journal of Discrete Mathematics, 10, 31-44. https://doi.org/10.4236/ojdm.2020.101004
[6]	Hong, X., Ao, G. and Gao, F. (2021) The Generalization of Signed Domination Number of Two Classes of Graphs. Open Journal of Discrete Mathematics, 11, 114-132. https://doi.org/10.4236/ojdm.2021.114009
[7]	Anderson, I. (1971) Perfect Matchings of a Graph. Journal of Combinatorial Theory, Series B, 10, 183-186. https://doi.org/10.1016/0095-8956(71)90041-4
[8]	Plummer, M.D. and Saito, A. (2017) Toughness, Binding Number and Restricted Matching Extension in a Graph. Discrete Mathematics, 340, 2665-2672. https://doi.org/10.1016/j.disc.2016.10.003
[9]	Katerinis, P. and Woodall, D.R. (1987) Binding Numbers of Graphs and the Existence of k-Factors. The Quarterly Journal of Mathematics, 38, 221-228. https://doi.org/10.1093/qmath/38.2.221
[10]	Katerinis, P. (1985) Minimum Degree of a Graph and the Existence of k-Factors. Proceedings of the Indian Academy of Sciences-Section A, 94, 123-127. https://doi.org/10.1007/bf02880991
[11]	Zhou, S.Z. (2013) Binding Numbers for Fractional ID-k-Factor-Critical Graphs. Acta Mathematica Sinica, English Series, 30, 181-186. https://doi.org/10.1007/s10114-013-1396-9
[12]	Kano, M. and Tokushige, N. (1992) Binding Numbers and F-Factors of Graphs. Journal of Combinatorial Theory, Series B, 54, 213-221. https://doi.org/10.1016/0095-8956(92)90053-z
[13]	Yashima, T. (2018) Binding Number, Minimum Degree and (g, f)-Factors of Graphs, Contrib. Discrete Mathematics, 13, 137-141.
[14]	Zhou, S. (2021) Binding Numbers and Restricted Fractional (g, f)-Factors in Graphs. Discrete Applied Mathematics, 305, 350-356. https://doi.org/10.1016/j.dam.2020.10.017
[15]	Wu, J. and Gao, W. (2018) Binding Number Condition for Fractional (g, f, n’, m)-Critical Deleted Graph in the New Setting. Utilitas Mathematica, 109, 129-137.
[16]	Chen, Y. and Dai, G. (2022) Binding Number and Path-Factor Critical Deleted Graphs. AKCE International Journal of Graphs and Combinatorics, 19, 197-200. https://doi.org/10.1080/09728600.2022.2094299
[17]	Fan, D. and Lin, H. (2024) Binding Number, k-Factor and Spectral Radius of Graphs. The Electronic Journal of Combinatorics, 31, Article No. 1.30. https://doi.org/10.37236/12165
[18]	Feng, X. and Deng, X. (2023) Toughness and Binding Number Bounds of Star-Like and Path Factor. RAIRO-Operations Research, 57, 1167-1177. https://doi.org/10.1051/ro/2023057
[19]	Liu, G. and Zhang, L. (2001) Fractional (g, f)-Factors of Graphs. Acta Mathematica Scientia, 21, 541-545. https://doi.org/10.1016/s0252-9602(17)30443-5
[20]	Chang, R. and Zhu, Y. (2012) Toughness and [a, b]-Factors in Graphs. Ars Combinatoria, 105, 451-459.
[21]	Liu, G. and Zhang, L. (2008) Toughness and the Existence of Fractional k-Factors of Graphs. Discrete Mathematics, 308, 1741-1748. https://doi.org/10.1016/j.disc.2006.09.048