Let G be a graph of order n, and let k≥1 be an integer. Let h:E(G)→[0,1] be a function. If ∑ e∋xh(e)=k holds for any x∈V (G), then we call G[Fh] a fractional k-factor of G with indicator function h where Fh ={e∈E(G):h(e)>0}. A graph G is called a fractional (k,m) -deleted graph if for every e∈E(H) , there exists a fractional k-factor G[Fh ] of G with indicator function h such that h(e)=0 , where H is any subgraph of G with m edges. The minimum degree of a vertex in G is denoted by δ(G) . For X⊆V (G), NG(X)=⋃ x∈XNG(x) . The binding number of G is defined by In this paper, it is proved that if then G is a fractional (k,m) -deleted graph. Furthermore, it is shown that this result is best possible in some sense.

Let G be a connected simple graph. The degree distance of G is defined as D′(G)=∑ u∈V (G)dG(u)DG(u), where DG(u) is the sum of distances between the vertex u and all other vertices in G and dG(u) denotes the degree of vertex u in G. In contrast to many established results on extremal properties of degree distance, few results in the literature deal with the degree distance of composite graphs. Towards closing this gap, we study the degree distance of some composite graphs here. We present explicit formulas for D′ (G) of three composite graphs, namely, double graphs, extended double covers and edge copied graphs.

Pooling designs are a very helpful tool for reducing the number of tests for DNA library screening. A disjunct matrix is usually used to represent the pooling design. In this paper, we construct a new family of disjunct matrices and prove that it has a good row to column ratio and error-tolerant property.

An ergodic Markov chain is proved to be the realization of a random walk in a directed graph subject to a synchronizing road coloring. The result ensures the existence of appropriate random mappings in Propp-Wilson's coupling from the past. The proof is based on the road coloring theorem. A necessary and sufficient condition for approximate preservation of entropies is also given.

In this paper, we use the product ⊗h in order to study super edge-magic labelings, bi-magic labelings and optimal k-equitable labelings. We establish, with the help of the product ⊗h, new relations between super edge-magic labelings and optimal k-equitable labelings and between super edge-magic labelings and edge bi-magic labelings. We also introduce new families of graphs that are inspired by the family of generalized Petersen graphs. The concepts of super bi-magic and r-magic labelings are also introduced and discussed, and open problems are proposed for future research.

A super edge-magic labeling of a graph G=(V,E) of order p and size q is a bijection f:V ∪E→{i}p+qi=1 such that: (1) f(u)+f(uv)+f(v)=k for all uv∈E; and (2) f(V )={i}pi=1. Furthermore, when G is a linear forest, the super edge-magic labeling of G is called strong if it has the extra property that if uv∈E(G) , u′,v′ ∈V (G) and dG (u,u′ )=dG (v,v′ )<+∞, then f(u)+f(v)=f(u′ )+f(v′ ). In this paper we introduce the concept of strong super edge-magic labeling of a graph G with respect to a linear forest F, and we study the super edge-magicness of an odd union of nonnecessarily isomorphic acyclic graphs. Furthermore, we find exponential lower bounds for the number of super edge-magic labelings of these unions. The case when G is not acyclic will be also considered.

The main aim of this paper is to establish conditions that are necessary and sufficient for the edge-connectivity of the Cartesian product of two graphs to equal the sum of the edge-connectivities of the factors. The paper also clarifies an issue that has arisen in the literature on Cartesian products of graphs.

We consider a serialized coin-tossing leader election algorithm that proceeds in rounds until a winner is chosen, or all contestants are eliminated. The analysis allows for either biased or fair coins. We find the exact distribution for the duration of any fixed contestant; asymptotically, it turns out to be a geometric distribution. Rice's method (an analytic technique) shows that the moments of the duration contain oscillations, which we give explicitly for the mean and variance. We also use convergence in the Wasserstein metric space to show that the distribution of the total number of coin flips (among all participants), suitably normalized, approaches a normal limiting random variable.

We analyze a class of signal-to-interference-and-noise-ratio (SINR) random graphs. These random graphs arise in the modeling packet transmissions in wireless networks. In contrast to previous studies on SINR graphs, we consider both a space and a time dimension. The spatial aspect originates from the random locations of the network nodes in the Euclidean plane. The time aspect stems from the random transmission policy followed by each network node and from the time variations of the wireless channel characteristics. The combination of these random space and time aspects leads to fluctuations of the SINR experienced by the wireless channels, which in turn determine the progression of packets in space and time in such a network. In this paper we study optimal paths in such wireless networks in terms of first passage percolation on this random graph. We establish both ‘positive’ and ‘negative’ results on the associated time constant. The latter determines the asymptotics of the minimum delay required by a packet to progress from a source node to a destination node when the Euclidean distance between the two tends to ∞. The main negative result states that this time constant is infinite on the random graph associated with a Poisson point process under natural assumptions on the wireless channels. The main positive result states that, when adding a periodic node infrastructure of arbitrarily small intensity to the Poisson point process, the time constant is positive and finite.

In this paper we study the number of random records in an arbitrary split tree (or, equivalently, the number of random cuttings required to eliminate the tree). We show that a classical limit theorem for the convergence of sums of triangular arrays to infinitely divisible distributions can be used to determine the distribution of this number. After normalization the distributions are shown to be asymptotically weakly 1-stable. This work is a generalization of our earlier results for the random binary search tree in Holmgren (2010), which is one specific case of split trees. Other important examples of split trees include m-ary search trees, quad trees, medians of (2k + 1)-trees, simplex trees, tries, and digital search trees.

Let Γ be a graph and let G be a vertex-transitive subgroup of the full automorphism group Aut(Γ) of Γ. The graph Γ is called G-normal if G is normal in Aut(Γ). In particular, a Cayley graph Cay(G, S) on a group G with respect to S is normal if the Cayley graph is R(G)-normal, where R(G) is the right regular representation of G. Let T be a non-abelian simple group and let G = Tℓ with ℓ ≥ 1. We prove that if every connected T-vertex-transitive cubic symmetric graph is T-normal, then every connected G-vertex-transitive cubic symmetric graph is G-normal. This result, among others, implies that a connected cubic symmetric Cayley graph on G is normal except for T ≅ A47 and a connected cubic G-symmetric graph is G-normal except for T ≅ A7, A15 or PSL(4, 2).

An interval in a combinatorial structure R is a set I of points that are related to every point in R∖I in the same way. A structure is simple if it has no proper intervals. Every combinatorial structure can be expressed as an inflation of a simple structure by structures of smaller sizes—this is called the substitution (or modular) decomposition. In this paper we prove several results of the following type: an arbitrary structure S of size n belonging to a class 𝒞 can be embedded into a simple structure from 𝒞 by adding at most f(n) elements. We prove such results when 𝒞 is the class of all tournaments, graphs, permutations, posets, digraphs, oriented graphs and general relational structures containing a relation of arity greater than two. The functions f(n) in these cases are 2, ⌈log 2(n+1)⌉, ⌈(n+1)/2⌉, ⌈(n+1)/2⌉, ⌈log 4(n+1)⌉, ⌈log 3(n+1)⌉ and 1, respectively. In each case these bounds are the best possible.

In this paper we study the size of the largest clique ω(G(n, α)) in a random graph G(n, α) on n vertices which has power-law degree distribution with exponent α. We show that, for ‘flat’ degree sequences with α > 2, with high probability, the largest clique in G(n, α) is of a constant size, while, for the heavy tail distribution, when 0 < α < 2, ω(G(n, α)) grows as a power of n. Moreover, we show that a natural simple algorithm with high probability finds in G(n, α) a large clique of size (1 − o(1))ω(G(n, α)) in polynomial time.

We investigate the final size distribution of the SIR (susceptible-infected-recovered) epidemic model in the critical regime. Using the integral representation of Martin-Löf (1998) for the hitting time of a Brownian motion with parabolic drift, we derive asymptotic expressions for the final size distribution that capture the effect of the initial number of infectives and the closeness of the reproduction number to zero. These asymptotics shed light on the bimodularity of the limiting density of the final size observed in Martin-Löf (1998). We also discuss the connection to the largest component in the Erdős-Rényi random graph, and, using this connection, find an integral expression of the Laplace transform of the normalized Brownian excursion area in terms of Airy functions.

A dynamic model for a random network evolving in continuous time is defined, where new vertices are born and existing vertices may die. The fitness of a vertex is defined as the accumulated in-degree of the vertex and a new vertex is connected to an existing vertex with probability proportional to a function b of the fitness of the existing vertex. Furthermore, a vertex dies at a rate given by a function d of its fitness. Using results from the theory of general branching processes, an expression for the asymptotic empirical fitness distribution {pk} is derived and analyzed for a number of specific choices of b and d. When b(i) = i + α and d(i) = β, that is, linear preferential attachment for the newborn and random deaths, then pk ∼ k-(2+α). When b(i) = i + 1 and d(i) = β(i + 1), with β < 1, then pk ∼ (1 + β)−k, that is, if the death rate is also proportional to the fitness, then the power-law distribution is lost. Furthermore, when b(i) = i + 1 and d(i) = β(i + 1)γ, with β, γ < 1, then logpk ∼ -kγ, a stretched exponential distribution. The momentaneous in-degrees are also studied and simulations suggest that their behaviour is qualitatively similar to that of the fitnesses.

The expansion constant of a simple graph G of order n is defined as where denotes the set of edges in G between the vertex subset S and its complement . An expander family is a sequence {Gi} of d-regular graphs of increasing order such that h(Gi)>ϵ for some fixed ϵ>0. Existence of such families is known in the literature, but explicit construction is nontrivial. A folklore theorem states that there is no expander family of circulant graphs only. In this note, we provide an elementary proof of this fact by first estimating the second largest eigenvalue of a circulant graph, and then employing Cheeger’s inequalities where G is a d-regular graph and λ2(G) denotes the second largest eigenvalue of G. Moreover, the associated equality cases are discussed.

Let n points be placed independently in d-dimensional space according to the density f(x) = Ade−λ||x||α, λ, α > 0, x ∈ ℝd, d ≥ 2. Let dn be the longest edge length of the nearest-neighbor graph on these points. We show that (λ−1 log n)1−1/α dn - bn converges weakly to the Gumbel distribution, where bn ∼ ((d − 1)/λα) log log n. We also prove the following strong law for the normalized nearest-neighbor distance d̃n = (λ−1 log n)1−1/α dn/ log log n: (d − 1)/αλ ≤ lim infn→∞d̃n ≤ lim supn→∞d̃n ≤ d/αλ almost surely. Thus, the exponential rate of decay α = 1 is critical, in the sense that, for α > 1, dn → 0, whereas, for α ≤ 1, dn → ∞ almost surely as n → ∞.

We study first passage percolation (FPP) on the configuration model (CM) having power-law degrees with exponent τ ∈ [1, 2) and exponential edge weights. We derive the distributional limit of the minimal weight of a path between typical vertices in the network and the number of edges on the minimal-weight path, both of which can be computed in terms of the Poisson-Dirichlet distribution. We explicitly describe these limits via construction of infinite limiting objects describing the FPP problem in the densely connected core of the network. We consider two separate cases, the original CM, in which each edge, regardless of its multiplicity, receives an independent exponential weight, and the erased CM, for which there is an independent exponential weight between any pair of direct neighbors. While the results are qualitatively similar, surprisingly, the limiting random variables are quite different. Our results imply that the flow carrying properties of the network are markedly different from either the mean-field setting or the locally tree-like setting, which occurs as τ > 2, and for which the hopcount between typical vertices scales as log n. In our setting the hopcount is tight and has an explicit limiting distribution, showing that information can be transferred remarkably quickly between different vertices in the network. This efficiency has a down side in that such networks are remarkably fragile to directed attacks. These results continue a general program by the authors to obtain a complete picture of how random disorder changes the inherent geometry of various random network models; see Aldous and Bhamidi (2010), Bhamidi (2008), and Bhamidi, van der Hofstad and Hooghiemstra (2009).

A random intersection graph G(n, m, p) is defined on a set V of n vertices. There is an auxiliary set W consisting of m objects, and each vertex v ∈ V is assigned a random subset of objects Wv ⊆ W such that w ∈ Wv with probability p, independently for all v ∈ V and all w ∈ W. Given two vertices v1, v2 ∈ V, we set v1 ∼ v2 if and only if Wv1 ∩ Wv2 ≠ ∅. We use Stein's method to obtain an upper bound on the total variation distance between the distribution of the number of h-cliques in G(n, m, p) and a related Poisson distribution for any fixed integer h.