共查询到20条相似文献,搜索用时 15 毫秒
1.
d -regular graph G, let M be chosen uniformly at random from the set of all matchings of G, and for let be the probability that M does not cover x.
We show that for large d, the 's and the mean μ and variance of are determined to within small tolerances just by d and (in the case of μ and ) :
Theorem. For any d-regular graph G,
(a)
, so that ,
(b)
,
where the rates of convergence depend only on d.
Received: April 12, 1996 相似文献
2.
r -regular n-vertex graph G with random independent edge lengths, each uniformly distributed on (0, 1). Let mst(G) be the expected length of a minimum spanning tree. We show that mst(G) can be estimated quite accurately under two distinct circumstances. Firstly, if r is large and G has a modest edge expansion property then , where . Secondly, if G has large girth then there exists an explicitly defined constant such that . We find in particular that .
Received: Februray 9, 1998 相似文献
3.
4.
Omran Ahmadi 《Linear algebra and its applications》2009,430(1):547-3232
It is shown that only a fraction of 2-Ω(n) of the graphs on n vertices have an integral spectrum. Although there are several explicit constructions of such graphs, no upper bound for their number has been known. Graphs of this type play an important role in quantum networks supporting the so-called perfect state transfer. 相似文献
5.
choice number of a graph G is the minimum integer k such that for every assignment of a set S(v) of k colors to every vertex v of G, there is a proper coloring of G that assigns to each vertex v a color from S(v). It is shown that the choice number of the random graph G(n, p(n)) is almost surely whenever . A related result for pseudo-random graphs is proved as well. By a special case of this result, the choice number (as well
as the chromatic number) of any graph on n vertices with minimum degree at least in which no two distinct vertices have more than common neighbors is at most .
Received: October 13, 1997 相似文献
6.
C
2
k
-free subgraph of a random graph may have, obtaining best possible results for a range of p=p(n). Our estimates strengthen previous bounds of Füredi [12] and Haxell, Kohayakawa, and Łuczak [13]. Two main tools are used
here: the first one is an upper bound for the number of graphs with large even-girth, i.e., graphs without short even cycles, with a given number of vertices and edges, and satisfying a certain additional pseudorandom
condition; the second tool is the powerful result of Ajtai, Komlós, Pintz, Spencer, and Szemerédi [1] on uncrowded hypergraphs
as given by Duke, Lefmann, and R?dl [7].
Received: February 17, 1995 相似文献
7.
Christian Borgs Jennifer T. Chayes Remco van der Hofstad Gordon Slade Joel Spencer 《Combinatorica》2006,26(4):395-410
We study random subgraphs of the n-cube {0,1}n, where nearest-neighbor edges are occupied with probability p. Let pc(n) be the value of p for which the expected size of the component containing a fixed vertex attains the value λ2n/3, where λ is a small positive constant. Let ε=n(p−pc(n)). In two previous papers, we showed that the largest component inside a scaling window given by |ε|=Θ(2−n/3) is of size Θ(22n/3), below this scaling window it is at most 2(log 2)nε−2, and above this scaling window it is at most O(ε2n). In this paper, we prove that for
the size of the largest component is at least Θ(ε2n), which is of the same order as the upper bound. The proof is based on a method that has come to be known as “sprinkling,”
and relies heavily on the specific geometry of the n-cube. 相似文献
8.
in the probability space ? Second, does there exist a constant such that the -chromatic number of the random graph is almost surely ? The second question was posed by Scheinerman (SIAM J. Discrete Math.
5 (1992) 74–80).
The two questions are closely related and, in the case p=1/2, have already been answered. Pr?mel and Steger (Contemporary Mathematics
147, Amer. Math. Soc., Providence, 1993, pp. 167-178), Alekseev (Discrete Math. Appl.
3 (1993) 191-199) and the authors ( Algorithms and Combinatorics
14 Springer-Verlag (1997) 70–78) provided an approximation which was used by the authors (Random Structures and Algorithms
6 (1995) 353–356) to answer the -chromatic question for p=1/2. However, the approximating properties that work well for p=1/2 fail completely for .
In this paper we describe a class of properties that do approximate in , in the following sense: for any desired accuracy of approximation, there is a property in our class that approximates to this level of accuracy. As may be expected, our class includes the simple properties used in the case p=1/2.
The main difficulty in answering the second of our two questions, that concerning the -chromatic number of , is that the number of small -graphs in has, in general, large variance. The variance is smaller if we replace by a simple approximation, but it is still not small enough. We overcome this by considering instead a very rigid non-hereditary
subproperty of the approximating property; the variance of the number of small -graphs is small enough for our purpose, and the structure of is sufficiently restricted to enable us to show this by a fine analysis.
Received April 20, 1999 相似文献
9.
The goal of the paper is to initiate research towards a general, Blow-up Lemma type embedding statement for pseudo-random graphs with sublinear degrees. In particular, we show that if the second eigenvalue of a d-regular graph G on 3n vertices is at most cd
3/n
2 log n, for some sufficiently small constant c > 0, then G contains a triangle factor. We also show that a fractional triangle factor already exists if < 0.1d
2/n. The latter result is seen to be best possible up to a constant factor, for various values of the degree d = d(n).* Supported by a USA-Israeli BSF grant, by a grant from the Israel Science Foundation and by a Bergmann Memorial Award. Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Research supported in part by NSF grant DMS 99-70270 and by the joint Berlin/Zurich graduate program Combinatorics, Geometry, Computation, financed by the German Science Foundation (DFG) and ETH Zürich. 相似文献
10.
《Journal of Graph Theory》2018,87(1):35-45
A graph is called equimatchable if all of its maximal matchings have the same size. Kawarabayashi, Plummer, and Saito showed that the only connected equimatchable 3‐regular graphs are K4 and K3, 3. We extend this result by showing that for an odd positive integer r, if G is a connected equimatchable r‐regular graph, then . Also it is proved that for an even r, a connected triangle‐free equimatchable r‐regular graph is isomorphic to one of the graphs C5, C7, and . 相似文献
11.
Ben Johnsen 《BIT Numerical Mathematics》1991,31(1):15-31
A binary tree is characterized as a sequence of graftings. This sequence is used to construct a Markov chain useful for generating trees with uniform probability. A code for the Markov chain gives a characteristic binary string for the trees. The main result is the calculation of the transition probabilities of the Markov chain. Some applications are pointed out. 相似文献
12.
The Diameter of a Scale-Free Random
Graph 总被引:1,自引:0,他引:1
We consider a random graph process in which vertices are
added to the graph one at a time and joined to a fixed number
m of earlier vertices, where
each earlier vertex is chosen with probability proportional to
its degree. This process was introduced by Barabási and Albert
[3], as a simple model of the growth of real-world graphs such
as the world-wide web. Computer experiments presented by
Barabási, Albert and Jeong [1,5] and heuristic arguments given
by Newman, Strogatz and Watts [23] suggest that after
n steps the resulting graph
should have diameter approximately logn. We show that while this holds for
m=1, for
m2 the diameter is
asymptotically log n/log
logn.* Research supported in part by NSF grant no.
DSM9971788 相似文献
13.
We show that the maximum vertex degree in a random
3-connected planar triangulation is concentrated in an interval
of almost constant width. This is a slightly weaker type of
result than our earlier determination of the limiting
distribution of the maximum vertex degree in random planar maps
and in random triangulations of a (convex) polygon. We also
derive sharp concentration results on the number of vertices of
given degree in random planar maps of all three types. Some
sharp concentration results about general submaps in 3-connected
triangulations are also given.* Research supported by NSERC and Australian
Research Council Research supported by the Australian Research
Council 相似文献
14.
《Journal of Graph Theory》2018,87(1):5-17
A 2‐cell embedding of a graph Γ into a closed (orientable or nonorientable) surface is called regular if its automorphism group acts regularly on the flags. In this article, we classify the regular embeddings of the complete multipartite graph . We show that if the number of partite sets is greater than 3, there exists no such embedding; and if the number of partite sets is 3, for any n, there exist one orientable regular embedding and one nonorientable regular embedding of up to isomorphism. 相似文献
15.
Let P
n be the order determined by taking a random graph G on {1, 2,..., n}, directing the edges from the lesser vertex to the greater (as integers), and then taking the transitive closure of this relation. We call such and ordered set a random graph order. We show that there exist constants c, and °, such that the expected height and set up number of P
n are sharply concentrated around cn and °n respectively. We obtain the estimates: .565<c<.610, and .034<°<.289. We also discuss the width, dimension, and first-order properties of P
n. 相似文献
16.
Colin McDiarmid 《Combinatorica》2007,27(2):183-203
In the radio channel assignment problems considered here, we must assign a ‘channel’ from the set 1,2,... of positive integers
to each of n transmitters, and we wish to minimise the span of channels used, subject to the assignment leading to an acceptable level
of interference. A standard form of this problem is the ‘constraint matrix’ model. The simplest case of this model (the 0,
1 case) is essentially graph colouring. We consider here a random model for the next simplest case (with lengths 0, 1 or 2),
and determine the asymptotic behaviour of the span of channels needed as n→∞. We find that there is a ‘phase change’ in this behaviour, depending on the probabilities for the different lengths. 相似文献
17.
whenever is a fixed positive irrational. This raises the question what zero-one valued functions on the positive irrationals arise as the limit probability of a first order sentence on these graphs. Here we prove two necessary conditions on these functions, a number-theoretic and a complexity condition. We hope to prove in a subsequent paper that these conditions together with two simpler and previously proved conditions are also sufficient and thus they constitute a characterization. Received October 2, 1998 相似文献
18.
Consider a complete graph on n vertices with edge weights chosen randomly and independently from an exponential distribution with parameter 1. Fix k vertices and consider the minimum weight Steiner tree which contains these vertices. We prove that with high probability the weight of this tree is (1+o(1))(k-1)(log n-log k)/n when k =o(n) and n.* Research supported in part by NSF grant DSM9971788 Research supported in part by NSF grants DMS-0106589, CCR-9987845 and by the State of New Jersey. Part of this research was done while visiting IBM T. J. Watson Research Center. 相似文献
19.
《Quaestiones Mathematicae》2013,36(2):159-164
AbstractThe Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence so(G),s1 (G),…,8p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized. 相似文献
20.
Dedicated to the memory of Paul Erdős
We provide an elementary proof of the fact that the ramsey number of every bipartite graph H with maximum degree at most is less than . This improves an old upper bound on the ramsey number of the n-cube due to Beck, and brings us closer toward the bound conjectured by Burr and Erdős. Applying the probabilistic method
we also show that for all and there exists a bipartite graph with n vertices and maximum degree at most whose ramsey number is greater than for some absolute constant c>1.
Received December 1, 1999
RID="*"
ID="*" Supported by NSF grant DMS-9704114
RID="**"
ID="**" Supported by KBN grant 2 P03A 032 16 相似文献