强竞赛图中包含一条路的圈

设T为强竞赛图,P为T中一条长度为2的路.给出了T存在包含P的一些圈的充分条件.     

推点与二部竞赛图的强连通性

设D是一个有向图,S是V(D)的子集．在D中推S,是指颠倒D中所有的只有一个端点在S中的弧的方向． Klostermeyer提出了对于任给的一个有向图D,能否通过推点使之成为强连通的有向图的问题．他证明了上述判定问题是NP-完备的．而我们论证了对于任意的二部竞赛图D,如果V(D)的二划分是(X,Y),并满足3≤|X|≤|Y|≤2|X|-1-1, 则可以通过推点使D成为强连通的有向图,而且,|Y|的上界2|X|-1-1是最好可能的．     

3—连通正则无爪图的Hamilton圈

本文证明了：任一阶数不超过６ｋ－４的３－连通ｋ－正则无爪图是Ｈａｍｉｔｏｎ的。     

关于三圈连通标号图的计数公式

关于三圈连通标号图的计数公式张树生江西宁都固厚中学本文所指的图者是无向简单图。如果一个图恰好包含有ｍ个初级圈，那么就说这个图恰好包含有ｍ个单个的圈。Ｈａｒａｒｙ在［１］中提出了给定圈的个数的连通标号圈的计数问题。Ｒｅｎｙｉ在［２］中解决了单圈边通标号...     

完全图圈分解的一种新方法

本文给出完全图圈分解的一种新方法，设Ｋｎ（ｎ≥３）是一个ｎ阶完全图，我们得到下列结果：（１）若ｎ为奇数，Ｇ是ｎ阶群，并且｛ｏ（ｘ）│∈Ｇ，ｏ（ｘ）≥３｝＝｛ａ１，…，ａｔ｝，则Ｋｎ＝ｍ１Ｃａ１＋…＋ｍｔＣａｔ。（２）若ｎ为偶数，Ｇ是ｎ阶群，Ｔ＝｛ｘ│ｘ∈Ｇ，ｏ（ｘ）＝２｝＝｛ｘ０，ｘ１，ｙ１，…，ｘｓ，ｙｓ｝，ｏ（ｘｉｙｉ）＝ｂｉ，ｉ＝１，…，ｓ及｛ｏ（ｘ）│ｘ∈Ｇ，ｏ（ｘ）≥｝＝｛ａ１，…，ａｔ     

三圈图的极小广义和连通指数

图的广义和连通指数作为新提出的一类分子拓扑指数, 在QSPR/QSAR 中有很大的应用价值. 树图、单圈图和双圈图的极值问题已取得很多结果, 而三圈图相关问题的研究较为复杂. 限制 - 1\leqslant \alpha < 0, 对三圈图的广义和连通指数进行了研究. 通过对三圈图的分析, 构造了一种图的变换, 指出在三圈图中广义和连通指 数的极小值必由其中的七种类型图取得. 然后通过悬挂边的变换, 最终得到三圈图广义和连通指 数的极小值并刻画了唯一的极图.     

3强竞赛图的得分向量

如果对n阶竞赛图T_n的每个h—1元顶点子集U,删点子图T_n—U都是强的,则称T_n是h强的。如果非降的非负整向量R_n=(r_1,r_2,…,r_n)是某个n阶h强竞赛图的得分向量,则称R_n是隐含h强的;如果所有以R_n为得分向量的n阶竞赛图都是h强的,则称R_n是完全h强的。本文给出了得分向量R_n隐含3强和完全3强的判准。     

图的强符号圈控制数

本文研究了图的强符号圈控制数γ′_(ssc)(G).利用最大独立集最大匹配等方法,刻画了满足γ′_(ssc)(G)=|E|-2的所有连通图,给出了γ′_(ssc)(G)的一个下界,求出了两类特殊图的强符号圈控制数.     

2-连通半无爪图的最长圈

A graph G is called quasi-claw-free if it satisfies the property:d(x,y)=2 there exists a vertex u∈N(x)∩N(y)such that N[u]■N[x]∪N[y].In this paper,we show that every 2-connected quasi-claw-free graph of order n with G■F contains a cycle of length at least min{3δ+2,n},where F is a family of graphs.     

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.     

Decomposing oriented graphs into transitive tournaments

For an oriented graph G with n vertices, let f(G) denote the minimum number of transitive subtournaments that decompose G. We prove several results on f(G). In particular, if G is a tournament then and there are tournaments for which f(G)>n²/3000. For general G we prove that f(G)?⌊n²/3⌋ and this is tight. Some related parameters are also considered.     

某些Lie单群的传递性

设D为有限线性空间，且T G Aut（T），其中T是非交换单群，并且同构于^2B2（g），Cn（g）（n≥3），^3D4（g），E7（q），E8（q），F4（q），^2F4（q），G2（q），^2G2（q）。假设D不是射影平面，G线传递作用在D上，则T点传递。     

Tournaments associated with multigraphs and a theorem of Hakimi

A tournament of order n$n$ is usually considered as an orientation of the complete graph _Kn$K_n$. In this note, we consider a more general definition of a tournament that we call aC$C$-tournament, where C$C$ is the adjacency matrix of a multigraph G$G$, and a C$C$-tournament is an orientation of G$G$. The score vector of a C$C$-tournament is the vector of outdegrees of its vertices. In 1965 Hakimi obtained necessary and sufficient conditions for the existence of a C$C$-tournament with a prescribed score vector R$R$ and gave an algorithm to construct such a C$C$-tournament which required, however, some backtracking. We give a simpler and more transparent proof of Hakimi’s theorem, and then provide a direct construction of such a C$C$-tournament which works even for weighted graphs.     

具有固定得分向量的竞赛矩阵的数目

本文考虑以允许平局的单循环比赛为模型的竞赛图（二重完全图）的定向图的邻接矩阵（竞赛矩阵）．给出了具有特殊得分向量的竞赛矩阵的数目,得到了具有ｎ阶强有效得分向量的竞赛矩阵的数目的下确界,并给出了达到此下界的得分向量的刻划．     

A Note on a Packing Problem in Transitive Tournaments

Let TT_n 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 TT_n. Moreover, this bound is generally the best possible. The research partially supported by KBN grant 2 P03A 016 18     

A note on sensitivity of semigroup actions

It is well known that for a transitive dynamical system (X,f) sensitivity to initial conditions follows from the assumption that the periodic points are dense. This was done by several authors: Banks, Brooks, Cairns, Davis and Stacey (Am. Math. Mon. 99, 332–334, 1992), Silverman (Rocky Mt. J. Math. 22, 353–375, 1992) and Glasner and Weiss (Nonlinearity 6, 1067–1075, 1993). In the latter article Glasner and Weiss established a stronger result (for compact metric systems) which implies that a transitive non-minimal compact metric system (X,f) with dense set of almost periodic points is sensitive. This is true also for group actions as was proved in the book of Glasner (Ergodic Theory via Joinings, 2003). Our aim is to generalize these results in the frame of a unified approach for a wide class of topological semigroup actions including one-parameter semigroup actions on Polish spaces.     

强非零线性系统有正解的判定

本文给出了判定强非零线系统有正解的一系列结果。     

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.