排序方式: 共有79条查询结果,搜索用时 15 毫秒
1.
Extendable Cycles in Multipartite Tournaments 总被引:1,自引:0,他引:1
An n-partite tournament is an orientation of a complete n-partite graph. If D is a strongly connected n-partite (n3) tournament, then we shall prove that every partite set of D has at least one vertex which lies on a cycle Cm of each length m for such that V(C3)V(C4)V(Cn), where V(Cm) is the vertex set of Cm for . This result extends those of Bondy [2], Guo and Volkmann [4], Gutin [6], Moon [8], and Yeo [12].Final version received: June 9, 2003 相似文献
2.
We find a formula for the number of directed 5‐cycles in a tournament in terms of its edge scores and use the formula to find upper and lower bounds on the number of 5‐cycles in any n‐tournament. In particular, we show that the maximum number of 5‐cycles is asymptotically equal to , the expected number 5‐cycles in a random tournament (), with equality (up to order of magnitude) for almost all tournaments. 相似文献
3.
《Journal of Graph Theory》2018,88(1):192-210
A tournament is called locally transitive if the outneighborhood and the inneighborhood of every vertex are transitive. Equivalently, a tournament is locally transitive if it avoids the tournaments W4 and L4, which are the only tournaments up to isomorphism on four vertices containing a unique 3‐cycle. On the other hand, a sequence of tournaments with is called almost balanced if all but vertices of have outdegree . In the same spirit of quasi‐random properties, we present several characterizations of tournament sequences that are both almost balanced and asymptotically locally transitive in the sense that the density of W4 and L4 in goes to zero as n goes to infinity. 相似文献
4.
《Discrete Mathematics》2020,343(12):112127
Let be a positive integer. The Bermond–Thomassen conjecture states that, a digraph of minimum out-degree at least contains vertex-disjoint directed cycles. A digraph is called a local tournament if for every vertex of , both the out-neighbours and the in-neighbours of induce tournaments. Note that tournaments form the subclass of local tournaments. In this paper, we verify that the Bermond–Thomassen conjecture holds for local tournaments. In particular, we prove that every local tournament with contains disjoint cycles , satisfying that either has the length at most 4 or is a shortest cycle of the original digraph of for . 相似文献
5.
Gennian Ge 《Journal of Combinatorial Theory, Series A》2007,114(4):747-760
Frames are useful in dealing with resolvable designs such as resolvable balanced incomplete block designs and triplewhist tournaments. Z-cyclic triplewhist tournament frames are also useful in the constructions of Z-cyclic triplewhist tournaments. In this paper, the concept of an (h1,h2,…,hn;u)-regular Z-cyclic triplewhist tournament frame is defined, and used to establish several quite general recursive constructions for Z-cyclic triplewhist tournaments. As corollaries, we are able to unify many known constructions for Z-cyclic triplewhist tournaments. As an application, some new Z-cyclic triplewhist tournament frames and Z-cyclic triplewhist tournaments are obtained. The known existence results of such designs are then extended. 相似文献
6.
Youssef Boudabbous 《Mathematical Logic Quarterly》1999,45(3):421-431
Let T and T1 be tournaments with n elements, E a basis for T, E′ a basis for T′, and k ≥ 3 an integer. The dual of T is the tournament T” of basis E defined by T(x, y) = T(y, x) for all x, y ε E. A hemimorphism from T onto T′ is an isomorphism from T onto T” or onto T. A k-hemimorphism from T onto T′ is a bijection f from E to E′ such that for any subset X of E of order k the restrictions T/X and T1/f(X) are hemimorphic. The set of hemimorphisms of T onto itself has group structure, this group is called the group of hemimorphisms of T. In this work, we study the restrictions to n – 2 elements of a tournament with n elements. In particular, we prove: Let k ≥ 3 be an integer, T a tournament with n elements, where n ≥ k + 5. Then the following statements are equivalent: (i) All restrictions of T to subsets with n – 2 elements are k-hemimorphic. (ii) All restrictions of T to subsets with n – 2 elements are 3-hemimorphic. (iii) All restrictions of T to subsets with n – 2 elements are hemimorphic. (iv) All restrictions of T to subsets with n – 2 elements are isomorphic, (v) Either T is a strict total order, or the group of hemimorphisms of T is 2-homogeneous. 相似文献
7.
The problem of complementary cycles in tournaments and bipartite tournaments was completely solved. However, the problem of complementary cycles in semicomplete n-partite digraphs with n ≥ 3 is still open. Based on the definition of componentwise complementary cycles, we get the following result. Let D be a 2-strong n-partite (n ≥ 6) tournament that is not a tournament. Let C be a 3-cycle of D and D \ V (C) be nonstrong. For the unique acyclic sequence D1, D2, ··· , Dα of D \V (C), where α≥ 2, let Dc = {Di|Di contains cycles, i = 1, 2, ··· , α}, Dc = {D1, D2, ··· , Dα} \ Dc. If Dc ≠ , then D contains a pair of componentwise complementary cycles. 相似文献
8.
Andrei Horbach 《Operations Research Letters》2010,38(2):121-122
We prove a new combinatorial property of the maximum round robin tournament (MRRT) problem. This property allows us to answer negatively the question of Briskorn, whether the optimal objective value of the MRRT problem and that of its conventional linear relaxation always coincide. 相似文献
9.
We prove that every tournament T with no three disjoint cycles contains a set X of at most four vertices such that is acyclic. 相似文献
10.
Let TTn be a transitive tournament on n vertices. We show that for any directed acyclic graph G of order n and of size not greater than two directed graphs isomorphic to G are arc disjoint subgraphs of TTn. Moreover, this bound is generally the best possible.
The research partially supported by KBN grant 2 P03A 016 18 相似文献