Paths with a given number of vertices from each partite set in regular multipartite tournaments

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.     

On cycles in regular 3-partite tournaments

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)|.     

Outpaths of arcs in multipartite tournaments

1. IntroductionThroughout the paPer, we use the terminology and notation of [1] and [2]. Let D =(V(D), A(D)) be a digraPh. If xy is an arc of a digraPh D, then we say that x dominatesy, denoted by x - y. More generally, if A and B are two disjoint vertex sets of D such thatevery vertex of A dominates every vertex of B, then we say that A dominates B, denotedby A - B. The outset N (x) of a vertex x is the set of vertices dominated by x in D,and the inset N--(x) is the set of vertices d…     

Complementary cycles in regular multipartite tournaments, where one cycle has length five

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.     

Kings in semicomplete multipartite digraphs

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     

Longest cycles in almost regular 3-partite tournaments

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

     

Strong subtournaments containing a given vertex in regular multipartite tournaments

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

     

On Cycles Containing a Given Arc in Regular Multipartite Tournaments

In this paper we prove that if T is a regular n-partite tournament with n≥4, then each arc of T lies on a cycle whose vertices are from exactly κ partite sets for κ=4,5,…,n. Our result, in a sense, generalizes a theorem due to Alspach.     

How Close to Regular Must a Semicomplete Multipartite Digraph Be to Secure Hamiltonicity?

 Let D be a semicomplete multipartite digraph, with partite sets V ₁, V ₂,…, V _c, such that |V ₁|≤|V ₂|≤…≤|V _c|. Define f(D)=|V(D)|−3|V _c|+1 and . We define the irregularity i(D) of D to be max|d ⁺(x)−d ⁻(y)| over all vertices x and y of D (possibly x=y). We define the local irregularity i _l(D) of D to be max|d ⁺(x)−d ⁻(x)| over all vertices x of D and we define the global irregularity of D to be i _g(D)=max{d ⁺(x),d ⁻(x) : x∈V(D)}−min{d ⁺(y),d ⁻(y) : y∈V(D)}. In this paper we show that if i _g(D)≤g(D) or if i _l(D)≤min{f(D), g(D)} then D is Hamiltonian. We furthermore show how this implies a theorem which generalizes two results by Volkmann and solves a stated problem and a conjecture from [6]. Our result also gives support to the conjecture from [6] that all diregular c-partite tournaments (c≥4) are pancyclic, and it is used in [9], which proves this conjecture for all c≥5. Finally we show that our result in some sense is best possible, by giving an infinite class of non-Hamiltonian semicomplete multipartite digraphs, D, with i _g(D)=i(D)=i _l(D)=g(D)+?≤f(D)+1. Revised: September 17, 1998     

Hamilton cycles,avoiding prescribed arcs,in close-to-regular tournaments

The local irregularity of a digraph D is defined as i_l(D) = max {|d⁺ (x) − d⁻ (x)| : x ϵ V(D)}. Let T be a tournament, let Γ = {V₁, V₂, …, V_c} be a partition of V(T) such that |V₁| ≥ |V₂| ≥ … ≥ |V_c|, 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{2i_l(T) + 2|V₁| + 2|V₂| − 2, i_l(T) + 3|V₁| − 1}, then D is Hamiltonian. Furthermore, if T is regular (i.e., i_l(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     

c-Pancyclic Partial Ordering and （c-1）-Pan-Outpath Partial Ordering in Semicomplete Multipartite Digraphs

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.     

S-polar sets of super-brownian motions and solutions of nonlinear differential equations

This paper gives probabilistic expressions of the minimal and maximal positive solutions of the partial differential equation -1/2△v(x) γ(x)v(x)α = 0 in D, where D is a regular domain in Rd(d ≥ 3) such that its complement Dc is compact, γ(x) is a positive bounded integrable function in D, and 1 < α≤ 2. As an application, some necessary and sufficient conditions for a compact set to be S-polar are presented.     

Characterising the Accuracy of Multivariable Refinable Functions via the Symbol Function

Suppose that f(x) = (f ₁(x),...,f _r (x)) ^T , x∈R ^d is a vector-valued function satisfying the refinement equation f(x) = ∑_Λ c _κ f(2x−κ) with finite set Λ of Z ^d and some r×r matricex c _κ. The requirements for f to have accuracy p are given in terms of the symbol function m(ξ). Supported by NSFC     

Componentwise complementary cycles in multipartite tournaments

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.     

Three supplements to Reid’s theorem in multipartite tournaments

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.     

On semicomplete multipartite digraphs whose king sets are semicomplete digraphs

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 K_r(T) denote the set of r-kings of T. Let Q be the subdigraph of T induced by K₄(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 K₄(Q)⊆K₄(T), Tan [On the kings and kings-of-kings in semicomplete multipartite digraphs, Discrete Math. 290 (2005) 249-258] showed that K₃(Q)⊆K₃(T) and K₂(Q)=K₂(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 K₃(Q) need not be the same as K₃(T) in general and posed the problem: characterize all those semicomplete multipartite digraphs T such that K₃(Q)=K₃(T). In the course of proving our result (1), we (2) show that K₃(Q)=K₃(T) for all semicomplete multipartite digraphs T with no transmitters such that Q is a semicomplete digraph.     

Diameter and diametrical pairs of points in ultrametric spaces

Let F(X) be the set of finite nonempty subsets of a set X. We have found the necessary and sufficient conditions under which for a given function τ: F(X) → ℝ there is an ultrametric on X such that τ(A) = diamA for every A ∈ F(X). For finite nondegenerate ultrametric spaces (X, d) it is shown that X together with the subset of diametrical pairs of points of X forms a complete k-partite graph, k ⩾ 2, and, conversely, every finite complete k-partite graph with k ⩾ 2 can be obtained by this way. We use this result to characterize the finite ultrametric spaces (X, d) having the minimal card{(x, y): d(x, y) = diamX, x, y ∈ X} for given card X.     

Weakly Cycle Complementary 3-Partite Tournaments

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. Let V ₁, V ₂, . . . ,V _c be the partite sets of D. If there exist two vertex disjoint cycles C and C′ in D such that V_i?(V(C)èV(C￠)) 1 ?{V_{\mathrm{i}}\cap(V(C)\cup V(C'))\neq\emptyset} for all i = 1, 2, . . . , c, then D is weakly cycle complementary. In 2008, Volkmann and Winzen gave the above definition of weakly complementary cycles and proved that all 3-connected c-partite tournaments with c ≥ 3 are weakly cycle complementary. In this paper, we characterize multipartite tournaments are weakly cycle complementary. Especially, we show that all 2-connected 3-partite tournaments that are weakly cycle complementary, unless D is isomorphic to D _3,2, D _3,2,2 or D _3,3,1.     

Asymptotic behaviour of a Brownian motion on exterior domains

We study the asymptotic behaviour of the transition density of a Brownian motion in ?, killed at ∂?, where ? ^c is a compact non polar set. Our main result concern dimension d = 2, where we show that the transition density p ^? _t (x, y) behaves, for large t, as u(x)u(y)(t(log t)²)⁻¹ for x, y∈?, where u is the unique positive harmonic function vanishing on (∂?) ^r , such that u(x) ∼ log ∣x∣. Received: 29 January 1999 / Revised version: 11 May 1999     

On n-partite Tournaments with Unique n-cycle

An n-partite tournament is an orientation of a complete n-partite graph. An n-partite tournament is a tournament, if it contains exactly one vertex in each partite set. Douglas, Proc. London Math. Soc. 21 (1970) 716–730, obtained a characterization of strongly connected tournaments with exactly one Hamilton cycle (i.e., n-cycle). For n≥3, we characterize strongly connected n-partite tournaments that are not tournaments with exactly one n-cycle. For n≥5, we enumerate such non-isomorphic n-partite tournaments.