Approximation Algorithms for the Achromatic Number

The achromatic number for a graph G = V, E is the largest integer m such that there is a partition of V into disjoint independent sets {V₁, …, V_m} such that for each pair of distinct sets V_i, V_j, V_i V_j is not an independent set in G. Yannakakis and Gavril (1980, SIAM J. Appl. Math.38, 364–372) proved that determining this value for general graphs is NP-complete. For n-vertex graphs we present the first o(n) approximation algorithm for this problem. We also present an O(n^5/12) approximation algorithm for graphs with girth at least 5 and a constant approximation algorithm for trees.     

Linear Extensions of Additive Partial Orders

Addive partial orders arise naturally in theories of comparativeprobability and subset preferences. An additive partial order is a partialorder on the family of subsets of ann-element set that satisfies . This is reformulated as a subset P of {1,0,–1}ⁿ that excludes 0 and containsx+y whenever x,y P and x+y {1,0,–1}ⁿ. Additional conditions of positivity andcompleteness give rise to positive additive partial orders and additivelinear orders respectively. The paper investigates conditions under which anadditive partial order is included in, or extendable to, an additive linearorder. The additive dimension of an extendable additive partial order isdefined and computed for several classes of additive orders.     

Proper and Unit Trapezoid Orders and Graphs

We show that the class of trapezoid orders in which no trapezoid strictly contains any other trapezoid strictly contains the class of trapezoid orders in which every trapezoid can be drawn with unit area. This is different from the case of interval orders, where the class of proper interval orders is exactly the same as the class of unit interval orders.     

Recognition by the Set of Element Orders of Symmetric Groups of Degree r and r+1 for Prime r

We prove that the symmetric group S _r of prime degree r17 is recognizable by its element order set. A test for recognizability is obtained for the symmetric group S _r+1 with r17 prime.     

具有较小直径的三类图的对极色数

对一个连通图G,令d(u,v)表示G中两个顶点间u和v之间的距离,d表示G的直径.G的一个对极染色指的是从G的顶点集到正整数集(颜色集)的一个映射c,使得对G的任意两个不同的顶点u和v满足d(u,v)+|c(u)-c(v)|≥d.由c映射到G的顶点的最大颜色称为c的值,记作ac(c),而对G的所有对极染色c,ac(c)的最小值称为G的对极色数,记作ac(G).本文确定了轮图、齿轮图以及双星图三类图的对极色数,这些图都具有较小的直径d.     

Euler数，Bernoulli数及有序Bell数的渐近估计

利用特殊函数的发生函数为亚纯函数的特点,给出Euler数、Bernoulli数、有序Bell数等几个组合数的带有余项的渐进估计．     

基于BP神经网络的手写体数字的识别方法研究

对手写体数字的识别问题进行了讨论,提出一种基于BP神经网络的识别方法.从而提高了识别效率.主要就在识别时,数字在图片上的位置和数字本身大小方面做了改进,发现数字在图片上的大小和其在图片上的位置直接影响识别效果.具体做的是,首先提取了图片的轮廓,然后归一化成28×28的图像.这样做,不仅使得图像数字区域大小相同,而且都在图像中心上,使得识别结果变的更加理想化,达到了高识别的目的.另外,选择了容错性较好的BP网络,以200组手写体数字图像作为输入向量,以其他的110组进行识别,效率达到了90%.     

基于SVM的车牌数字识别方法

运用支持向量机对车牌字符进行识别,解决了由于图像受客观条件的影响、样本数量不是很大等原因导致的识别率不高的问题.主要针对车牌字符中的数字进行实验,选取了15组数字样本,8组进行训练,7组进行测试,采用交叉验证的思想对SVM进行参数C与g的寻优,并选择合适的核函数,对样本进行训练和预测,对于某些数字的识别率可达到100%,并在相同的训练集和测试集下与BP网络的识别效果进行对比.实验结果表明,SVM在训练样本较少且无字符特征提取的情况下具有很好的识别率,并且有很好的分类推广能力.     

Elementary Properties of Cycle-free Partial Orders and their Automorphism Groups

A classification was given by Creed, Truss, and Warren of all the countable k-CS-transitive cycle-free partial orders for k3. Here the elementary theories of these structures and their automorphism groups are examined, and it is shown that in many cases we can distinguish the structures or their groups by means of their first- or second-order properties. The small index property is established for weakly 2-transitive trees, and for several classes of cycle-free partial orders.     

Partial Online List Coloring of Graphs

For a graph G, let be the maximum number of vertices of G that can be colored whenever each vertex of G is given t permissible colors. Albertson, Grossman, and Haas conjectured that if G is s‐choosable and , then . In this article, we consider the online version of this conjecture. Let be the maximum number of vertices of G that can be colored online whenever each vertex of G is given t permissible colors online. An analog of the above conjecture is the following: if G is online s‐choosable and then . This article generalizes some results concerning partial list coloring to online partial list coloring. We prove that for any positive integers , . As a consequence, if s is a multiple of t, then . We also prove that if G is online s‐choosable and , then and for any , .     

平面图的绑定数

图G的绑定数b(G)是指边集合的最少边数,当这个边集合从G中去掉后所 得图的控制数大于G的控制数． Fischermann等人在[3]中给出了两个猜想: (1)如果 G是一个连通的平面图且围长g(G)≥4,则b(G)≤5;(2)如果G是一个连通的平面图且 围长g(G)≥5,则b(G)≤4．设n3表示度为3的顶点个数,r4和r5分别表示长为4和 5的圈的个数．本文,我们证明了如果r4<(5n3)/2 10,则猜想1成立;如果r5<12,则猜 想2成立．     

图的孤立断裂度

连通图G的孤立断裂度isc(G)=max{i(G-S)-|S|:S∈C(G)},其中i(G-S)是G-S中的孤立点数,C(G)是G的点割集.本文研究了孤立断裂度和图的其它一些参数的关系.讨论了孤立断裂度取特殊值的一些图,证明了圈、连通二部图、连通二部图的联图以及树和圈的补图的孤立断裂度都达到最小.给出了具有给定阶数和最大度的村的最大、最小孤立断裂度.     

English Decycling Number of Some Graphs

1.IntroductionInthispaper,weonlydiscusssimplegraph(withneithermulti-edgenorloop).TheterminologiesnotexplainedcanbeseeninII].Thecyclerankofagraphistheminimumnumberofedgesthatmustberemovedinordertoeliminateallofthecyclesinthegraph.IfGhaspvenices,qedges...     

算子偏序的刻画及性质

本文定义了Hilbert空间上两个算子间的四种关系:星序、左星序,右星序及减序,使用了算子分块矩阵的方法,给出了两个算子具有上述四种关系之一时它们几何结构的刻画,证明了这四种关系是真正的偏序关系,进一步研究了它们之间的关系和性质.     

Lower Bounds of Size Ramsey Number for Graphs with Small Independence Number

Acta Mathematicae Applicatae Sinica, English Series - Let r ≥ 3 be an integer such that r ? 2 is a prime power and let H be a connected graph on n vertices with average degree at least...     

Orderings on Graphs and Game Coloring Number

Many graph theoretic algorithms rely on an initial ordering of the vertices of the graph which has some special properties. We discuss new ways to measure the quality of such orders, give methods for constructing high quality orders, and provide applications for these orders. While our main motivation is the study of game chromatic number, there have been other applications of these ideas and we expect there will be more. This revised version was published online in June 2006 with corrections to the Cover Date.     

On Domination Number of 4-Regular Graphs

Let G be a simple graph. A subset S V is a dominating set of G, if for any vertex v V – S there exists a vertex u S such that uv E(G). The domination number, denoted by (G), is the minimum cardinality of a dominating set. In this paper we prove that if G is a 4-regular graph with order n, then (G) ⁴/₁₁ n     

高度图的关联色数

为了解决强边着色猜想,1993年,Brualdi和Massey（Discrete Math. (122)51-58)引入了关联着色概念,陈东灵等证明了对于△（G）=n-2的图G.inc(G)≤△(G) 2,其中n是G的阶数,本将进一步探讨在什么条件下,它的关联色数肯定是△（G） 1,又在什么条件下,肯定是△（G） 2。     

划分图上的正影响数

一个社会网络中通常包括具有正面影响和负面影响的两类人员,为了研究这个社会网络中人们之间相互影响的某些规律,引入了一个新的概念. 用划分图G=(V,E),V=V⁺ \cup V^-表示这样的一个社会网络,其中V⁺和V^- 分别表示正面人员的集合和负面人员的集合. 图G的一个点子集D\subseteq V^-被称为G的一个正影响集,若G的每个点的至少一半的邻点在D\cup V⁺中. G的所有正影响集的最小基数称为G的正影响数. 给出G的正影响数的几个下界并证明了这些界是紧的. 此外,还证明了求正影响数问题在二部图和弦图上都是NP-完全的.