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.

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 a distributed database system, data replicas are placed at different locations to achieve high data availability in the presence of link failures. With a majority voting protocol, a location survives for read/write operations if and only if it is accessible to more than half of the replicas. The problem is to find out the optimal placements for a given number of data replicas in a ring network. When the number of replicas is odd, it was conjectured by Hu et al. [X.-D. Hu, X.-H. Jia, D.-Z. Du, D.-Y. Li, H.-J. Huang, Placement of data replicas for optimal data availability in ring networks, J. Parallel Distrib. Comput., 61 (2001) 1412–1424] that every uniform placement is optimal, which is proved by Shekhar and Wu later. However, when the number of replicas is even, it was pointed out by Hu et al. that uniform placements are not optimal and the optimal placement problem may be very complicated. In this paper, we study the optimal placement problem in a ring network with majority voting protocol and an even number of replicas, and give a complete characterization of optimal placements when the number of replicas is not too large compared with the number of locations.

When homogeneous sensors are deployed into a three-dimensional space instead of a plane, the mathematical model for the sensor network is a unit ball graph instead of a unit disk graph. It is known that for the minimum connected dominating set in unit disk graph, there is a polynomial time approximation scheme (PTAS). However, that construction cannot be extended to obtain a PTAS for unit ball graph. In this paper, we will introduce a new construction, which gives not only a PTAS for the minimum connected dominating set in unit ball graph, but also improves running time of PTAS for unit disk graph.

A vertex set S⊆V(G) is k-weak-edge-connected if, for every C⊂Sand x∈S−C, there are min{k,|C|} edge-disjoint (x, C)-paths in G. For a graph G and a k-weak-edge-connected vertex set S⊂V(G) with k≥3 and 4≤|S|≤2k, we show that G has an Eulerian subgraph containing all vertices in S.