A result on fractional (a,b,k)-critical covered graphs

DOI10.1007/S10255-021-1034-8MaRDI QIDQ2240647zbMATH OpenOpenAlexFDO

Authors Sizhong Zhou

Publication date 4 November 2021

Published in Acta Mathematicae Applicatae Sinica. English Series (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1912.12542

zbMATH Keywords

fractional graph theorygraph factors

Mathematics Subject Classification ID

Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Fractional graph theory, fuzzy graph theory (05C72)

Abstract: For a graph $G$, the set of vertices in $G$ is denoted by $V(G)$, and the set of edges in $G$ is denoted by $E(G)$. A fractional $[a,b]$-factor of a graph $G$ is a function $h$ from $E(G)$ to $[0,1]$ satisfying $aleq{d}_G^h(v)leqb$ for every vertex $v$ of $G$, where $d_G^h(v)=sumlimit{s}_{einE(v)}h(e)$ and $E(v)=e=uv:uinV(G)$. A graph $G$ is called fractional $[a,b]$-covered if $G$ contains a fractional $[a,b]$-factor $h$ with $h(e)=1$ for any edge $e$ of $G$. A graph $G$ is called fractional $(a,b,k)$-critical covered if $G-Q$ is fractional $[a,b]$-covered for any $QsubseteqV(G)$ with $|Q|=k$. In this article, we demonstrate a neighborhood condition for a graph to be fractional $(a,b,k)$-critical covered. Furthermore, we claim that the result is sharp.

Review text

A fractional \([a,b]\)-factor of a graph \(G\) is a function \(h:E(G) \rightarrow [0,1]\) such that, for any \(v \in V(G)\), we have \(a \le \sum_{e \ni v} f(e) \le b\). A graph \(G\) is fractional \([a,b]\)-covered if, for each \(e \in E(G)\), it has a fractional \([a,b]\)-factor \(h\) with \(h(e)=1\). This paper considers an additional parameter \(k\) and the condition of \(G\) being fractional \((a,b,k)\)-critical covered if the subgraph obtained by deleting any \(k\) vertices from \(G\) is fractional \([a,b]\)-covered. \textit{S. Zhou} et al. showed in [Bull. Aust. Math. Soc. 81, No. 3, 473--480 (2010; Zbl 1203.05129)] that, given an integer \(r \ge 1\), a sufficient condition for \(G\) to have a fractional \(r\)-factor (\(a=b=r\) in the above definition) is \(n \ge 6r-12+\frac{6}{r}\) and, for every \(X \subseteq V(G)\), \[ \begin{cases} |N_G(X)| = n &\text{if } |X| \ge \lfloor \frac{rn}{2r-1} \rfloor; \\ |N_G(X)| \ge \frac{2r-1}{r}|X| & \text{otherwise.} \end{cases} \] Loosely speaking, this condition says that \(|N_G(X)|\) is roughly \(2|X|\). This article extends this result to the context of fractional \((a,b,k)\)-critical covered graphs, with a similar two-case condition on the neighborhood sizes of subsets \(X \subseteq V(G)\). This result is given in Theorem 1.2. Special cases when \(k=0\) or \(a=b\) are stated as corollaries of this. The main theorem is proved in Section 2. The proof relies on a result from \textit{Z. Li} et al. [Math. Appl. 16, No. 1, 148--154 (2003; Zbl 1032.05113)]. Later, in Section 3, a construction is given which shows the stated cases for \(|X|\) are necessary. Reviewer's remark: Please note that reference [\textit{S. Wang} and \textit{W. Zhang}, Probl. Inf. Transm. 56, No. 3, 270--277 (2020; Zbl 1458.05221); translation from Probl. Peredachi Inf. 56, No. 5, 77--85 (2020)] in the bibliography is very similar to this paper, with only some minor changes to notation and presentation.

Recommendations

• Discussion on fractional (a, b, k)-critical covered graphs
• A neighborhood union condition for fractional \((a, b, k)\)-critical covered graphs
• Notes on fractional (a, b, k)-critical covered graphs
• Independence number and connectivity for fractional \((a, b, k)\)-critical covered graphs
• A sufficient condition for fractional ID-\([a,b]\)-factor-critical covered graphs
• Degree conditions for fractional \((a,b,k)\)-critical covered graphs
• Binding numbers for fractional \((a, b, k)\)-critical covered graphs
• An existence theorem on fractional ID-\((g, f)\)-factor-critical covered graphs
• A degree condition for fractional (g, f, n)-critical covered graphs
• Research on fractional critical covered graphs

Cites work

• A degree condition for fractional \([a,b]\)-covered graphs
• A neighborhood union condition for fractional \((a, b, k)\)-critical covered graphs
• A neighborhood union condition for fractional ID-\([a, b]\)-factor-critical graphs
• A note on degree sum conditions for 2-factors with a prescribed number of cycles in bipartite graphs
• A note on fractional ID-\( [ a , b ]\)-factor-critical covered graphs
• A sufficient condition for a graph to have \([a,b]\)-factors
• A sufficient condition for the existence of restricted fractional (g, f)-factors in graphs
• A toughness condition for fractional \((k, m)\)-deleted graphs revisited
• Binding numbers and restricted fractional ( g , f )-factors in graphs
• Brooks type results for conflict-free colorings and \(\{a, b \}\)-factors in graphs
• Component factors and binding number conditions in graphs
• Degree conditions for fractional \((a,b,k)\)-critical covered graphs
• scientific article; zbMATH DE number 3587078 (Why is no real title available?)
• Isolated toughness and path-factor uniform graphs
• Neighbourhood and the existence of fractional k-factors of graphs
• On k-orthogonal factorizations in networks
• On factors with given components
• Path factors in subgraphs
• Remarks on path factors in graphs
• Research on fractional critical covered graphs
• Some results on path-factor critical avoidable graphs
• Subgraphs with orthogonal factorizations in graphs
• Two tight independent set conditions for fractional (g,f,m)-deleted graphs systems

Cited in

(28)

• A degree condition for fractional \([a,b]\)-covered graphs
• A neighborhood union condition for fractional \((a, b, k)\)-critical covered graphs
• On \(P_{\geq 3}\)-factor deleted graphs
• Discussion on fractional (a, b, k)-critical covered graphs
• Discussions on orthogonal factorizations in digraphs
• A degree condition for fractional (g, f, n)-critical covered graphs
• Research on fractional critical covered graphs
• Neighborhood union conditions for fractional \([a, b]\)-covered graphs
• Degree conditions for fractional \((a,b,k)\)-critical covered graphs
• Some properties on f-edge covered critical graphs
• Two sufficient conditions for odd \([1,b]\)-factors in graphs
• Toughness for fractional \((2, b, k)\)-critical covered graphs
• Spectral radius conditions for fractional \([a,b]\)-covered graphs
• Some sufficient conditions for path-factor uniform graphs
• Notes on fractional (a, b, k)-critical covered graphs
• A Note of Generalization of Fractional ID-factor-critical Graphs
• A note on fractional covers of a graph
• An existence theorem on fractional ID-\((g, f)\)-factor-critical covered graphs
• A neighborhood condition for all fractional \((a,b,k)\)-critical graphs.
• Path factors and neighborhoods of independent sets in graphs
• Isolated toughness and path-factor uniform graphs. II.
• An improvement of the previous result on fractional (a,b,k)-critical covered graphs
• Sun toughness and path-factor uniform graphs
• Path-factor critical covered graphs and path-factor uniform graphs
• Remarks on restricted fractional (g, f)-factors in graphs
• On fractional (g, f, n^, m)-critical covered graphs
• Some results about star-factors in graphs
• On path-factor critical uniform graphs

This page was built for publication: A result on fractional \((a,b,k)\)-critical covered graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2240647)