Search

In communication networks, the existence of fractional factors can be characterized as the feasibility of data transmission. When some nonadjacent nodes with each other are damaged and a special channel is assigned, the possibility of data transmission in a communication network is equivalent to the existence of fractional ID-factor-critical covered graph. As a consequence, the existence of fractional ID- [ a , b ] -factor-critical covered graph plays a key role in studying data transmissions of communication networks. Neighborhood and minimum degree of a graph or a network are often used to measure the vulnerability and robustness of a graph or a network, which are two important parameters considered in network design. In this article, we mainly investigate the relationship between neighborhood of independent set, minimum degree and the fractional ID- [ a , b ] -factor-critical covered graph, and acquire a neighborhood of independent set and minimum degree condition for a graph being fractional ID- [ a , b ] -factor-critical covered, which is a generalization of the previous results.

A graph G is P ≥ k -factor deleted if for every edge e ∈ E ( G ) , G contains a P ≥ k -factor that excludes e . We first define the concept of ( P ≥ k , n ) -critical deleted graph, that is, a graph G is ( P ≥ k , n ) -critical deleted if for every subset D ⊆ V ( G ) with | D | = n , the graph G − D is P ≥ k -factor deleted. Clearly, a ( P ≥ k , 0 ) -critical deleted graph is a P ≥ k -factor deleted graph. In this paper, we verify that (i) an ( n + 2 ) -connected graph G is ( P ≥ 2 , n ) -critical deleted if its binding number b i n d ( G ) > 3 + n 4 ; (ii) an ( n + 2 ) -connected graph G is ( P ≥ 3 , n ) -critical deleted if its binding number b i n d ( G ) > 3 + n 2 . Furthermore, we claim that two results above are best possible in some sense.

Let G be a connected graph of even order n. An odd [1,b]-factor of G is a spanning subgraph F of G such that dF(v) ∈ {1,3,5,··· ,b} for any v ∈ V (G), where b is positive odd integer. The distance matrix D(G) of G is a symmetric real matrix with (i,j)-entry being the distance between the vertices vi and vj. The distance signless Laplacian matrix Q(G) of G is defined by Q(G) = Tr(G) + D(G), where Tr(G) is the diagonal matrix of the vertex transmissions in G. The largest eigenvalue η1(G) of Q(G) is called the distance signless Laplacian spectral radius of G. In this paper, we verify sharp upper bounds on the distance signless Laplacian spectral radius to guarantee the existence of an odd [1,b]-factor in a graph; we provide some graphs to show that the bounds are optimal.

A graph G is called a $(P_{\geq n},k)$ -factor-critical covered graph if for any $Q\subseteq V(G)$ with $|Q|=k$ and any $e\in E(G-Q)$ , $G-Q$ has a $P_{\geq n}$ -factor covering e. We demonstrate that (i) a $(k+1)$ -connected graph G with at least $k+3$ vertices is a $(P_{\geq 3},k)$ -factor-critical covered graph if its toughness $t(G)>{(2+k)}/{3}$ ; (ii) a $(k+2)$ -connected graph G is a $(P_{\geq 3},k)$ -factor-critical covered graph if its isolated toughness $I(G)>{(5+k)}/{3}$ . Furthermore, we show that the conditions on $t(G)$ and $I(G)$ are sharp.

Let G be a graph and h : E ( G ) → [ 0 , 1 ] be a function. If g ( x ) ≤ ∑ e ∋ x h ( e ) ≤ f ( x ) for every x ∈ V ( G ) , then we call a graph F h with vertex set V ( G ) and edge set E h a fractional ( g , f ) -factor of G with indicator function h , where e ∋ x means the edge e incident to vertex x in G and E h = { e : e ∈ E ( G ) , h ( e ) > 0 } . We say that G admits property E ( m , n ) with respect to fractional ( g , f ) -factor if for any two sets of independent edges M and N with | M | = m , | N | = n and M ∩ N = 0 , G admits a fractional ( g , f ) -factor F h such that h ( e ) = 1 for any e ∈ M and h ( e ) = 0 for any e ∈ N . In this paper, we show a lower bound on binding number which guarantees a graph G to have property E ( 1 , n ) with respect to fractional ( g , f ) -factor.

Let $$k\ge 2$$ be an integer. A $$P_{\ge k}$$ -factor of a graph G is its spanning subgraph each of whose components is a path of order at least k. A graph G is $$P_{\ge k}$$ -factor covered if for any edge e of G, G has a $$P_{\ge k}$$ -factor containing e. A graph G is $$P_{\ge k}$$ -factor deleted if for any edge e of G, G has a $$P_{\ge k}$$ -factor excluding e. A graph G is $$(P_{\ge k},n)$$ -factor critical covered if for any $$Q\subseteq V(G)$$ with $$|Q|=n$$ , the graph $$G-Q$$ is $$P_{\ge k}$$ -factor covered. A graph G is $$(P_{\ge k},n)$$ -factor critical deleted if for any $$Q\subseteq V(G)$$ with $$|Q|=n$$ , the graph $$G-Q$$ is $$P_{\ge k}$$ -factor deleted. Zhou et al. (Contribut Dis Math 14(1): 167–174, 2019) introduced the sun toughness of a graph G, which is denoted by s(G) and defined by $$\begin{aligned} s(G)=\min \left\{ \frac{|X|}{sun(G-X)}:X\subseteq V(G),sun(G-X)\ge 2\right\} \end{aligned}$$ if G is not a complete graph; otherwise, $$s(G)=+\infty $$ . In this article, we prove that (i) an $$(n+r+2)$$ -connected graph G is $$(P_{\ge 3},n)$$ -factor critical deleted if $$s(G)>\frac{n+r+3}{2(r+2)}$$ , where $$n\ge 0$$ and $$r\ge 0$$ are two integers; (ii) an $$(n+r+1)$$ -connected graph G is $$(P_{\ge 3},n)$$ -factor critical covered if $$s(G)>\frac{n+r+1}{2r+1}$$ , where $$n\ge 0$$ and $$r\ge 1$$ are two integers.