共查询到20条相似文献,搜索用时 15 毫秒
1.
多部竞赛图D中弧x_1x_2的一条(l-1)一外路是指起始于x_1x_2的长为l-1的路x_1x_2…x_1,其中要么x_1与x_1同部,要么x_1控制x_1.特别地,当l=|V(D)|且x_1控制x_1时,x_1x_2…x_lx_1是一个通过弧x_1x_2的Hamilton.Guo(Discrete Appl.Math.95(1999)273-277)证明了一个正则c-部(c≥3)竞赛图中的每条弧都有一个(k-1)-外路,其中k∈{3,4,…,c}.作为一个推广,该文证明了一个正则c-部(c≥5)竞赛图中的每条弧都有一个(k-1)-外路,其中k∈{3,4,…,|V(D)|}.进一步,使用路收缩技巧,下面一个结果也被证明:D是一个正则c-部(c≥8)竞赛图,且每个部集包含两个顶点,则D的每条弧被包含在一个Hamilton圈中.这个结果部分地支持了Volkmann和Yeo(Discrete Math.281(2004)267-276)提出的猜想:正则多部竞赛图的每条孤都包含在一个Hamilton圈中. 相似文献
2.
If x is a vertex of a digraph D, then we denote by d
+(x) and d
−(x) the outdegree and the indegree of x, respectively. A digraph D is called regular, if there is a number p ∈ ℕ such that d
+(x) = d
−(x) = p for all vertices x of D.
A c-partite tournament is an orientation of a complete c-partite graph. There are many results about directed cycles of a given length or of directed cycles with vertices from a
given number of partite sets. The idea is now to combine the two properties. In this article, we examine in particular, whether
c-partite tournaments with r vertices in each partite set contain a cycle with exactly r − 1 vertices of every partite set. In 1982, Beineke and Little [2] solved this problem for the regular case if c = 2. If c ⩾ 3, then we will show that a regular c-partite tournament with r ⩾ 2 vertices in each partite set contains a cycle with exactly r − 1 vertices from each partite set, with the exception of the case that c = 4 and r = 2. 相似文献
3.
If x is a vertex of a digraph D, then we denote by d+(x) and d−(x) the outdegree and the indegree of x, respectively. The global irregularity of a digraph D is defined by
4.
5.
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. 相似文献
6.
The vertex set of a digraph D is denoted by V(D). A c-partite tournament is an orientation of a complete c-partite graph.In 1999, Yeo conjectured that each regular c-partite tournament D with c≥4 and |V(D)|≥10 contains a pair of vertex disjoint directed cycles of lengths 5 and |V(D)|−5. In this paper we shall confirm this conjecture using a computer program for some cases. 相似文献
7.
8.
Lutz Volkmann 《Discrete Mathematics》2006,306(21):2724-2732
A tournament is an orientation of a complete graph, and in general a multipartite or c-partite tournament is an orientation of a complete c-partite graph.For c?2 we prove that a regular c-partite tournament with r?2 vertices in each partite set contains a directed path with exactly two vertices from each partite set. Furthermore, if c?4, then we will show that almost all regular c-partite tournaments D contain a directed path with exactly r-s vertices from each partite set for each given integer s∈N, if r is the cardinality of each partite set of D. Some related results are also presented. 相似文献
9.
Lutz Volkmann 《Discrete Mathematics》2006,306(12):1198-1206
The vertex set of a digraph D is denoted by V(D). A c-partite tournament is an orientation of a complete c-partite graph. In 1991, Jian-zhong Wang conjectured that every arc of a regular 3-partite tournament D is contained in directed cycles of all lengths 3,6,9,…,|V(D)|. This conjecture is not valid, because for each integer t with 3?t?|V(D)|, there exists an infinite family of regular 3-partite tournaments D such that at least one arc of D is not contained in a directed cycle of length t.In this paper, we prove that every arc of a regular 3-partite tournament with at least nine vertices is contained in a directed cycle of length m, m+1, or m+2 for 3?m?5, and we conjecture that every arc of a regular 3-partite tournament is contained in a directed cycle of length m, (m+1), or (m+2) for each m∈{3,4,…,|V(D)|-2}.It is known that every regular 3-partite tournament D with at least six vertices contains directed cycles of lengths 3, |V(D)|-3, and |V(D)|. We show that every regular 3-partite tournament D with at least six vertices also has a directed cycle of length 6, and we conjecture that each such 3-partite tournament contains cycles of all lengths 3,6,9,…,|V(D)|. 相似文献
10.
A weakening arc of an irreducible tournament is an arc whose reversal creates a reducible tournament. We consider properties of such arcs and derive recurrence relations for enumerating strong tournaments with no such arcs, one or more such arcs, and exactly one such arc. We also give some asymptotic results on the numbers of such tournaments, among other things. © 2003 Wiley Periodicals, Inc. J Graph Theory 45: 142–162, 2004 相似文献
11.
A digraph obtained by replacing each edge of a complete p‐partite graph by an arc or a pair of mutually opposite arcs with the same end vertices is called a semicomplete p‐partite digraph, or just a semicomplete multipartite digraph. A semicomplete multipartite digraph with no cycle of length two is a multipartite tournament. In a digraph D, an r‐king is a vertex q such that every vertex in D can be reached from q by a path of length at most r. Strengthening a theorem by K. M. Koh and B. P. Tan (Discr Math 147 (1995), 171–183) on the number of 4‐kings in multipartite tournaments, we characterize semicomplete multipartite digraphs, which have exactly k 4‐kings for every k = 1, 2, 3, 4, 5. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 177‐183, 2000 相似文献
12.
Lutz Volkmann 《Discrete Mathematics》2006,306(22):2931-2942
If D is a digraph, then we denote by V(D) its vertex set. A multipartite or c-partite tournament is an orientation of a complete c-partite graph. The global irregularity of a digraph D is defined by
13.
Dejan Brcanov 《Discrete Mathematics》2010,310(19):2550-2554
Let and be two n-tuples of nonnegative integers. An all-4-kings n-partite tournament T(V1,V2,…Vn) is said to have a -property if there exists an n-partite tournament T1(W1,W2,…,Wn) such that for each i∈{1,…,n}:
- (1)
- Vi⊆Wi;
- (2)
- exactly ti 4-kings of Vi are not 4-kings in T1;
- (3)
- exactly ci 4-kings of Wi are not vertices of Vi.
14.
An n-partite tournament is an orientation of a complete n-partite graph. In this paper, we give three supplements to Reid’s theorem [K.B. Reid, Two complementary circuits in two-connected tournaments, Ann. Discrete Math. 27 (1985) 321-334] in multipartite tournaments. The first one is concerned with the lengths of cycles and states as follows: let D be an (α(D)+1)-strong n-partite tournament with n≥6, where α(D) is the independence number of D, then D contains two disjoint cycles of lengths 3 and n−3, respectively, unless D is isomorphic to the 7-tournament containing no transitive 4-subtournament (denoted by ). The second one is obtained by considering the number of partite sets that cycles pass through: every (α(D)+1)-strong n-partite tournament D with n≥6 contains two disjoint cycles which contain vertices from exactly 3 and n−3 partite sets, respectively, unless it is isomorphic to . The last one is about two disjoint cycles passing through all partite sets. 相似文献
15.
B.P. Tan 《Discrete Mathematics》2006,306(21):2702-2710
Koh and Tan gave a sufficient condition for a 3-partite tournament to have at least one 3-king in [K.M. Koh, B.P. Tan, Kings in multipartite tournaments, Discrete Math. 147 (1995) 171-183, Theorem 2]. In Theorem 1 of this paper, we extend this result to n-partite tournaments, where n?3. In [K.M. Koh, B.P. Tan, Number of 4-kings in bipartite tournaments with no 3-kings, Discrete Math. 154 (1996) 281-287, K.M. Koh, B.P. Tan, The number of kings in a multipartite tournament, Discrete Math. 167/168 (1997) 411-418] Koh and Tan showed that in any n-partite tournament with no transmitters and 3-kings, where n?2, the number of 4-kings is at least eight, and completely characterized all n-partite tournaments having exactly eight 4-kings and no 3-kings. Using Theorem 1, we strengthen substantially the above result for n?3. Motivated by the strengthened result, we further show that in any n-partite tournament T with no transmitters and 3-kings, where n?3, if there are r partite sets of T which contain 4-kings, where 3?r?n, then the number of 4-kings in T is at least r+8. An example is given to justify that the lower bound is sharp. 相似文献
16.
17.
B.P. Tan 《Discrete Mathematics》2008,308(12):2564-2570
Reid [Every vertex a king, Discrete Math. 38 (1982) 93-98] showed that a non-trivial tournament H is contained in a tournament whose 2-kings are exactly the vertices of H if and only if H contains no transmitter. Let T be a semicomplete multipartite digraph with no transmitters and let Kr(T) denote the set of r-kings of T. Let Q be the subdigraph of T induced by K4(T). Very recently, Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] proved that Q contains no transmitters and gave an example to show that the direct extension of Reid's result to semicomplete multipartite digraphs with 2-kings replaced by 4-kings is not true. In this paper, we (1) characterize all semicomplete digraphs D which are contained in a semicomplete multipartite digraph whose 4-kings are exactly the vertices of D. While it is trivial that K4(Q)⊆K4(T), Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] showed that K3(Q)⊆K3(T) and K2(Q)=K2(T). Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] also provided an example to show that K3(Q) need not be the same as K3(T) in general and posed the problem: characterize all those semicomplete multipartite digraphs T such that K3(Q)=K3(T). In the course of proving our result (1), we (2) show that K3(Q)=K3(T) for all semicomplete multipartite digraphs T with no transmitters such that Q is a semicomplete digraph. 相似文献
18.
Anders Yeo 《Journal of Graph Theory》1999,32(2):123-136
The local irregularity of a digraph D is defined as il(D) = max {|d+ (x) − d− (x)| : x ϵ V(D)}. Let T be a tournament, let Γ = {V1, V2, …, Vc} be a partition of V(T) such that |V1| ≥ |V2| ≥ … ≥ |Vc|, and let D be the multipartite tournament obtained by deleting all the arcs with both end points in the same set in Γ. We prove that, if |V(T)| ≥ max{2il(T) + 2|V1| + 2|V2| − 2, il(T) + 3|V1| − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., il(T) = 0), then we state slightly better lower bounds for |V(T)| such that we still can guarantee that D is Hamiltonian. Finally, we show that our results are best possible. © 1999 John Wiley & Sons, Inc. J Graph Theory 32: 123–136, 1999 相似文献
19.
20.
LinQiangPAN KeMinZHANG 《数学学报(英文版)》2003,19(4):829-832
An outpath of a vertex v in a digraph is a path starting at v such that v dominates the end vertex of the path only if the end vertex also dominates v.First we show that letting D be a strongly connected semicomplete c-partite digraph (c≥3)1 and one of the partite sets of it consists of a single vertex, say v, then D has a c-pancyclic partial ordering from v, which generalizes a result about pancyclicity of multipartite tournaments obtained by Gutin in 1993.Then we prove that letting D be a strongly connected semicomplete c-partite digraph with c≥3 and letting v be a vertex of D,then Dhas a(c-1)-pan-outpath partly ordering from v.This result improves a theorem about outpaths in semicomplete multipartite digraphs obtained by Guo in 1999. 相似文献