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.     

Every cycle-connected multipartite tournament has a universal arc

A digraph D is cycle-connected if for every pair of vertices u,v∈V(D) there exists a directed cycle in D containing both u and v. In 1999, Ádám [A. Ádám, On some cyclic connectivity properties of directed graphs, Acta Cybernet. 14 (1) (1999) 1-12] posed the following problem. Let D be a cycle-connected digraph. Does there exist a universal arc in D, i.e., an arc e∈A(D) such that for every vertex w∈V(D) there is a directed cycle in D containing both e and w?A c-partite or multipartite tournament is an orientation of a complete c-partite graph. Recently, Hubenko [A. Hubenko, On a cyclic connectivity property of directed graphs, Discrete Math. 308 (2008) 1018-1024] proved that each cycle-connected bipartite tournament has a universal arc. As an extension of this result, we show in this note that each cycle-connected multipartite tournament has a universal arc.     

传递的二部竞赛图的性质

Abipartitetournamentistransitiveifitcontainsnocycles.Becausetransitivem ×nbi partitetournamentisn’tuniqueintheisomorphicsense,theproblemsoftransitivebipartitetournamentsarecomplicated .Hence ,BEINEKELWandMOONJW gaveacriterionforde terminingwhetherascoreorderedpaircontainssometransitivebipartitetournament(see [1 ]) .Theenumerationoftransitivebipartitetournamentswasdiscussedby [2 ].LetTm ,n =(V ,U ,E) beam ×nbipartitetournamentwith｜V｜=mand｜U｜=n .Denotebyd(w)thescoreofvertexw .Th…     

Cycles with a chord in dense graphs

A cycle of order $k$ is called a $k$-cycle. A non-induced cycle is called a chorded cycle. Let $n$ be an integer with $n\ge 4$. Then a graph $G$ of order $n$ is chorded pancyclic if $G$ contains a chorded $k$-cycle for every integer $k$ with $4\le k\le n$. Cream, Gould and Hirohata (Australas. J. Combin. 67 (2017), 463–469) proved that a graph of order $n$ satisfying ${deg}_{G}u+{deg}_{G}v\ge n$ for every pair of nonadjacent vertices $u$,  $v$ in $G$ is chorded pancyclic unless $G$ is either $K_{\frac{n}{2},\frac{n}{2}}$ or $K_3\square K_2$, the Cartesian product of $K_3$ and $K_2$. They also conjectured that if $G$ is Hamiltonian, we can replace the degree sum condition with the weaker density condition $\left|E\left(G\right)\right|\ge \frac{1}{4}{n}^2$ and still guarantee the same conclusion. In this paper, we prove this conjecture by showing that if a graph $G$ of order $n$ with $\left|E\left(G\right)\right|\ge \frac{1}{4}{n}^2$ contains a $k$-cycle, then $G$ contains a chorded $k$-cycle, unless $k=4$ and $G$ is either $K_{\frac{n}{2},\frac{n}{2}}$ or $K_3\square K_2$, Then observing that $K_{\frac{n}{2},\frac{n}{2}}$ and $K_3\square K_2$ are exceptions only for $k=4$, we further relax the density condition for sufficiently large $k$.     

The partition of a strong tournament

A digraph T is strong if for every pair of vertices u and v there exists a directed path from u to v and a directed path from v to u. Denote the in-degree and out-degree of a vertex v of T by d^-(v) and d⁺(v), respectively. We define δ^-(T)=min_vV(T){d^-(v)} and δ⁺(T)=min_vV(T){d⁺(v)}. Let T₀ be a 7-tournament which contains no transitive 4-subtournament. In this paper, we obtain some conditions on a strong tournament which cannot be partitioned into two cycles. We show that a strong tournament T with n6 vertices such that TT₀ and max{δ⁺(T),δ^-(T)}3 can be partitioned into two cycles. Finally, we give a sufficient condition for a tournament to be partitioned into k cycles.     

K1,4-自由的模κ泛圈图

设G是2-连通的K1，4自由图．本文证明了当δ(G)≥κ 1时，G是模κ泛圈图．这一结果肯定了猜想2，继而也肯定了Thomassen猜想在2-连通图中的正确性．     

K(1,4)-自由的模k泛圈图(英文)

设G是2-连通的K1,4自由图.本文证明了当δ(G)≥k 1时,G是模k泛圈图.这一结果肯定了猜想2,继而也肯定了Thomassen猜想在2-连通图中的正确性.     

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

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

Bondy的泛圈图定理的改进

记G=(V,E)是简单图,1971年Bondy得到O re条件下的泛圈图的著名结果:若2连通n阶图G的不相邻的任两点x、y均有d(x) d(y)≥n,则G是泛圈图或G=Kn/2,n/2.这里进一步研究条件d(x) d(y)≥n-1,得到:若2连通n阶图G的不相邻的任两点x、y均有d(x) d(y)≥n-1,则G是泛圈图或G∈{K(Cn 1)/2∨G(n-1)/2,Kn/2,n/2}.本文作者得知最近国际著名权威专家Ho lton等人也得到完全相同的结果,但本证明更简捷.     

邻域并与泛圈图

本文中 ,我们用邻域并对泛圈图进行深入的研究 ,主要取得了“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”