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.     

Two Sufficient Conditions for Hamiltonian Graphs

ＴｗｏＳｕｆｆｉｃｉｅｎｔＣｏｎｄｉｔｉｏｎｓｆｏｒＨａｍｉｌｔｏｎｉａｎＧｒａｐｈｓＬＩＧｕｏｊｕｎ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＹａｎｔａｉＴｅａｃｈｅｒ＇ｓＣｏｌｌｅｇｅ，Ｙａｎｔａｉ２６４０００，Ｓｈａｎｄｏｎｇ）ＬＩＵＺ...     

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.     

BINARY SEQUENCE WITH PERFECT SPREADING STAIRCASE PROFILE OF LINEAR COMPLEXITY

1.IntroductionThelinearcomplexityofasequenceisdefinedasthelengthoftheshortestlinearfeedbackshiftregisterthatcangeneratethesequence.LetS=s182s3''beaninfinitebinarysequence.S(n)=slsZ''sathesubsequenceofSformedbythefirstnbits,L(S(n))=L.thelinearcomplexityo…     

一种新的混沌序列随机性刻画及提高方法

通过定义混沌序列中元素之间的邻接关系,提出了一种基于网络邻接图的方法来刻画此序列的随机性.通过数值模拟发现此方法具有很好的有效性,且与传统的Lyapunov指数判别法相一致,尤其在Lyapunov指数难以求得的情况下,此方法具有很好的参照性.通过考察网络邻接图的度分布、聚类系数和平均路径长度,发现混沌序列的网络邻接图是无标度网络,并且具有明显的小世界特性.利用网络邻接图的无标度性,适当减少网络邻接图中为数不多的度大的点可以有效提高混沌序列的随机性.     

面向虚拟装配的装配顺序规划研究

针对虚拟装配中的产品装配顺序规划问题，提出层次化装配模型，在此基础上生成产品装配层次树结构，并给出基于装配关联图的分层规划算法，进一步，分析简化简装关联图的有效途径，并通过固定顺序判据法降低装配序列组合复杂性，提高装配顺序规划的效率。     

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…     

ON A CONJECTURE OF HARMONIOUS GRAPH

Let the coronas C_n⊙K_1 be the polygons with one additional end-point for eachvertex.Thom Grace conjectured that C_n⊙K_1 are harmonious for n even.In this paper,aproof of his conjecture is given.     

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.     

A Problem in Combinatorics

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

基于图序列的卫星网络时变拓扑可视分析

卫星网络拓扑结构具有典型的时变特征,对时变拓扑的可视化研究有助于直观理解卫星网络随时间的演化状态。从可视化的角度入手,针对上述时变特征,提出一种基于图序列的拓扑可视化方法。首先,设计时变拓扑可视化视图,作为传统两视图结构的重要补充;然后,建立图序列模型,并提出瞬时拓扑图布局算法和拓扑图序列布局算法;最后,通过典型实例验证所提算法的合理性。实验表明,时变拓扑分析视图在卫星网络拓扑信息展示方面能够起到辅助作用,时变拓扑可视化结果可以清晰地展示出视觉元素之间的关系,并支持对拓扑结构进行对比分析,有助于用户发现和理解卫星网络的动态演化规律。     

A 2－FACTORIZATION ORTHOGONAL TO A STAR IN A GRAPH

Ａ２－ＦＡＣＴＯＲＩＺＡＴＩＯＮＯＲＴＨＯＧＯＮＡＬＴＯＡＳＴＡＲＩＮＡＧＲＡＰＨ￥ＬＩＵＧｕｉｓｈｅｎ（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＳｈａｎｄｏｎｇＵｎｉｖｅｒｓｉｔｙ，Ｊｉｎａｎ２５０１００，Ｃｈｉｎａ）Ａｂｓｔｒａｃｔ：Ｌｅ...     

A Shortest Path Problem

ＡＳｈｏｒｔｅｓｔＰａｔｈＰｒｏｂｌｅｍ￥ＪＩＡＺｈｅｎｇｓｈｅｎｇ（ＭａｔｈｅｍａｔｉｃｓａｎｄＭｅｃｈａｎｉｃｓＤｅｐａｒｔｍｅｎｔｏｆＴａｉｙｕａｎＵｎｉｖｅｒｓｉｔｙｏｆｔｅｃｈｎｏｌｏｇｙＴａｉｙｕａｎ０３００２４）ＦＡＮＨｕｉ（Ｆｏｕｎｄ...     

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

PATHS BETWEEN TWO VERTICES IN A TREE GRAPH

Let T(G)be the tree graph of a simple graph G.It is proved that ifT and T′are two vertices of T(G)such that d_T(G)(T)(?)d_T(G}(T′),then there ared_T(G)(T) internally disjoint paths in T(G) joining T and T′.     

A NEIGHBORHOOD UNION CONDITION FOR PANCYCLIC GRAPHS

1.IntroductionWeconsideronlysimplefinitegraphs.OurbasicnotationandterminologynotdefinedherefollowthOSeofBondyandMurtyll].ForagraphG,letV(G)andE(G)(orjustVandE)deDOtelievertexsetandedgeset,respectively.Wedenoteapathandacyclecontaining8veniCesbyPaandCarespectively.ThecycleCaiscalledans-cycle.Denotebyg(G)(orbrieflybyg)thegirthofG1.SetNC=min{IN(u)UN(v)l:tv相似文献   

系统核度的一般算法

本文研究并解决了一般结构系统核度的计算方法,讨论了该算法在微机上的实现.     

A NEW SUFFICIENT CONDITION FOR S-CIRCUITS IN GRAPHS

In[1],P.Paulraja posed the following problem:Let G be a 2-connected graph suchthat δ(G)≥3,where δ(G)denotes the minimum degree of G.If each edge of G lies on either a cycle oflength 3 or a cycle of length 4,is it true that G has a spanning Eulerian subgraph?A related case inwhich δ(G)≥4 is settled affairmatively in this paper.     

A Fault-tolerant Routing Control for Double Loop Networks

This paper divides the vertex set into several disjoined subsets and provides an optimal fault-tolerance routing algorithm based on the vertex set partition. This algorithm is efficient and convergent, in polynomial time, we can get the output if the vertex is given.     

赋权Hamilton路的DNA计算模型

DNA计算是一种基于生化反应的新型计算方式 ,目前已成为一个非常热门的研究领域。首先简单介绍了DNA分子的结构、计算机理及实现方式。然后 ,在Adleman工作的基础上 ,给出了赋权 (有向与无向 )型Hamil ton路问题的DNA计算模型。通过权值的转换方式 ,指出此模型对于任意实数权值的赋权图均适应。最后 ,指出了该模型存在的问题及进一步研究的方向。研究结果进一步证实了DNA计算的可行性。