关于二次型图的完美性

本文应用强完美图定理,解决了二次型图的完美图判别问题.     

基于图方法的自回归和双线性时间序列模型系数的检验

自回归和双线性时间序列模型被表示为时间序列链图模型.在此基础上, 证明了自回归和双线性模型的系数为其他时间序列分量给定的条件下的条件相关系数.然后提出基于图的检验方法来检验自回归和双线性模型系数的显著性, 模拟结果表明此方法在水平和功效方面表现很好.     

E_1 ~oE_d型距离正则图的关于余弦序列的不等式

给出了E1 Ed型距离正则图的关于余弦序列的不等式.     

侧向加热腔体中的多圈型对流斑图

基于流体力学方程组的数值模拟,研究了倾角θ=90°时侧向加热的大高宽比腔体中的对流斑图.对于Prandtl数Pr=6.99的流体,在相对Rayleigh数2≤Ra r≤25的范围内,腔体中发生的是单圈型对流斑图.对于Pr=0.0272的流体,取Ra r=13.9,随着计算时间的发展,腔体中由最初的单圈型对流斑图过渡到多圈型对流斑图,这是出现在侧向加热大高宽比腔体中的新型对流斑图.对不同Ra r情况的计算结果表明,Ra r对对流斑图的形成存在明显的影响.当Ra r≤4.4时是单圈型对流滚动;当Ra r=8.9~11.1时是过渡状态;当Ra r≥13.9时是多圈型对流滚动.对流最大振幅和Nusselt数Nu随着相对Rayleigh数的增加而增加.该对流斑图与Pr=6.99时对流斑图的比较说明,对流斑图的形成依赖于Prandtl数.     

图^nUi=1 Fmi,t和^nUi=1 Hmi,t的优美性

本文构造了两类非连通图^nUi=1 Fmi,t和^nUi=1 Hmi,t并证明了这两类图是优美的，且也是交错的。     

Fan型条件对图的匹配的影响(英文)

设G是顶点数为2n且至多含有2(n-c)个奇分支的简单图(1≤c≤n).若不存在G的两个距离为2的顶点,其度均小于c-1,则G的边独立数至少为c,除非G含一类明显的禁用导出子图.特别,我们给出了Fan(-1)-型图含有1-因子的充要条件.     

具有广义可行性余弦序列的E1(。)Ed型距离正则图

给出了具有广义可行性余弦序列的E1(?)Ed型距离正则图的特征,并计算了这类图的交叉数.     

关于指数型丢番图方程的整数解

本文简要地介绍了有关Ｓ－单位方程、Ｒａｍａｎｕｊａｎ－Ｎａｇｅｌｌ方程、Ｔｈｕｅ－Ｍａｈｌｅｒ方程、ＬｅＶｅｑｕｅ方程、Ｃａｔａｌａｎ方程、Ｐｉｌｌａｉ方程等指数型丢番图方程整数解的最新结果。这些结果大多是用Ｔｈｕｅ－Ｓｉｅｇｌｅ－Ｒｏｔｈ－Ｓｃｈｍｉｄｔ方法和Ｇｅｌ’ｆｏｎｄ－Ｂａｋｅｒ方法得到的。     

E1(о)Ed型距离正则图的关于余弦序列的不等式

给出了E1(о)Ed型距离正则图的关于余弦序列的不等式.     

损伤断裂图型演化的统计描述

本文采用动力学演化与随机跃迁并存的模型,研究损伤断裂图型的演化规律。根据演化的终态,损伤演化可分为整体稳定(GS)和演化引起剧变(EIC)两种模式,后者联系于断裂现象。本文引入统计描述,并指出,即使微损伤的连接规律是确定性的,无序介质中断裂的出现亦应以概率分布函数描写。     

Smith Normal Form and acyclic matrices

An approach, based on the Smith Normal Form, is introduced to study the spectra of symmetric matrices with a given graph. The approach serves well to explain how the path cover number (resp. diameter of a tree T) is related to the maximal multiplicity MaxMult(T) occurring for an eigenvalue of a symmetric matrix whose graph is T (resp. the minimal number q(T) of distinct eigenvalues over the symmetric matrices whose graphs are T). The approach is also applied to a more general class of connected graphs G, not necessarily trees, in order to establish a lower bound on q(G).     

On the Laplacian Eigenvalues of Signed Graphs

A signed graph is a graph with a sign attached to each edge. This article extends some fundamental concepts of the Laplacian matrices from graphs to signed graphs. In particular, the largest Laplacian eigenvalue of a signed graph is investigated, which generalizes the corresponding results on the largest Laplacian eigenvalue of a graph.     

图的最小完整度

主要研究了图的完整度,并给出若干关于完整度的结果. 对于所有的顶点数和边数都给定的连通图类,如何确定该图类中完整度最小的图. 同时研究了对于顶点数和完整度都给定的连通图类,如何确定该图类中边数最多的图的问题. 这些结果为图的最小完整度的优化设计提供了理论和方法.     

Thickness-Two Graphs Part Two: More New Nine-Critical Graphs,Independence Ratio,Cloned Planar Graphs,and Singly and Doubly Outerplanar Graphs

There are numerous means for measuring the closeness to planarity of a graph such as crossing number, splitting number, and a variety of thickness parameters. We focus on the classical concept of the thickness of a graph, and we add to earlier work in [4]. In particular, we offer new 9-critical thickness-two graphs on 17, 25, and 33 vertices, all of which provide counterexamples to a conjecture on independence ratio of Albertson; we investigate three classes of graphs, namely singly and doubly outerplanar graphs, and cloned planar graphs. We give a sharp upper bound for the largest chromatic number of the cloned planar graphs, and we give upper and lower bounds for the largest chromatic number of the former two classes.     

Perfect Matchings of Cellular Graphs

We introduce a family of graphs, called cellular, and consider the problem of enumerating their perfect matchings. We prove that the number of perfect matchings of a cellular graph equals a power of 2 times the number of perfect matchings of a certain subgraph, called the core of the graph. This yields, as a special case, a new proof of the fact that the Aztec diamond graph of order n introduced by Elkies, Kuperberg, Larsen and Propp has exactly 2 ^n(n+1)/2 perfect matchings. As further applications, we prove a recurrence for the number of perfect matchings of certain cellular graphs indexed by partitions, and we enumerate the perfect matchings of two other families of graphs called Aztec rectangles and Aztec triangles.     

Precoloring Extension of Co-Meyniel Graphs

The pre-coloring extension problem consists, given a graph G and a set of nodes to which some colors are already assigned, in finding a coloring of G with the minimum number of colors which respects the pre-coloring assignment. This can be reduced to the usual coloring problem on a certain contracted graph. We prove that pre-coloring extension is polynomial for complements of Meyniel graphs. We answer a question of Hujter and Tuza by showing that “PrExt perfect” graphs are exactly the co-Meyniel graphs, which also generalizes results of Hujter and Tuza and of Hertz. Moreover we show that, given a co-Meyniel graph, the corresponding contracted graph belongs to a restricted class of perfect graphs (“co-Artemis” graphs, which are “co-perfectly contractile” graphs), whose perfectness is easier to establish than the strong perfect graph theorem. However, the polynomiality of our algorithm still depends on the ellipsoid method for coloring perfect graphs. C.N.R.S. Final version received: January, 2007     

偶匹配可扩性的极图问题(英文)

设G是含有完美匹配的简单图.称图G是偶匹配可扩的(BM-可扩的),如果G的每一个导出子图是偶图的匹配M都可以扩充为一个完美匹配.极图问题是图论的核心问题之一.本文将刻画极大偶匹配不可扩图,偶图图类和完全多部图图类中的极大偶匹配可扩图.     

Convex Quadratic Programming Approach to the Maximum Matching Problem

The problem of determining a maximum matching or whether there exists a perfect matching, is very common in a large variety of applications and as been extensively studied in graph theory. In this paper we start to introduce a characterisation of a family of graphs for which its stability number is determined by convex quadratic programming. The main results connected with the recognition of this family of graphs are also introduced. It follows a necessary and sufficient condition which characterise a graph with a perfect matching and an algorithmic strategy, based on the determination of the stability number of line graphs, by convex quadratic programming, applied to the determination of a perfect matching. A numerical example for the recognition of graphs with a perfect matching is described. Finally, the above algorithmic strategy is extended to the determination of a maximum matching of an arbitrary graph and some related results are presented.     

Convex Quadratic Programming Approach to the Maximum Matching Problem

The problem of determining a maximum matching or whether there exists a perfect matching, is very common in a large variety of applications and as been extensively studied in graph theory. In this paper we start to introduce a characterisation of a family of graphs for which its stability number is determined by convex quadratic programming. The main results connected with the recognition of this family of graphs are also introduced. It follows a necessary and sufficient condition which characterise a graph with a perfect matching and an algorithmic strategy, based on the determination of the stability number of line graphs, by convex quadratic programming, applied to the determination of a perfect matching. A numerical example for the recognition of graphs with a perfect matching is described. Finally, the above algorithmic strategy is extended to the determination of a maximum matching of an arbitrary graph and some related results are presented.