A subset is called an -vertex-cut of if is disconnected and each vertex has at least two neighbors in . The cardinality of a minimum -vertex-cut of , denoted by , is the -vertex-connectivity of . In this work, we prove that for , where is the -dimensional star graph.

In this paper, we characterize graphs whose tensor product admit nowhere‐zero 3‐flow. The main result is: For two graphs G1 and G2 with δurn:x-wiley:03649024:media:JGT20211:tex2gif-inf-3 ≥ 2 and G2 not belonging to a well‐characterized class of graphs, the tensor product of G1 and G2 admits a nowhere‐zero 3‐flow.

For a connected graph , an edge set is a k-restricted-edge-cut, if is disconnected and every component of has at least k vertices. The k-restricted-edge-connectivity of G, denoted by , is defined as the cardinality of a minimum k-restricted-edge-cut. The k-isoperimetric-edge-connectivity is defined as , where is the set of edges with one end in U and the other end in ⧹. In this note, we give some degree conditions for a graph to have optimal and/or .

Because of its application in the field of security in wireless sensor networks, k-path vertex cover (VCPk) has received a lot of attention in recent years. Given a graph G=(V,E), a vertex set C⊆V is a k-path vertex cover (VCPk) of G if every path on k vertices has at least one vertex in C, and C is a connected k-path vertex cover of G (CVCPk) if furthermore the subgraph of G induced by C is connected. A homogeneous wireless sensor network can be modeled as a unit disk graph. This paper presents a new PTAS for MinCVCPk on unit disk graphs. Compared with previous PTAS given by Liu et al., our method not only simplifies the algorithm and reduces the time-complexity, but also simplifies the analysis by a large amount.

A vertex set F is a k-path vertex cover () of graph G if every path of G on k vertices contains at least one vertex from F. A graph G is a d-dimensional ball graph if each vertex of G corresponds to a ball in , two vertices are adjacent in G if and only if their corresponding balls have nonempty intersection. The heterogeneity of a ball graph is defined to be , where and are the largest radius and the smallest radius of those balls, respectively. In this paper, we present a PTAS for the minimum problem in a ball graph whose heterogeneity is bounded by a constant.