Home About us Contact
|
Home About us Contact | ||
|
|
||
Degree D (degree + d)
Selected AbstractsThe minimal complementation property above 0,MLQ- MATHEMATICAL LOGIC QUARTERLY, Issue 5 2005Andrew E. M. Lewis Abstract Let us say that any (Turing) degree d > 0satisfies the minimal complementation property (MCP) if for every degree 0 < a < d there exists a minimal degree b < d such that a , b = d (and therefore a , b = 0). We show that every degree d , 0, satisfies MCP. (© 2005 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim) [source] Isomorphisms of the De Bruijn digraph and free-space optical networksNETWORKS: AN INTERNATIONAL JOURNAL, Issue 3 2002D. Coudert Abstract The de Bruijn digraph B(d, D) has degree d, diameter D, dD vertices, and dD+1 arcs. It is usually defined by words of size D on an alphabet of cardinality d, through a cyclic left-shift permutation on the words, after which the rightmost symbol is changed. In this paper, we show that any digraph defined on words of a given size, through an arbitrary permutation on the alphabet and an arbitrary permutation on the word indices, is isomorphic to the de Bruijn digraph, provided that this latter permutation is cyclic. We use this result to improve from O(dD+1) to the number of lenses required for the implementation of B(d, D) by the Optical Transpose Interconnection System proposed by Marsden et al. [Opt Lett 18 (1993), 1083,1085]. © 2002 Wiley Periodicals, Inc. [source] The evolution of the mixing rate of a simple random walk on the giant component of a random graphRANDOM STRUCTURES AND ALGORITHMS, Issue 1 2008N. Fountoulakis Abstract In this article we present a study of the mixing time of a random walk on the largest component of a supercritical random graph, also known as the giant component. We identify local obstructions that slow down the random walk, when the average degree d is at most O(), proving that the mixing time in this case is ,((n/d)2) asymptotically almost surely. As the average degree grows these become negligible and it is the diameter of the largest component that takes over, yielding mixing time ,(n/d) a.a.s.. We proved these results during the 2003,04 academic year. Similar results but for constant d were later proved independently by Benjamini et al. in 3. © 2008 Wiley Periodicals, Inc. Random Struct. Alg., 2008 [source] The degree sequences and spectra of scale-free random graphsRANDOM STRUCTURES AND ALGORITHMS, Issue 2 2006Jonathan Jordan Abstract We investigate the degree sequences of scale-free random graphs. We obtain a formula for the limiting proportion of vertices with degree d, confirming non-rigorous arguments of Dorogovtsev, Mendes, and Samukhin (Phys Rev Lett 85 (2000), 4633). We also consider a generalization of the model with more randomization, proving similar results. Finally, we use our results on the degree sequence to show that for certain values of parameters localized eigenfunctions of the adjacency matrix can be found. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006 [source] The degree sequence of a scale-free random graph processRANDOM STRUCTURES AND ALGORITHMS, Issue 3 2001B´ela Bollobás Recently, Barabási and Albert [2] suggested modeling complex real-world networks such as the worldwide web as follows: consider a random graph process in which vertices are added to the graph one at a time and joined to a fixed number of earlier vertices, selected with probabilities proportional to their degrees. In [2] and, with Jeong, in [3], Barabási and Albert suggested that after many steps the proportion P(d) of vertices with degree d should obey a power law P(d),d,,. They obtained ,=2.9±0.1 by experiment and gave a simple heuristic argument suggesting that ,=3. Here we obtain P(d) asymptotically for all d,n1/15, where n is the number of vertices, proving as a consequence that ,=3. © 2001 John Wiley & Sons, Inc. Random Struct. Alg., 18, 279,290, 2001 [source] | ||||||||||