Several Sufficient Conditions for Class I

1　IntroductionIn1 964 ,the Soviet Union mathematician V.G.Vizing made a breakthrough resulton edgescoloring of graph:if G is a simple graph whose maximum degree isΔ ,then the edges of Gcan be normally colored withΔorΔ 1 colors.From this resultthe problem of classifyingsimple graphs arises,that is,what types of simple graph can be normally colored byΔcolors. Accordingly,there exists a similar problem of complex graphs. Solving theclassifying problem thoroughly means solving the4 -colo…     

Star Chromatic Numbers of Planar Graphs

１ＩｎｔｒｏｄｕｃｔｉｏｎＤｅｆｉｎｉｔｉｏｎ１．１Ｌｅｔｋ,ｄｂｅｎａｔｕｒａｌｎｕｍｂｅｒｓｓｕｃｈｔｈａｔｋ２ｄ,ａ（ｋ,ｄ）－ｃｏｌｏｒｉｎｇｏｆａｇｒａｐｈＧ＝（Ｖ,Ｅ）ｉｓａｍａｐｐｉｎｇｃ：Ｖ→Ｚｋ,ｓｕｃｈｔｈａｔｆｏｒｅａｃｈｅｄ...     

DEGREE CONDITIONS FOR GRAPHS TO BE FRACTIONAL （a, b, n）-CRITICAL GRAPHS

Let G be a graph, and a and b be integers with a ≤ b. A graph G is called a fraetional （a, b, n）-critical graph if after any n vertices of G are deleted the remaining subgraph has a fractional [a, b]-factor. In this paper two degree conditions for graphs to be fractional （a, b, n）-eritical graphs are presented, and the degree conditions are sharp in some sense.     

A k-HAMILTON-NICE SEQUENCE

Ａｋ－ＨＡＭＩＬＴＯＮ－ＮＩＣＥＳＥＱＵＥＮＣＥＬＩＵＹｉｐｉｎｇ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＮａｎｊｉｎｇＮｏｒｍａｌＵｎｉｖｅｒｓｉｔｙ，Ｎａｎｊｉｎｇ２１００２４，Ｃｈｉｎａ）ＴＩＡＮＦｅｎｇ（ＩｎｓｔｉｔｕｔｅｏｆＳｙｓ...     

EXISTENCE OF HAMILTONIAN k-FACTOR

A Hamiltonian k-factor is a k-factor containing a Hamiltonian cycle. An n/2-critical graph G is a simple graph of order n which satisfies S(G) > n/2 and δ(G - e)< n/2 for any edge e ∈ E(G). Let k > 2 be an integer and G be an n/2-critical graph of even order n > 8k-14. It is shown in this paper that for any given Hamiltonian cycle C except that G - C consists of two components of odd orders when fc is odd, G has a k-factor containing C.     

爪心独立图的可扩圈

图Ｇ中的一个与Ｋ１，３同构的导出子图叫做Ｇ的一个爪。爪中的３次顶点叫该爪的爪心。Ｂ表示Ｇ中所有爪心构成的集合。本文将证明：设Ｇ是顶点数≥３的连通、局部连通图，如果Ｇ的爪心集合Ｂ是点独立集，且Ｇ－Ｂ是局部连通的，则Ｇ是完全圈可扩的。     

EDGE CONDITION FOR A HAMILTONIAN BIPARTITE GRAPH TO BE BIPANCYCLIC

Let G be a hamiltonian, bipartite graph on 2n vertices, where n>3. It isshown that if e(G)>n(n-1)/2 + 2 then G contains cycles of every possible even length.This improves a result of Entringer and Schmeichel.     

A Problem in Combinatorics

ＡＰｒｏｂｌｅｍｉｎＣｏｍｂｉｎａｔｏｒｉｃｓ￥ＨＵＪｉｕｒｅｎ（ＮａｎｋａｉＩｎｓｔｉｔｕｔｅｏｆＭａｔｈｅｍａｔｉｃｓＴｉａｎｊｉｎ３０００７１）Ａｂｓｔｒａｃｔ：Ｉｎｔｈｉｓｐａｐｅｒ，ｂｙｕｓｉｎｇａｎｏｖｅｌｍｅｔｈｏｄｏｆｇｒａｐｈ－ｃｏ...     

FORBIDDEN SUBGRAPHS,DEGREES,NEIGHBORHOOD UNIONS AND CIRCUMFERENCES OF GRAPHS

Combining forbidden subgraphs with degree restrictions and neighborhood unionrestrictions,respectively,we prove the following results:(1) Let G be a 2-connected graph of order n,and 3≤c≤n.If for each induced subgraphL of order four of G(?)|V_1(L)∩S_c|≥2 if L≌K_(1,3),and |V(L)∩S_c|≥1 if L≌P_4,then thecircumference of G is at least c,where V_1(L)is the set of vertices with degree 1 of L,S_c isthe set of vertices with degree at least c/2 of G and P_4 is a path of order 4.(2) Let G be a 2-connected graph of order n,and n≥s+2.If for each induced subgraphL of G isomorphic to K_(1,3)or P_4,d_L(u,v)=2(?)|N(u)∪N(v)|≥s,then the circumferencec (G) of G is at least s+2.Moreover,if n≥s+3 and s is odd,then c(G)≥s+3.     

CYCLES CONTAINING MANY VERTICES OF SUBSETS IN GRAPHS WITH LARGE DEGREE SUMS AND NEIGHBORHOOD UNIONS

1. ResultsWe use[IJ for terminology and notations not defined here and consider simple graph only.Let G be a graph of order n and X C V(G). A graph G is called 1--tough if w(G\S) 5 ISIfor any S g V(G) with w(G\S) > 1, where w(G\S) denotes the number of components ofgraph G\S. A cycle C of G is called X-longest if no cycle of G contains more venices of Xthan C, and by c(X) we denote the number of venices of X in an X-longest cycle. A cycle Cof G is called X-dominating if all neigh…     

Traceability of Subsets in Cubic Graphs

１ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅｓｔｕｄｙｏｆｃｙｃｌａｂｉｌｉｔｙｏｆｒｅｇｕｌａｒｇｒａｐｈｓｉｓａｎａｃｔｉｖｅａｒｅａｏｆｒｅｓｅａｒｃｈｉｎｔｈｅｄｉｒｅｃｔｉｏｎｏｆＤｉｒａｃ’ｓＴｈｅｏｒｅｍ（ｅｖｅｒｙｋｃｏｎｎｅｃｔｅｄｇｒａｐｈ...     

Sufficient Conditions of Robust Schur Stability for Uncertain 2-D Polynomials

１　ＩｎｔｒｏｄｕｃｔｉｏｎＴｈｅｒｅｅｘｉｓｔｓａｋｉｎｄｏｆ２Ｄｄｉｓｃｒｅｔｅｓｙｓｔｅｍｓｗｉｔｈｕｎｃｅｒｔａｉｎｐａｒａｍｅｔｅｒｓｏｒｓｕｂｊｅｃｔｔｏｒａｎｄｏｍｄｉｓｔｕｒｂａｎｃｅｓ．Ｄｉｆｆｅｒｅｎｔｆｒｏｍｕｎｃｅｒｔａｉｎ１Ｄｐｏｌｙｎｏｍｉａｌｓ,ｔｈｅｐａｒａｍｅｔｅｒｓｐａｃｅｏｆｔｈｅｕｎｃｅｒｔａｉｎ２Ｄｐｏｌｙｎｏｍｉａｌｓｉｓｏｆ（Ｍ＋１）×（Ｎ＋１）ｄｉｍｅｎｓｉｏｎｓａｔｍｏｓｔ．ＴｈｏｕｇｈｓｏｍｅｒｅｓｕｌｔｓａｂｏｕｔｔｈｅｒｏｂｕｓｔＨ…     

A FURTHER GENERALIZATION OF JUNG''''S THEOREM

Let G be a graph of order n. We define the distance between two vertices u andv in G, denoted by d(u, v), as the minimum value of the lengths of all u-v paths. We writeσ_k(G)=min{∑_i=1~k d(v_i)|{v_1, v_2,…, v_k} is an independent set in G} and NC2(G)=min {|N(u)∪N(v)| | d(u, v)=2}. We denote by ω(G) the number of components of agraph G. A graph G is called 1-tough if ω(G\S)≤|S| for every subset S of V(G) withω(G\S)>l. By c(G) we denote the length of the longest cycle in G; in particular, G iscalled a Hamiltonian graph if c(G)=n. H.A. Jung proved that every 1-tough graphwith order n≥11 and σ2≥n-4 is Hamiltonian. We generalize it further as follows: ifG is a 1-tough graph and σ3(G)≥n, then c(G)≥min {n,2NC2(G)+4}. Thus, theconjecture of D. Bauer, G. Fan and H.J. Veldman in [2] is completely solved.     

On the Toughness and Fractional Perfect Matching of Graphs

In this paper, we prove the following results： let G be a graph with even order P ≥ 2k ＋ 2, if t（G） 〉 k, then the subgraph of G obtained by deleting any 2k-edges or 2k-vertices has a fractional perfect matching.     

多色图及其在仿真复杂对象及系统时的应用

在介绍了多色图的概念,多色图的组成和多色图的数学模型后,阐述了在围道析取矩阵的多色图PG和围道合取矩阵的多色图PG中路径F（μi）的计算公式和方法。最后举出了简例。多色图这一新的信息处理工具对复杂对象和系统具有强大的仿真功能。     

Edge-Fault-Tolerant Properties of Augmented Cubes

As an enhancement on the hypercube Qn, the augmented cube AQn, pro- posed by Choudum and Sunitha [Choudum S.A., Sunitha V., Augmented cubes, Networks, 40（2）（2002）, 71-84], possesses some properties superior to the hypercube Qn. In this paper, assuming that （u, v） is an arbitrary fault-free d-link in an n-dimensional augmented cubes, 1 ≤ d ≤ n - 1, n ≥ 4. We show that there exists a fault-free Hamiltonian cycle in the augmented cube contained （u, v）, even if there are 2n - 3 link faults.     

结构VAR模型辨识的条件互信息图模型

在结构向量自回归(VAR)模型辨识的图模型中引入信息论方法.定义了线性条件互信息图,图中的结点表示时间序列不同时刻的随机变量,结点间的边表示随机变量之间存在的因果相依关系.提出了随机变量之间条件线性联系存在性的信息论检验方法.图中边的存在性用基于线性条件互信息的枢轴量检验,枢轴量的显著性用置换检验决定.用统计分析的方法确定当前变量之间联系的方向,建立了有向非循环图.最后以模拟序列为例,验证了所提出的方法是可行且有效的.     

基于距离图的决策表简化方法

首先给出知识表达系统及决策表的距离图的概念 ;随后 ,借助距离图的性质 ,得到一种知识表达系统相容性判定与求核的方法 .特别地 ,这种方法可用于决策表相容性判定及条件属性核的求解 .最后 ,建立了一个利用约简决策表的距离图求决策规则的核值及最小决策算法的算法框架 .     

Alternative Theorems and Sufficient Conditions of Global Convergence for a Class of Feasible Direction Algorithms

In this paper,two alternative theorems which differ from Theorem 10.2.6 in [1] andTheorem 1 in [3] are presented for a class of feasible direction algorithms.On the basis of alternativetheorems,furthermore,two sufficient conditions of global convergence of this class of algorithms areobtained.     

A Degree Condition on Long Paths and Large Cycles

We present a new condition ensuring the existence of a large cycle of passing throughgiven edge.Let l(C)denote the length of the cycle C.Suppose G is a 4-connected graph withvertices set{x_1,x_2….x_n}and edge set E and with the property that,for any two positiveintegers j and k,j相似文献