共查询到20条相似文献,搜索用时 343 毫秒
1.
Let k be a fixed, positive integer. We give an algorithm which computes the Tutte polynomial of any graph G of treewidth at most k in time O( n2+7 log2 c), where c is twice the number of partitions of a set with 3 k + 3 elements and n the number of vertices of G. 相似文献
2.
Let G be a k-edge-connected graph of order n. If k4log 2 n then G has a nowhere-zero 3-flow. 相似文献
3.
A connected graph is doubly connected if its complement is also connected. The following Ramsey-type theorem is proved in this paper. There exists a function h( n), defined on the set of integers exceeding three, such that every doubly connected graph on at least h( n) vertices must contain, as an induced subgraph, a doubly connected graph, which is either one of the following graphs or the complement of one of the following graphs: - (1) Pn, a path on n vertices;
- (2) K1,ns, the graph obtained from K1,n by subdividing an edge once;
- (3) K2,ne, the graph obtained from K2,n by deleting an edge;
- (4) K2,n+, the graph obtained from K2,n by adding an edge between the two degree-n vertices x1 and x2, and a pendent edge at each xi.
Two applications of this result are also discussed in the paper. 相似文献
4.
We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R( G,ρ)/ F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D( R( G,ρ)/ F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2 k2, in which the route degree is
, the total number of routes is O( k2n) and D( R( G,λ)/ F)3 for any fault set F (| F|< k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is
, the total number of routes is O( n) and D( R( G,λ′)/{ f})3 for any fault f. We also show that we can construct a routing ρ 1 for every n-node biconnected graph, in which the total number of routes is O( n) and D( R( G,ρ 1)/{ f})2 for any fault f, and a routing ρ 2 (using ρ 1) for every n-node biconnected graph, in which the route degree is
, the total number of routes is
and D( R( G,ρ 2)/{ f})2 for any fault f. 相似文献
5.
A total cover of a graph G is a subset of V( G) E( G) which covers all elements of V( G) E( G). The total covering number 2( G) of a graph G is the minimum cardinality of a total cover in G. In [1], it is proven that 2( G)[ n/2] for a connected graph G of order n. Here we consider the extremal case and give some properties of connected graphs which have a total covering number [ n/2]. We prove that such a graph with even order has a 1-factor and such a graph with odd order is factor-critical. 相似文献
6.
Let S1 and S2 be two ( k-1)-subsets in a k-uniform hypergraph H. We call S1 and S2 strongly or middle or weakly independent if H does not contain an edge e ∈ E( H) such that S1 ∩ e ≠∅ and S2 ∩ e ≠∅ or e ⊆ S1 ∪ S2 or e ⊇ S1 ∪ S2, respectively. In this paper, we obtain the following results concerning these three independence. (1) For any n ≥ 2 k2- k and k ≥ 3, there exists an n-vertex k-uniform hypergraph, which has degree sum of any two strongly independent ( k-1)-sets equal to 2 n-4( k-1), contains no perfect matching; (2) Let d ≥ 1 be an integer and H be a k-uniform hypergraph of order n ≥ kd+( k-2) k. If the degree sum of any two middle independent ( k-1)-subsets is larger than 2( d-1), then H contains a d-matching; (3) For all k ≥ 3 and sufficiently large n divisible by k, we completely determine the minimum degree sum of two weakly independent ( k-1)-subsets that ensures a perfect matching in a k-uniform hypergraph H of order n. 相似文献
7.
We form squares from the product of integers in a short interval [ n, n + tn], where we include n in the product. If p is prime, p| n, and ( 2p) > n, we prove that p is the minimum tn. If no such prime exists, we prove tn √5 n when n> 32. If n = p(2 p − 1) and both p and 2 p − 1 are primes, then tn = 3 p> 3 √ n/2. For n( n + u) a square > n2, we conjecture that a and b exist where n < a < b < n + u and nab is a square (except n = 8 and N = 392). Let g2( n) be minimal such that a square can be formed as the product of distinct integers from [ n, g2( n)] so that no pair of consecutive integers is omitted. We prove that g2( n) 3 n − 3, and list or conjecture the values of g2( n) for all n. We describe the generalization to kth powers and conjecture the values for large n. 相似文献
8.
A cover (bipartite) of a graph G is a family of complete bipartite subgraphs of G whose edges cover G's edges. G's bipartite dimension d(G) is the minimum cardinality of a cover, and its bipartite degree η(G) is the minimum over all covers of the maximum number of covering members incident to a vertex. We prove that d( G) equals the Boolean interval dimension of the irreflexive complement of G, identify the 21 minimal forbidden induced subgraphs for d 2, and investigate the forbidden graphs for d n that have the fewest vertices. We note that for complete graphs, d( Kn) = [log 2n], η( Kn) = d( Kn) for n 16, and η( Kn) is unbounded. The list of minimal forbidden induced subgraphs for η 2 is infinite. We identify two infinite families in this list along with all members that have fewer than seven vertices. 相似文献
9.
Suppose G is a graph. The chromatic Ramsey number rc( G) of G is the least integer m such that there exists a graph F of chromatic number m for which the following is true: for any 2-colouring of the edges of F there is a monochromatic subgraph isomorphic to G. Let Mn = min[ rc( G): χ( G) = n]. It was conjectured by Burr et al. (1976) that Mn = ( n − 1) 2 + 1. This conjecture has been confirmed previously for n 4. In this paper, we shall prove that the conjecture is true for n = 5. We shall also improve the upper bounds for M6 and M7. 相似文献
10.
Let D = ( V1, V2; A) be a directed bipartite graph with | V1| = | V2| = n 2. Suppose that dD( x) + dD( y) 3 n + 1 for all x ε V1 and y ε V2. Then D contains two vertex-disjoint directed cycles of lengths 2 n1 and 2 n2, respectively, for any positive integer partition n = n1 + n2. Moreover, the condition is sharp for even n and nearly sharp for odd n. 相似文献
11.
A graph G on at least 2 n + 2 vertices in n- extendable if every set of n independent edges extends to (i.e., is a subset of) a perfect matching in G. It is known that no planar graph is 3-extendable. In the present paper we continue to study 2-extendability in the plane. Suppose independent edges e1 and e2 are such that the removal of their endvertices leaves at least one odd component Co. The subgraph G[ V( Co) V( e1) V( e2)] is called a generalized butterfly (or gbutterfly). Clearly, a 2-extendable graph can contain no gbutterfly. The converse, however, is false. We improve upon a previous result by proving that if G is 4-connected, locally connected and planar with an even number of vertices and has no gbutterfly, it is 2-extendable. Sharpness with respect to the various hypotheses of this result is discussed. 相似文献
12.
We present a network of delay log 2N, whose comparators have only log 2N different lengths with maximum length N/2. This network is log-sequential in that it will sort N data items when they are passed through it log 2Ntimes. The design, which is related to the Batcher odd-even merge, is distinctly different from the first known example of a log-delay log-sequential network, due to Dowd, Perl, Rudolf, and Saks. It is quite probably the best possible sorting network. 相似文献
13.
A graph G is said to be cyclable if for each orientation
of G, there exists a set S of vertices such that reversing all the arcs of
with one end in S results in a hamiltonian digraph. Let G be a 3-connected graph of order n36. In this paper, we show that if for any three independent vertices x1, x2 and x3, | N( x1) N( x2)|+| N( x2) N( x3)|+| N( x3) N( x1)|2 n+1, then G is cyclable. 相似文献
14.
Let π i : Ei→ M, i=1,2, be oriented, smooth vector bundles of rank k over a closed, oriented n-manifold with zero sections si : M→ Ei. Suppose that U is an open neighborhood of s1( M) in E1 and F : U→ E2 a smooth embedding so that π 2Fs1 : M→ M is homotopic to a diffeomorphism f. We show that if k>[( n+1)/2]+1 then E1 and the induced bundle f*E2 are isomorphic as oriented bundles provided that f have degree +1; the same conclusion holds if f has degree −1 except in the case where k is even and one of the bundles does not have a nowhere-zero cross-section. For n≡0(4) and [( n+1)/2]+1< kn we give examples of nonisomorphic oriented bundles E1 and E2 of rank k over a homotopy n-sphere with total spaces diffeomorphic with orientation preserved, but such that E1 and f*E2 are not isomorphic oriented bundles. We obtain similar results and counterexamples in the more difficult limiting case where k=[( n+1)/2]+1 and M is a homotopy n-sphere. 相似文献
15.
We study the problem of selecting one of the r best of n rankable individuals arriving in random order, in which selection must be made with a stopping rule based only on the relative ranks of the successive arrivals. For each r up to r=25, we give the limiting (as n→∞) optimal risk (probability of not selecting one of the r best) and the limiting optimal proportion of individuals to let go by before being willing to stop. (The complete limiting form of the optimal stopping rule is presented for each r up to r=10, and for r=15, 20 and 25.) We show that, for large n and r, the optical risk is approximately (1− t*) r, where t*≈0.2834 is obtained as the roof of a function which is the solution to a certain differential equation. The optimal stopping rule τ r,n lets approximately t*n arrivals go by and then stops ‘almost immediately’, in the sense that τ r,n/ n→ t* in probability as n→∞, r→∞ 相似文献
16.
For a connected graph G with n vertices, let {λ 1,λ 2,…,λ r} be the set of distinct positive eigenvalues of the Laplacian matrix of G. The Hoffman number μ( G) of G is defined by μ( G)=λ 1λ 2…λ r/ n. In this paper, we study some properties and applications of the Hoffman number. 相似文献
17.
Optimal diagonal scaling of an n× n matrix A consists in finding a diagonal matrix D that minimizes a condition number of AD. Often a nearly optimal scaling of A is achieved by taking a diagonal matrix D1 such that all diagonal elements of D1ATAD1 are equal to one. It is shown in this paper that the condition number of AD1 can be at least ( n/2) 1/2 times the minimal one. Some questions for a further research are posed. 相似文献
18.
In this paper, we shall prove a conjecture of Mills: for two ( k+1)-connected matroids whose symmetric difference between their collections of bases has size at most k, there is a matroid that is obtained from one of these matroids by relaxing n1 circuit-hyperplanes and from the other by relaxing n2 circuit-hyperplanes, where n1 and n2 are non-negative integers such that n1+ n2k 相似文献
19.
N people select a loser by flipping coins. Recursively, the 0-party continues until the loser is found. Among other things, it is shown that this process stops on the average after about log 2 N steps. Nevertheless, this very plausible result requires rather advanced methods. 相似文献
20.
Let sk( n) be the largest integer such that every n-point interval order with no antichain of more than k points includes an sk( n)-point semiorder. When k = 1, s1( n) = n since all interval orders with no two-point antichains are chains. Given ( c1,..., c5) = (1, 2, 3, 4), it is shown that s2( n) = cn for n 4, s3( n) = cn for n 5, and for all positive n, s2 ( n+4) = s2( n)+3, s3( n+5) = s3( n)+3. Hence s2 has a repeating pattern of length 4 [1, 2, 3, 3; 4, 5, 6, 6; 7, 8, 9, 9;...], and s3 has a repeating pattern of length 5 [1, 2, 3, 3, 4; 4, 5, 6, 6, 7; 7, 8, 9, 9, 10;...]. Let s(n) be the largest integer such that every n-point interval order includes an s(n)-point semiorder. It was proved previously that
for even n from 4 to 14, and that s(17) = 9. We prove here that s(15) = s(16) = 9, so that s begins 1, 2, 3, 3, 4, 4,..., 8, 8, 9, 9, 9. Since s(n)/n→0, s cannot have a repeating pattern. 相似文献
|