The q-composite key predistribution scheme [1] is used prevalently for secure communications in large-scale wireless sensor networks (WSNs). Prior work [2]-[4] explores topological properties of WSNs employing the q-composite scheme for q = 1 with unreliable communication links modeled as independent on off channels. In this paper, we investigate topological properties related to the node degree in WSNs operating under the q-composite scheme and the on off channel model. Our results apply to general q and are stronger than those reported for the node degree in prior work even for the case of q being 1. Specifically, we show that the number of nodes with certain degree asymptotically converges in distribution to a Poisson random variable, present the asymptotic probability distribution for the minimum degree of the network, and establish the asymptotically exact probability for the property that the minimum degree is at least an arbitrary value. Numerical experiments confirm the validity of our analytical findings.
In graph @math , Ya g an @cite_35 presents zero--one laws for connectivity and for the property that the minimum degree is at least @math . We extend Ya g an's results to general @math for @math in @cite_6 @cite_33 .
@cite_35 @cite_33 @cite_6
2005079131 1963903160 2080022329 2065527713
In this paper, we consider a wireless network with unreliable links and investigate its minimum node degree and k- connectivity. In such network, n nodes are uniformly distributed in a region, and edges are established for any two nodes within a certain distance and with a probabilistically active link in between. On a torus topology, we present a zero-one law for the property of minimum degree being at least k, leading to a zero-law for k-connectivity and an intermediate result towards a one-law. On a square with boundary effect, we establish a one- law for minimum degree. Our results are derived from rigorous analysis and also confirmed by the simulation, and they provide guidelines for the design of wireless networks. Index Terms—Connectivity, Erdos-Renyi graph, geometric graph, graph intersection, minimum node degree, random graph, unreliable link, wireless network, zero-one law. The visibility graph of a finite set of points in the plane has the points as vertices and an edge between two vertices if the line segment between them contains no other points. This paper establishes bounds on the edge- and vertex-connectivity of visibility graphs. Unless all its vertices are collinear, a visibility graph has diameter at most 2, and so it follows by a result of Plesnik (Acta Fac. Rerum Nat. Univ. Comen. Math. 30:71–93, 1975) that its edge-connectivity equals its minimum degree. We strengthen the result of Plesnik by showing that for any two vertices v and w in a graph of diameter 2, if deg(v)≤deg(w) then there exist deg(v) edge-disjoint vw-paths of length at most 4. For vertex-connectivity, we prove that every visibility graph with n vertices and at most l collinear vertices has connectivity at least @math , which is tight. We also prove the qualitatively stronger result that the vertex-connectivity is at least half the minimum degree. Finally, in the case that l=4 we improve this bound to two thirds of the minimum degree. A problem arising in the design of vacuum systems and having applications to some natural problems of interconnection design is described as follows. (1) Given a set X and subsets @math of @math , satisfying @math , find a graph G with vertex set X and the minimum number of edges such that for any i, the subgraph induced by @math has a connected component containing @math .Two other problems related to this one are the following ones. (2) Given a set X and subsets @math such that @math , find a graph G with vertex set X and the minimum number of edges such that for any i the subgraph @math induced by @math in G is connected. (3) Given a set X and subsets @math such that @math , find a graph G with vertex set X, find a graph G with vertex set X and the minimum number of edges such that for any subset I of @math , the subgraph induced by @math is co... We propose a fast methodology for encoding graphs with information-theoretically minimum numbers of bits. Specifically, a graph with property @math is called a @math -graph . If @math satisfies certain properties, then an n-node m-edge @math -graph G can be encoded by a binary string X such that (1) G and X can be obtained from each other in O(n log n) time, and (2) X has at most @math bits for any continuous superadditive function @math so that there are at most @math distinct @math -node @math -graphs. The methodology is applicable to general classes of graphs; this paper focuses on planar graphs. Examples of such @math include all conjunctions over the following groups of properties: (1) G is a planar graph or a plane graph; (2) @math is directed or undirected; (3) @math is triangulated, triconnected, biconnected, merely connected, or not required to be connected; (4) the nodes of G are labeled with labels from @math for @math ; (5) the edges of G are labeled with labels from @math for @math ; and (6) each node (respectively, edge) of G has at most @math self-loops (respectively, @math multiple edges). Moreover, @math and @math are not required to be O(1) for the cases of @math being a plane triangulation. These examples are novel applications of small cycle separators of planar graphs and are the only nontrivial classes of graphs, other than rooted trees, with known polynomial-time information-theoretically optimal coding schemes.