首页 | 本学科首页   官方微博 | 高级检索  
相似文献
 共查询到20条相似文献,搜索用时 15 毫秒
1.
Letf(s, t; k) be the largest value ofm such that it is possible tok-color the edges of the complete graphK m so that everyK s K m has exactlyt colors occuring on its edges. The main object of this paper is to describe the behavior of the functionf(s,t;k), usually thinking ofs andt fixed, and lettingk become large. Dedicated to Paul Erdős on his seventieth birthday  相似文献   

2.
Adecomposition of a graphG=(V,E) is a partition of the vertex set into subsets (calledblocks). Thediameter of a decomposition is the leastd such that any two vertices belonging to the same connected component of a block are at distance d. In this paper we prove (nearly best possible) statements, of the form: Anyn-vertex graph has a decomposition into a small number of blocks each having small diameter. Such decompositions provide a tool for efficiently decentralizing distributed computations. In [4] it was shown that every graph has a decomposition into at mosts(n) blocks of diameter at mosts(n) for . Using a technique of Awerbuch [3] and Awerbuch and Peleg [5], we improve this result by showing that every graph has a decomposition of diameterO (logn) intoO(logn) blocks. In addition, we give a randomized distributed algorithm that produces such a decomposition and runs in timeO(log2 n). The construction can be parameterized to provide decompositions that trade-off between the number of blocks and the diameter. We show that this trade-off is nearly best possible, for two families of graphs: the first consists of skeletons of certain triangulations of a simplex and the second consists of grid graphs with added diagonals. The proofs in both cases rely on basic results in combinatorial topology, Sperner's lemma for the first class and Tucker's lemma for the second.A preliminary version of this paper appeared as Decomposing Graphs into Regions of Small Diameter in Proc. 2nd ACM-SIAM Symposium on Discrete Algorithms (1991) 321-330.This work was supported in part by NSF grant DMS87-03541 and by a grant from the Israel Academy of Science.This work was supported in part by NSF grant DMS87-03541 and CCR89-11388.  相似文献   

3.
An orthogonal double cover (ODC) of the complete graph Kn by a graph G is a collection G of n spanning subgraphs of Kn, all isomorphic to G, such that any two members of G share exactly one edge and every edge of Kn is contained in exactly two members of G. In the 1980s Hering posed the problem to decide the existence of an ODC for the case that G is an almost-Hamiltonian cycle, i.e. a cycle of length n-1. It is known that the existence of an ODC of Kn by a Hamiltonian path implies the existence of ODCs of K4n and of K16n, respectively, by almost-Hamiltonian cycles. Horton and Nonay introduced two-colorable ODCs and showed: If there are an ODC of Kn by a Hamiltonian path for some n?3 and a two-colorable ODC of Kq by a Hamiltonian path for some prime power q?5, then there is an ODC of Kqn by a Hamiltonian path. In [U. Leck, A class of 2-colorable orthogonal double covers of complete graphs by hamiltonian paths, Graphs Combin. 18 (2002) 155-167], two-colorable ODCs of Kn and K2n, respectively, by Hamiltonian paths were constructed for all odd square numbers n?9. Here we continue this work and construct cyclic two-colorable ODCs of Kn and K2n, respectively, by Hamiltonian paths for all n of the form n=4k2+1 or n=(k2+1)/2 for some integer k.  相似文献   

4.
We (1) determine the number of Latin rectangles with 11 columns and each possible number of rows, including the Latin squares of order 11, (2) answer some questions of Alter by showing that the number of reduced Latin squares of order n is divisible by f! where f is a particular integer close to (3) provide a formula for the number of Latin squares in terms of permanents of (+1, −1)-matrices, (4) find the extremal values for the number of 1-factorisations of k-regular bipartite graphs on 2n vertices whenever 1 ≤ kn ≤ 11, (5) show that the proportion of Latin squares with a non-trivial symmetry group tends quickly to zero as the order increases. Received September 3, 2004  相似文献   

5.
Summary A resolvableX-decomposition ofDK v (the complete symmetric digraph onv vertices) is a partition of the arcs ofDK v into isomorphic factors where each factor is a vertex-disjoint union of copies ofX and spans all vertices ofDK v . There are four orientations ofC 4 (the 4-cycle), only one of which has been considered: Bennett and Zhang, Aequationes Math.40 (1990), 248–260. We give necessary and sufficient conditions onv for resolvableX-decomposition ofDK v , whereX is any one of the other three orientations ofC 4. A near-resolvableX-decomposition ofDK v is as above except that each factor spans all but one vertex ofDK v . Again, one orientation ofC 4 has been dealt with by Bennett and Zhang, and we provide necessary and sufficient conditions onv for the remaining three cases. The construction techniques used are both direct (for small values ofv) and recursive.The author thanks Simon Fraser University for its support during her graduate studies when the research for this paper was undertaken.The author acknowledges the Natural Sciences and Engineering Research Council of Canada for financial support under grant A-7829.  相似文献   

6.
Denote by σ the subspace of Hilbert space {(xi)?l2:xi=0 for all but finitely many i}. Examples of cell-like decompositions of σ are constructed that have decomposition spaces that are not homeomorphic to σ. At one extreme is a cell-like decomposition G of σ produced using ghastly finite dimensional examples such that the decomposition space σ?G contains no embedded 2-cell but (σ?GR is homeomorphic to σ. At the other extreme is a cell-like decomposition G of σ satisfying: (a) the nondegeneracy set NG={g?G:g≠point} consists of countably many arcs (necessarily tame); (b) the nondegeneracy set NG is a closed subset of the decomposition space σ?G; (c) each map f:B2σ?G of a 2-cell into σ?G can be approximated arbitrarily closely by an embedding; (d) σ?G is not homeomorphic to σ but (σ?GR is homeomorphic to σ. The fact that both conditions (a) and (b) can be satisfied (and have (d) hold) is directly attributable to σ’s incompleteness as a topological space.  相似文献   

7.
The study of configurations or — more generally — finite incidence geometries is best accomplished by taking into account also their automorphism groups. These groups act on the geometry and in particular on points, blocks, flags and even anti-flags. The orbits of these groups lead to tactical decompositions of the incidence matrices of the geometries or of related geometries. We describe the general procedure and use these decompositions to study symmetric configurationsv 4 for smallv. Tactical decompositions have also been used to construct all linear spaces on 12 points [2] and all proper linear spaces on 17 points [3].  相似文献   

8.
Call a directed graph symmetric if it is obtained from an undirected graph G by replacing each edge of G by two directed edges, one in each direction. We will show that if G has a Hamilton decomposition with certain additional structure, then has a directed Hamilton decomposition. In particular, it will follow that the bidirected cubes for m?2 are decomposable into 2m+1 directed Hamilton cycles and that a product of cycles is decomposable into 2m+1 directed Hamilton cycles if ni?3 and m?2.  相似文献   

9.
It is proved in this paper that every bipartite graphic sequence with the minimum degree 2 has a realization that admits a nowhere-zero 4-flow. This result implies a conjecture originally proposed by Keedwell (1993) and reproposed by Cameron (1999) about simultaneous edge-colorings and critical partial Latin squares.* Partially supported by RGC grant HKU7054/03P. Partially supported by the National Security Agency under Grants MDA904-00-1-00614 and MDA904-01-1-0022.  相似文献   

10.
We derive easily verifiable conditions which characterize when complex Seidel matrices containing cube roots of unity have exactly two eigenvalues. The existence of such matrices is equivalent to the existence of equiangular tight frames for which the inner product between any two frame vectors is always a common multiple of the cube roots of unity. We also exhibit a relationship between these equiangular tight frames, complex Seidel matrices, and highly regular, directed graphs. We construct examples of such frames with arbitrarily many vectors.  相似文献   

11.
Just as matroids abstract the algebraic properties of determinants in a vector space, Pfaffian structures abstract the algebraic properties of Pfaffians or skew-symmetric determinants in a symplectic space (that is, a vector space with an alternating bilinear form). This is done using an exchange-augmentation axiom which is a combinatorial version of a Laplace expansion or straightening identity for Pfaffians. Using Pfaffian structures, we study a symplectic analogue of the classical critical problem: given a setS of non-zero vectors in a non-singular symplectic spaceV of dimension2m, find its symplectic critical exponent, that is, the minimum of the set {m?dim(U):U∩S=0}, whereU ranges over all the (totally) isotropic subspaces disjoint fromS. In particular, we derive a formula for the number of isotropic subspaces of a given dimension disjoint from the setS by Möbius inversion over the order ideal of isotropic flats in the lattice of flats of the matroid onS given by linear dependence. This formula implies that the symplectic critical exponent ofS depends only on its matroid and Pfaffian structure; however, it may depend on the dimension of the symplectic spaceV.  相似文献   

12.
The existence of a Room square of order 2n is known to be equivalent to the existence of two orthogonal one-factorizations of the complete graph on 2n vertices, where orthogonal means any two one-factors involved have at most one edge in common. DefineR(n) to be the maximal number of pairwise orthogonal one-factorizations of the complete graph onn vertices.The main results of this paper are bounds on the functionR. If there is a strong starter of order 2n–1 thenR(2n) 3. If 4n–1 is a prime power, it is shown thatR(4n) 2n–1. Also, the recursive construction for Room squares, to obtain, a Room design of sidev(u – w) +w from a Room design of sidev and a Room design of sideu with a subdesign of sidew, is generalized to sets ofk pairwise orthogonal factorizations. It is further shown thatR(2n) 2n–3.  相似文献   

13.
《Quaestiones Mathematicae》2013,36(4):537-548
Abstract

For a set F of graphs and a natural number k, an (F, k)-colouring of a graph G is a proper colouring of V (G) such that no subgraph of G isomorphic to an element of F is coloured with at most k colours. Equivalently, if P is the class of all graphs that do not contain an element of F as a subgraph, a χP,k colouring of G is a proper colouring such that the union of at most k colour classes induces a graph in P. The smallest number of colours in such a colouring of G, if it exists, is denoted by χP,k (G). We give some general results on χP,k-colourings and investigate values of χP,k (G) for some choices of P and classes of graphs G.  相似文献   

14.
We derive lower bounds on the maximal length s(n) of (n, s) Davenport Schinzel sequences. These bounds have the form 2s=1(n)=(ns(n)), where(n) is the extremely slowly growing functional inverse of the Ackermann function. These bounds extend the nonlinear lower bound 3 (n)=(n(n)) due to Hart and Sharir [5], and are obtained by an inductive construction based upon the construction given in [5].Work on this paper has been supported by Office of Naval Research Grant N00014-82-K-0381, National Science Foundation Grant No. NSF-DCR-83-20085, and by grants from the Digital Equipment Corporation, and the IBM Corporation.  相似文献   

15.
Davenport—Schinzel sequences are sequences that do not contain forbidden subsequences of alternating symbols. They arise in the computation of the envelope of a set of functions. We show that the maximal length of a Davenport—Schinzel sequence composed ofn symbols is Θ (nα(n)), where α(n) is the functional inverse of Ackermann’s function, and is thus very slowly increasing to infinity. This is achieved by establishing an equivalence between such sequences and generalized path compression schemes on rooted trees, and then by analyzing these schemes. Work on this paper by the second author has been supported in part by a grant from the U.S.-Israeli Binational Science Foundation.  相似文献   

16.
A nucleotide sequence can be considered as a realization of the non-equal-probability independently and identically distributed (niid) model. In this paper we derive the exact distribution of the occurrence number for each K-tuple with respect to the niid model by means of the Goulden-Jackson cluster method. An application of the probability function to get exact expectation curves [9] is presented, accompanied by comparison between the exact approach and the approximate solution.Received October 31, 2004  相似文献   

17.
Azéma associated with an honest time L the supermartingale and established some of its important properties. This supermartingale plays a central role in the general theory of stochastic processes and in particular in the theory of progressive enlargements of filtrations. In this paper, we shall give an additive characterization for these supermartingales, which in turn will naturally provide many examples of enlargements of filtrations. We combine this characterization with some arguments from both initial and progressive enlargements of filtrations to establish some path decomposition results, closely related to or reminiscent of Williams' path decomposition results. In particular, some of the fragments of the paths in our decompositions end or start with a new family of random times which are not stopping times, nor honest times.  相似文献   

18.
19.
In this paper, a new concept of an optimal complete multipartite decomposition of type 1 (type 2) of a complete n-partite graph Q n is proposed and another new concept of a normal complete multipartite decomposition of K n is introduced. It is showed that an optimal complete multipartite decomposition of type 1 of K n is a normal complete multipartite decomposition. As for any complete multipartite decomposition of K n , there is a derived complete multipartite decomposition for Q n . It is also showed that any optimal complete multipartite decomposition of type 1 of Q n is a derived decomposition of an optimal complete multipartite decomposition of type 1 of K n . Besides, some structural properties of an optimal complete multipartite decomposition of type 1 of K n are given. Supported by the National Natural Science Foundation of China (10271110).  相似文献   

20.
Let σ1,σ2 be two permutations in the symmetric group Sn. Among the many sequences of elementary transpositions τ1,…,τr transforming σ1 into σ2=τrτ1σ1, some of them may be signable, a property introduced in this paper. We show that the four color theorem in graph theory is equivalent to the statement that, for any n≥2 and any σ1,σ2Sn, there exists at least one signable sequence of elementary transpositions from σ1 to σ2. This algebraic reformulation rests on a former geometric one in terms of signed diagonal flips, together with a codification of the triangulations of a convex polygon on n+2 vertices by permutations in Sn.  相似文献   

设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号