## 2 Graph Models  
Connectivity is critical for WSNs, as information collected needs to be sent to data collection or processing centres. This is only possible if there is a path from each node to that collection centre. The connectivity of a WSN is usually studied by considering a graph associated with that WSN. A WSN or a wireless ad hoc network is often represented by a graph in which vertices correspond to the communication nodes, and a directed edge from one vertex to another indicates that the node corresponding to the former can send data directly to the node corresponding to the latter. It is common to assume that propagation conditions can be modelled simply by there being a \"transmission range\" within which transmission is possible, and outside of which it is impossible. If all nodes have equal transmission ranges, then the graph becomes undirected. A network is called connected if this associated graph is connected. A graph \(G\) is connected if and only if there exists a path between any pair of its vertices [8]. If a network is connected then any pair of nodes can communicate with each other, possibly taking multiple hops through relay nodes. It is sometimes useful to consider stronger forms of connectivity, such as \(k\)-connectivity, in which the network remains connected even if \(k-1\) nodes are removed. If a network is \(k\)-connected (\(k\geq 2\)), it has better fault-tolerance than if it is merely 1-connected. Ensuring \(k\)-connectivity extends the network lifetime if nodes fail at random times. Weaker notions of connectivity are also possible, such as the requirement that each node need only be connected to one of a set of base stations [9]. This paper will focus on the intermediate case in which the entire network is required to be 1-connected. It is clear that the connectivity of a WSN is related to the positions of nodes, and those positions are heavily affected by the method of sensor deployment. In general, there are two types of approaches to deploy sensors in a WSN: deterministic deployment, where sensors are placed exactly at pre-engineered positions, and the random deployment, where nodes are deployed at random positions. For the deterministic deployment, networks are carefully planned, and nodes are placed at desired positions. If specifications of nodes are known, it is not difficult to determine whether the network is connected, and if not, to add relay nodes where needed. Although deterministic deployment has many advantages, in order to reduce installation costs, it has often been proposed that large WSNs which contains very large numbers of nodes be deployed randomly. Nodes may be dispersed by a moving vehicle or artillery shell [3]. Therefore, sensors often have nondeterministic positions, and the analysis of connectivity of such a type of networks involves the modelling of random networks. Random graphs are often applied to model communication networks to highlight their randomness. Mathematically, a random graph is a graph that is generated by a stochastic process [10]. The theory of random graphs began with [PERSON] and [PERSON]'s pioneer work in the late \(1950\)s and early \(1960\)s, which considered a class of random graphs now called Erdos-Renyi graphs [11, 12]. An Erdos-Renyi graph \(G(n,p)\) is a graph with \(n\) vertices, in which each of the \(\mathrm{C}_{n}^{2}\) possible edges exists with probability \(p\), independent of all other edges. This class was originally used as a tool in the field of combinatorial mathematics. However, it is now widely accepted as a model for many fields, such as communications [13, 14, 15], social studies [16, 17] and biology [18]. Independent of [PERSON] and [PERSON], [PERSON] [19], [PERSON] _et al._[20], and [PERSON] and [PERSON] [21] also studied the statistical aspects of graphs. However, unlike [PERSON] and [PERSON], they used enumeration methods, which are essentially deterministic, to estimate exact values of graph properties, while [PERSON] and [PERSON] studied the distributions of graph properties.