Universal arcs in local tournaments

An arc $uv$ of a digraph $D$ is called universal if $uv$ and $w$ are in a common cycle for any vertex $w$ of $D$. In this paper we characterize local tournaments whose every arc is universal.     

Weakening arcs in tournaments

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     

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     

The number of pancyclic arcs in a k‐strong tournament

A tournament is a digraph, where there is precisely one arc between every pair of distinct vertices. An arc is pancyclic in a digraph D, if it belongs to a cycle of length l, for all 3 ≤ l ≤ |V (D) |. Let p(D) denote the number of pancyclic arcs in a digraph D and let h(D) denote the maximum number of pancyclic arcs belonging to the same Hamilton cycle of D. Note that p(D) ≥ h(D). Moon showed that h(T) ≥ 3 for all strong non‐trivial tournaments, T, and Havet showed that h(T) ≥ 5 for all 2‐strong tournaments T. We will show that if T is a k‐strong tournament, with k ≥ 2, then p(T) ≥ 1/2, nk and h(T) ≥ (k + 5)/2. This solves a conjecture by Havet, stating that there exists a constant α_k, such that p(T) ≥ α_k n, for all k‐strong tournaments, T, with k ≥ 2. Furthermore, the second results gives support for the conjecture h(T) ≥ 2k + 1, which was also stated by Havet. The previously best‐known bounds when k ≥ 2 were p(T) ≥ 2k + 3 and h(T) ≥ 5. © 2005 Wiley Periodicals, Inc. J Graph Theory     

邻域并与泛圈图

本文中 ,我们用邻域并对泛圈图进行深入的研究 ,主要取得了“2连通 n( n≥ 3 )阶图 G,满足下列条件之一 ,则 G是泛圈图 : :δ≤ ( n-7) /3 ,N C≥ ( 2 n-3 ) /3 ; :( n-6) /3≤ δ≤ ( n+2 ) /3 ,N C≥ 2 n/3 ; :δ≥ ( n+3 ) /3 ,N C≥ ( 2 n-3 ) /3 .当 3≤ n≤ 14时 ,N C≥ 2 n/3”     

关于几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m＜n)使对每个l∈{3,4,…,n} -{m},G恰有一个长为l的圈且不含长为m的圈,则称G是几乎唯一泛圈图,用(?)k表示具有n k条边和恰有1/2(k 1)(k 2)个圈的简单H图的集合,用(?)_k~*表示具有n k条边恰有2~k k个圈的简单外可平面H图的集合,本文确定了(?)_k和(?)_k~*中所有几乎唯一泛圈图,并证明这些图都是简单MCD图,本文还构造了50个含有同胚于K_4的子图的几乎唯一泛圈图,并提出了若干问题和猜想。     

Star-factors of tournaments

Let S_m denote the m-vertex simple digraph formed by m − 1 edges with a common tail. Let f(m) denote the minimum n such that every n-vertex tournament has a spanning subgraph consisting of n/m disjoint copies of S_m. We prove that m lg m − m lg lg m ≤ f(m) ≤ 4m² − 6m for sufficiently large m. © 1998 John Wiley & Sons, Inc. J. Graph Theory 28: 141–145, 1998     

泛圈图方面的著名Bondy定理的简单证明

本文用极好的新方法给出泛图图方面的Bondy定理的简捷证明。     

On cycles in regular 3-partite tournaments

A $c$-partite tournament is an orientation of a complete $c$-partite graph. In 2006, Volkmann conjectured that every arc of a regular 3-partite tournament $D$ is contained in an $m$-, $(m+1)$- or $(m+2)$-cycle for each $m\in \{3,4,\dots ,\left|V\left(D\right)\right|?2\}$, and this conjecture was proved to be correct for $3\le m\le 7$. In 2012, Xu et al. conjectured that every arc of an $r$-regular 3-partite tournament $D$ with $r\ge 2$ is contained in a $(3k?1)$- or $3k$-cycle for $k=2,3,\dots ,r$. They proved that this conjecture is true for $k=2$. In this paper, we confirm this conjecture for $k=3$, which also implies that Volkmann’s conjecture is correct for $m=7,8$.     

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…     

Monochromatic sinks in nearly transitive arc-colored tournaments

Let T be the set of all arc-colored tournaments, with any number of colors, that contain no rainbow 3-cycles, i.e., no 3-cycles whose three arcs are colored with three distinct colors. We prove that if T∈T and if each strong component of T is a single vertex or isomorphic to an upset tournament, then T contains a monochromatic sink. We also prove that if T∈T and T contains a vertex x such that T−x is transitive, then T contains a monochromatic sink. The latter result is best possible in the sense that, for each n≥5, there exists an n-tournament T such that (T−x)−y is transitive for some two distinct vertices x and y in T, and T can be arc-colored with five colors such that T∈T, but T contains no monochromatic sink.     

Median orders of tournaments: A tool for the second neighborhood problem and Sumner's conjecture

We give a short constructive proof of a theorem of Fisher: every tournament contains a vertex whose second outneighborhood is as large as its first outneighborhood. Moreover, we exhibit two such vertices provided that the tournament has no dominated vertex. The proof makes use of median orders. A second application of median orders is that every tournament of order 2n − 2 contains every arborescence of order n > 1. This is a particular case of Sumner's conjecture: every tournament of order 2n − 2 contains every oriented tree of order n > 1. Using our method, we prove that every tournament of order (7n − 5)/2 contains every oriented tree of order n. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 244–256, 2000     

一类几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m相似文献   

Solution of a conjecture of Volkmann on longest paths through an arc in strongly connected in‐tournaments

An in‐tournament is an oriented graph such that the negative neighborhood of every vertex induces a tournament. Let m = 4 or m = 5 and let D be a strongly connected in‐tournament of order such that each arc belongs to a directed path of order at least m. In 2000, Volkmann showed that if D contains an arc e such that the longest directed path through e consists of exactly m vertices, then e is the only arc of D with that property. In this article we shall see that this proposition is true for , thereby validating a conjecture of Volkmann. Furthermore, we prove that if we ease the restrictions on the order of D to , the in‐tournament D in question has at most two such arcs. In doing so, we also give a characterization of the in‐tournaments with exactly two such arcs. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 130–148, 2009     

Hamilton非二部图的弱泛圈性

图G称为弱泛圈图是指G包含了每个长为t(g(V)≤l≤c(G))的圈,其中g(G),c(v)分别是G的围长与周长.1997年Brandt提出以下猜想:边数大于[n2/4]-n 5的n阶非二部图为弱泛圈图.1999年Bollobas和Thomason证明了边数不小于[n2/4]-n 59的n阶非二部图为弱泛圈图.作者证明了如下结论:设G是n阶Hamilton非二部图,若G的边数不小于[n2/4]-n 12,则G为弱泛圈图.     

具有最小弧数的唯一泛圈有向图的计数

唯一泛圈有向图D是一个定向图,对每一个n,3≤n≤υ,D中有且只有一个长为n的有向圈.用g(υ)表示具有υ个顶点的唯一泛圈有向图最小可能的弧数,用N(υ)表示具有υ个顶点、g(υ)条弧且互不同构的唯一泛圈有向图的个数.确定了当υ=3,4,5,6,7,8时的N(υ).     

Ordered tournaments and ordered triplewhist tournaments with the three person property

It is well known that an ordered tournament OWh(v) exists if and only if v ≡ 1 (mod 4), v ≥ 5. An ordered triplewhist tournament on v players is said to have the three person property if no two games in the tournament have three common players. We briefly denote such a design as a 3POTWh(v). In this article, we show that a 3POTWh(v) exists whenever v>17 and v ≡ 1 (mod 4) with few possible exceptions. We also show that an ordered whist tournament on v players with the three person property, denoted 3POWh(v), exists if and only if v ≡ 1 (mod 4), v ≥ 9. © 2008 Wiley Periodicals, Inc. J Combin Designs 17: 39–52, 2009     

Hamiltonian dicycles avoiding prescribed arcs in tournaments

If I is a set ofk – 1 arcs in ak-connected tournamentT, thenT – I has a Hamiltonian dicycle.     

Circulant tournaments of prime order are tight

We say that a tournament is tight if for every proper 3-coloring of its vertex set there is a directed cyclic triangle whose vertices have different colors. In this paper, we prove that all circulant tournaments with a prime number p≥3 of vertices are tight using results relating to the acyclic disconnection of a digraph and theorems of additive number theory.     

Hamiltonicity and reversing arcs in digraphs

In this paper we introduce a new hamiltonian-like property of graphs. A graph G is said to be cyclable if for each orientation D of G there is a set S of vertices such that reversing all the arcs of D with one end in S results in a hamiltonian digraph. We characterize cyclable complete multipartite graphs and prove that the fourth power of any connected graph G with at least five vertices is cyclable. If, moreover, G is two-connected then its cube is cyclable. These results are shown to be best possible in a sense. © 1998 John Wiley & Sons, Inc. J Graph Theory 28: 13–30, 1998