共查询到20条相似文献,搜索用时 31 毫秒
1.
Paul Erdős Norbert Sauer Jonathan Schaer Joel Spencer 《Journal of Combinatorial Theory, Series B》1975,18(2):180-183
The graph G has star number n if any n vertices of G belong to a subgraph which is a star. Let f(n, k) be the smallest number m such that the complete graph on m vertices can be factorized into k factors with star number n. In the present paper we prove that . 相似文献
2.
D.T. Busolini 《Journal of Combinatorial Theory, Series B》1978,24(3):286-289
Let α(k, p, h) be the maximum number of vertices a complete edge-colored graph may have with no color appearing more than k times at any vertex and not containing a complete subgraph on p vertices with no color appearing more than h times at any vertex. We prove that and obtain a stronger upper bound for α(k, 3, 1). Further, we prove that a complete edge-colored graph with n vertices contains a complete subgraph on p vertices in which no two edges have the same color if where ei is the number of edges of color i, 1 ≤ i ≤ t. 相似文献
3.
4.
Edward A Bender Herbert S Wilf 《Journal of Algorithms in Cognition, Informatics and Logic》1985,6(2):275-282
The graph coloring problem is: Given a positive integer K and a graph G. Can the vertices of G be properly colored in K colors? The problem is NP-complete. The average behavior of the simplest backtrack algorithm for this problem is studied. Average run time over all graphs is known to be bounded. Average run time over all graphs with n vertices and q edges behaves like . It is shown that similar results hold for all higher moments of the run time distribution. For all graphs and for graphs where lim exists, the run time has a limiting disibution as n → ∞. 相似文献
5.
M Meyniel 《Journal of Combinatorial Theory, Series B》1973,14(2):137-147
In this article we prove that a sufficient condition for an oriented strongly connected graph with n vertices to be Hamiltonian is: (1) for any two nonadjacent vertices x and y. 相似文献
6.
Nemhauser and Trotter [12] proposed a certain easily-solved linear program as a relaxation of the node packing problem. They showed that any variables receiving integer values in an optimal solution to this linear program also take on the same values in an optimal solution to the (integer) node packing problem. Let π be the property of graphs defined as follows: a graph G has property π if and only if there is a unique optimal solution to the linear-relaxation problem, and this solution is completely fractional. If a graph G has property π then no information about the node packing problem on G is gained by solving the linear relaxation. We calculate the asymptotic probability that a certain type of ‘sparse’ random graph has property π, as the number of its nodes tends to infinity. Let m be a fixed positive integer, and consider the following random graph on the node set {1,2 …, n}). We join each node, j say, to exactly m other nodes chosen randomly with replacement, by edges oriented away from j; we denote by Gn(m) the undirected graph obtained by deleting all orientations and allowing all parallel edges to coalesce. We show that, as n → ∞, and we conjecture that . 相似文献
7.
Joel E. Cohen 《Discrete Mathematics》1982,40(1):21-24
Let G be a graph on v labelled vertices with E edges, without loops or multiple edges. Let v → ∞ and let E=E(v) be a function of v such that lim . The limit of the probability that a random graph is a unit interval graph, indifference graph or proper interval graph is exp(?c3). 相似文献
8.
Siddani Bhaskara Rao 《Journal of Combinatorial Theory, Series B》1979,27(1):13-41
A graph G is said to be highly constricted if there exists a nonempty subset S of vertices such that (i) G ? S has more than |S| components, (ii) S induces the complete graph, and (iii) for every u ∈ S and v ? S, we have dG(u) > dG(v), where dG(u) denotes the degree of u in G. In this paper it is shown that a non-hamiltonian self-complementary graph G of order p is highly constricted, unless p = 4N and G is a particular graph . It is also proved that if G is a self-complementary graph of order p(≥8) and π its degree sequence, then G is pancyclic if π has a realization with a hamiltonian cycle, and G has a 2-factor if π has a realization with a 2-factor, unless p = 4N and . 相似文献
9.
S. Ihara 《Journal of multivariate analysis》1974,4(1):74-87
The message m = {m(t)} is a Gaussian process that is to be transmitted through the white Gaussian channel with feedback: . Under the average power constraint, , we construct causally the optimal coding, in the sense that the mutual information It(m, Y) between the message m and the channel output Y (up to t) is maximized. The optimal coding is presented by , where and A(s) is a positive function such that . 相似文献
10.
In this paper we solve a conjecture of P. Erdös by showing that if a graph Gn has n vertices and at least edges, then G contains a cycle C2l of length 2l for every integer . Apart from the value of the constant this result is best possible. It is obtained from a more general theorem which also yields corresponding results in the case where Gn has only cn(log n)α edges (α ≥ 1). 相似文献
11.
《Journal of Combinatorial Theory, Series B》1986,40(2):187-195
The usual linear relaxation of the node-packing problem contains no useful information when the underlying graph G has the property of “bicriticality.” We consider a sparse random graph Gn(m) obtained in the usual way from a random directed graph with fixed out-degree m and show that the probability that Gn(2) is bicritical tends to as n→∞. This confirms a conjecture by G. R. Grimmett and W. R. Pulleyblank (Oper. Res. Lett., in press). 相似文献
12.
Steven F Arnold 《Statistics & probability letters》1985,3(5):275-279
Suppose that a statistical decision problem is invariant under a group of transformations g?G. T (X) is equivariant if there exists such that . We show that the minimal sufficient statistic is equivalent and that if T(X) is an equivariant sufficient statistics and d(X) is invariant under G, then is invariant under . 相似文献
13.
Let be the number of conjugacy classes of elements in SL(2, ) with trace t, and let be the number of equivalence classes of binary quadratic forms with discriminant n. Then for t≠±2, . For all real θ > 0 there is a T(θ) such that whenever |t|>T(θ), . There is a c>0 such that for those t such that t2?4 is squarefree, . 相似文献
14.
W Fernandez de la Vega 《Journal of Combinatorial Theory, Series B》1983,35(3):328-332
For any tournament T on n vertices, let h(T) denote the maximum number of edges in the intersection of T with a transitive tournament on the same vertex set. Sharpening a previous result of Spencer, it is proved that, if Tn denotes the random tournament on n vertices, then, as n → ∞. 相似文献
15.
Best upper and lower bounds, as functions of n, are obtained for the quantities and , where β2(G) denotes the total matching number and α2(G) the total covering number of any graph G with n vertices and with complementry graph ?.The best upper bound is obtained also for α2(G)+β2(G), when G is a connected graph. 相似文献
16.
CAI Mao-cheng 《Discrete Mathematics》1984,49(1):15-20
Given a finite loopless graph G (resp. digraph D), let σ(G), ?(G) and ψ(D) denote the minimal cardinalities of a completely separating system of G, a separating system of G and a separating system of D, respectively. The main results of this paper are: denotes the chromatic number of G. (ii) All the problems of determining σ(G), ?(G) and ψ(D) are NP-complete. 相似文献
17.
M Ajtai J Komlós J Pintz J Spencer E Szemerédi 《Journal of Combinatorial Theory, Series A》1982,32(3):321-335
Let G be a (k + 1)-graph (a hypergraph with each hyperedge of size k + 1) with n vertices and average degreee t. Assume k ? t ? n. If G is uncrowded (contains no cycle of size 2, 3, or 4) then there exists and independent set of size . 相似文献
18.
Z Füredi 《Journal of Combinatorial Theory, Series B》1983,34(2):187-190
Let f(n) denote the maximum number of edges of a graph on n vertices not containing a circuit of length 4. It is well known that . The old conjecture is proved for infinitely many q (whenever q = 2k). 相似文献
19.
David Barnette 《Discrete Mathematics》1974,10(1):9-13
The distance between two vertices of a polytope is the minimum number of edges in a path joining them. The diameter of a polytope is the greatest distance between two vertices of the polytope. We show that if P is a d-dimensional polytope with n facets, then the diameter of P is at most . 相似文献
20.
An algorithm is described which generates a random labeled cubic graph on n vertices. Also described is a procedure which, if successful, generates a random (0,1)-matrix with prescribed row and column sums. The latter yields procedures which, if successful, generate random labeled graphs with specified degree sequence and random labeled bipartite graphs with specified degree sequences. These procedures can be implemented so that each trial requires time which is linear in the number of vertices plus edges, but in generating a random r-regular graph, the probability of success of a given trial is about , which is prohibitively small for large r. Comparisons are made between the complexities of the two methods of generating random cubic graphs. The two general schemes presented derive from methods which have been used to enumerate regular graphs, both asymptotically and exactly. 相似文献