Random @math -intersection graphs have recently received much interest in a wide range of application areas. Broadly speaking, a random @math -intersection graph is constructed by first assigning each vertex a set of items in some random manner, and then putting an undirected edge between all pairs of vertices that share at least @math items (the graph is called a random intersection graph when @math ). A special case of particular interest is a uniform random @math -intersection graph, where each vertex independently selects the same number of items uniformly at random from a common item pool. Another important case is a binomial random @math -intersection graph, where each item from a pool is independently assigned to each vertex with the same probability. Both models have found numerous applications thus far including cryptanalysis, and the modeling of recommender systems, secure sensor networks, online social networks, trust networks and small-world networks (uniform random @math -intersection graphs), as well as clustering analysis, classification, and the design of integrated circuits (binomial random @math -intersection graphs). In this paper, for binomial uniform random @math -intersection graphs, we present results related to @math -connectivity and minimum vertex degree. Specifically, we derive the asymptotically exact probabilities and zero-one laws for the following three properties: (i) @math -vertex-connectivity, (ii) @math -edge-connectivity and (iii) the property of minimum vertex degree being at least @math .
Bloznelis @cite_45 investigates the clustering coefficient of graph @math and show that the chance of two neighbors of a given vertex @math to be adjacent decays as @math , where @math is a positive constant and @math is the degree of vertex @math . Bloznelis @cite_13 study the correlation coefficient of degrees of adjacent vertices in @math . Bloznelis @cite_19 demonstrate that a connected component in @math with at at least a constant fraction of @math emerges as @math when the edge probability @math exceeds @math .
@cite_19 @cite_45 @cite_13
1636592403 2150191198
We present an algorithm for testing the k-vertex-connectivity of graphs with the given maximum degree. The time complexity of the algorithm is independent of the number of vertices and edges of graphs. Fixed degree bound d, a graph G with n vertices and a maximum degree at most d is called e-far from k-vertex-connectivity when at least @math edges must be added to or removed from G to obtain a k-vertex-connected graph with a maximum degree at most d. The algorithm always accepts every graph that is k-vertex-connected and rejects every graph that is e-far from k-vertex-connectivity with a probability of at least 2 3. The algorithm runs in @math time (c>1 is a constant) for (k−1)-vertex-connected graphs, and in @math time (c>1 is a constant) for general graphs. It is the first constant-time k-vertex-connectivity testing algorithm for general k≥4. A graph @math is called @math -full if @math contains a subgraph @math of @math edges such that, for any non-empty @math , @math holds. Here, @math denotes the set of vertices incident to @math . It is known that the family of edge sets of @math -full graphs forms a family of matroid, known as the sparsity matroid of @math . In this paper, we give a constant-time approximation algorithm for the rank of the sparsity matroid of a degree-bounded undirected graph. This leads to a constant-time tester for @math -fullness in the bounded-degree model, (i.e., we can decide with high probability whether an input graph satisfies a property @math or far from @math ). Depending on the values of @math and @math , it can test various properties of a graph such as connectivity, rigidity, and how many spanning trees can be packed. Based on this result, we also propose a constant-time tester for @math -edge-connected-orientability in the bounded-degree model, where an undirected graph @math is called @math -edge-connected-orientable if there exists an orientation @math of @math with a vertex @math such that @math contains @math arc-disjoint dipaths from @math to each vertex @math and @math arc-disjoint dipaths from each vertex @math to @math . A tester is called a one-sided error tester for @math if it always accepts a graph satisfying @math . We show, for @math and (proper) @math , any one-sided error tester for @math -fullness and @math -edge-connected-orientability requires @math queries. Let @math be a 3-uniform hypergraph of order @math and size @math , and let @math be a subset of vertices of @math . The set @math is a strong transversal in @math if @math contains at least two vertices from every edge of @math . The strong transversal number @math of @math is the minimum size of a strong transversal in @math . We show that @math , and we characterize the hypergraphs that achieve equality in this bound. In particular, we show that the Fano plane is the only connected 3-uniform hypergraph @math of order @math and size @math that achieves equality in this bound. A set @math of vertices in a graph @math is a double total dominating set of @math if every vertex of @math is adjacent to at least two vertices in @math . The minimum cardinality of a double total dominating set of @math is the double total domination number @math of @math . Let @math be a connected graph of order @math with minimum degree at least three. As an application of our hypergraph results, we show that @math with equality if and only if @math is the Heawood graph (equivalently, the incidence bipartite graph of the Fano plane). Further if @math is not the Heawood graph, we show that @math , while if @math is a cubic graph different from the Heawood graph, we show that @math , and this bound is sharp. We study a one-parameter family of discrete dynamical systems called the @math -color firefly cellular automata (FCAs), which were introduced recently by the author. At each discrete time @math , each vertex in a graph has a state in @math , and a special state @math is designated as the blinking' state. At step @math , simultaneously for all vertices, the state of a vertex increments from @math to @math unless @math and at least one of its neighbors is in the state @math . A central question about this system is that on what class of network topologies synchrony is guaranteed to emerge. In a previous work, we have shown that for @math , every @math -coloring on a finite tree synchronizes iff the maximum degree is less than @math , and asked whether this behavior holds for all @math . In this paper, we answer the question positively for @math and negatively for all @math by constructing counterexamples on trees with maximum degree at most @math .