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.     

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相似文献   

On the Merrifield-Simmons Indices and Hosoya Indices of Cyclic Graphs

The Merrifield-Simmons index and Hosoya index are defined as the number of the graph G（V, E） as the number of subsets of V（G） in which no tow vertices are adjacent and the number of subsets of E（G） in which no two edges are incident, respectively. In this paper, we characterize the Unicyclic graphs with Merrifield-Simmons indices and Hosoya indices, respectively. And double-cyclic graphs with Hosoya indices among the doublecyclic graphs with n vertices.     

基于直接信号流图的数字控制系统计算机辅助分析

根据数字控制系统的直接信号流图,设计了改进的Johnson算法,并用MATLAB语言编制了适用任意输入信号的数字控制系统的计算机辅助分析软件。该软件模型输入简单,不仅能得到系统的输出响应,而且还能得到系统输出模型,为数字控制系统的计算机辅助设计和仿真提供了有用的工具。     

IMPLICIT DEGREES AND CHVATAL'S CONDITION FOR HAMILTONICITY

Based on the ideas in[9],an integer d~0(v),called the implicit degree of v whichsatisfies d~0(v)≥d(v),is associated with each vertex v of a graph G.It is proved that if theimplicit degree sequence d_1~0,d_2~0,…,d_n~0(where d_1~0≤d_2~0≤…≤d_n~0)of a simple graph G on n≥3vertices satisfiesd_i~0≤i相似文献