Though the latter is popular in short-range applications, such as smart homes, the former, ad hoc technique, attracts more interests due to its high flexibility and ability to support long-range, large scale, and highly distributed applications. In this survey, we only focus on wireless sensor networks adopting multi-hop transmission. In a WSN, after collecting information from the environment, sensors need to transmit aggregated data to gateways or information collection nodes. It is important to ensure that every sensor can communicate with the gateways. Due to the multi-hop communication of WSNs, a sufficient condition for reliable information transmission is full connectivity of the network. A network is said to be fully connected if every pair of nodes can communicate with each other, either directly or via intermediate relay nodes. Due to the large number of sensors in a WSN, the total cost could be high for the whole network, though the cost of each individual sensor is low. Therefore, it is important to find the minimum number of nodes required for a WSN to achieve connectivity. Another related important problem for WSNs is finding a small connected relay set to assist in routing. Multi-hop WSNs need to perform efficient routing. Since mobile ad hoc networks (MANETs) and WSNs often have very limited, or even does not have, fixed infrastructure, the routing process in such networks is often complicated and inefficient; it can generate a large amount of overhead, and there are many possible paths, due to the broadcast nature of the wireless communications. Thus it is helpful to find a small connected set of sensor nodes to form a routing \"backbone\", and restricted all other nodes to connecting to this backbone by a single hop. This node set can also help to resolve the broadcast storm problem [5], which is often caused by blind flooding. As WSNs may be deployed in inaccessible terrains, and may contain a tremendous number of sensor nodes, it is often difficult or impossible to replace or recharge their batteries. Thus, energy conservation is critical for WSNs, both for each sensor node and the entire network level operations. Various approaches have been proposed to reduce energy consumption for sensor networks. For example, for the network level operations such as routing, if only a small fraction of sensors are involved in the routing process, the rest of the sensors can be turned off to save energy. This scheme is supported by the hardware and software advances that leverage the capability of temporarily shutting down those sensors that are not involved in any network operations. For instance, Rockwell's WINS sensor nodes can achieve a factor of ten power reduction by shutting down the radio transceiver, compared to those idle nodes whose transceivers are on [6]. However, a prerequisite for this type of energy saving scheme is that the WSNs still perform all the required functions even with some nodes turned off. This raises an important research problem: what is the maximum number of sensors that can be turned off, while maintaining functionality of the WSN? This problem is equivalent to minimizing the total number of active nodes, subject to ordinary operations of the system. The selected sensors will function as backbone relay nodes to maintain communications within the entire sensor network. A further important problem, which is beyond the scope of this survey, is how to optimally shut off and turn on sensors over time to maximise network lifetime [7]. The remainder of this paper is organized as follows. Section 2 gives a brief introduction to the graph models applied to wireless network investigations. Section 3 provides an overview of the prior results for connectivity studies in wireless ad hoc networks and WSNs, including percolation theory. Section 4 describes models with more general radio coverage patterns, and some hybrid models.