×

A remark about fractional \((f,n)\)-critical graphs. (English) Zbl 1224.05431

Summary: Let \(G\) be a graph of order \(p\), and let \(a,b\) and \(n\) be nonnegative integers with \(b\geq a\geq 2\), and let \(f\) be an integer-valued function defined on \(V(G)\) such that \(a\leq f(x)\leq b\) for each \(x\in V(G)\). A fractional \(f\)-factor is a function \(h\) that assigns to each edge of a graph \(G\) a number in \([0,1]\) so that, for each vertex \(x\), we have \(d^h_G(x)=f(x)\), where \(d^h_G(x)=\sum_{e\ni x} h(e)\) (the sum is taken over all edges incident to \(x\)) is a fractional degree of \(x\) in \(G\). Then a graph \(G\) is called a fractional \((f,n)\)-critical graph if after deleting any \(n\) vertices of \(G\) the remaining graph of \(G\) has a fractional \(f\)-factor. The binding number \(\text{bind}(G)\) is defined as follows, \[ \text{bind}(G)=\min\left\{\frac {| N_G(X)|}{| X|}:\phi=X\subseteq V(G),N_G(X)\neq V(G)\right\}. \] In this paper, it is proved that \(G\) is a fractional \((f,n)\)-critical graph if \(p\geq \frac {(a+b-1)(a+b-2)-2}a +\frac {b_n}{a-1}\), \(\text{bind}(G)\geq \frac {(a+b-1)(p-1)}{a(p-1)-b_n}\) and \(\delta(G)=\lfloor\frac {(b-1)p+a+b+b_n-2}{a+b-1}\rfloor\).

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
PDFBibTeX XMLCite
Full Text: EuDML