全变换图的基本性质

我们引入了四对变换图,其中有一对是全图和它的补图。我们研究这些变换图的基本性质。     

Double-Pullback Transitions and Coalgebraic Loose Semantics for Graph Transformation Systems

The classical algebraic approach to graph transformation is a mathematical theory based on categorical techniques with several interesting applications in computer science. In this paper, a new semantics of graph transformation systems (in the algebraic, double-pushout (DPO) approach) is proposed in order to make them suitable for the specification of concurrent and reactive systems. Classically, a graph transformation system comes with a fixed behavioral interpretation. Firstly, all transformation steps are intended to be completely specified by the rules of the system, that is, there is an implicit frame condition: it is assumed that there is a complete control about the evolution of the system. Hence, the interaction between the system and its (possibly unknown) environment, which is essential in a reactive system, cannot be modeled explicitly. Secondly, each sequence of transformation steps represents a legal computation of the system, and this makes it difficult to model systems with control. The first issue is addressed by providing graph transformation rules with a loose semantics, allowing for unspecified effects which are interpreted as activities of the environment. This is formalized by the notion of double-pullback transitions, which replace (and generalize) the well-known double-pushout diagrams by allowing for spontaneous changes in the context of a rule application. Two characterizations of double-pullback transitions are provided: the first one describes them in terms of extended direct DPO derivations, and the second one as incomplete views of parallel or amalgamated derivations. The issue of constraining the behavior of a system to transformation sequences satisfying certain properties is addressed instead by introducing a general notion of logic of behavioral constraints, which includes instances like start graphs, application and consistency conditions, and temporal logic constraints. The loose semantics of a system with restricted behavior is defined as a category of coalgebras over a suitable functor. Such category has a final object which includes all finite and infinite transition sequences satisfying the constraints.     

有关完全图的图的紧性

双随机矩阵有许多重要的应用,紧图族可以看作是组合矩阵论中关于双随机矩阵的著名的Birkhoff定理的拓广,具有重要的研究价值.确定一个图是否紧图是个困难的问题,目前已知的紧图族尚且不多,给出了三个结果:任意多个完全图的不交并是紧图;圈C_3与圈C_n(n3)的不交并是非紧图;当n是大于等于3的奇数时,完全图K_n与图K_(n+1)的不交并是非紧图,其中图K_(n+1)是从完全图K_(n+1)删去一因子而得到的图.     

一些图的倍图与Mycielski图的邻点可区别VE-全染色

对简单图G(V,E),存在一个正整数κ,使得映射f:V(G)U E(G)→{1,2…,κ},如果对uv∈E(G),有f(u)≠f(uv),f(v)≠f(uv),且C(u)≠C(v),则称f是图G的邻点可区别VE-全染色,且称最小的数κ为图G的邻点可区别VE-全色数,讨论了路、圈、星、扇、轮等一些图的倍图与Mycielski图的邻点可区别VE-全色数。     

完全多部图同构于二面体群的Cayley齐次分解

设Γ=K_(s[t])是一个完全多部图,其中st是一个偶数,则存在一个二面体群R=D_(2n)(n=st/2),使得R能构造出一个同构于K_(s[t])的Cayley图.讨论了当s、t满足什么条件时,完全多部图Γ有同构于Cay(R,S)的齐次分解.     

用超广义线图构造整谱图

线图在图的谱理论研究中起着重要的作用.在本文中,通过研究超广义线图成为整谱图的充分条件,获得了一种全新的构造新的整 谱图的方法,运用这种方法,可以构造出无穷多个新的整谱图.     

满足Hamilton图必要条件的非Hamilton图的最小例子

找到一个满足Hamilton图必要条件的非Hamilton图的最小例子.     

完全多部图的区间图完全化问题

The interval graph completion problem of a graph G includes two class problems: the profile problem and the pathwidth problem, denoted as P(G) and PW(G) respectively, where the profile problem is to find an interval supergraph with the smallest possible number of edges; the pathwidth problem is to find an interval supergraph with the smallest possible cliquesize. These two class problems have important applications to numerical algebra, VLSI-layout and algorithm graph theory respectively; And they are known to be NP-complete for general graphs. Some classes of special graphs have been investigated in the literatures. In this paper the exact solutions of the profile and the pathwidth of the complete multipartite Graph Kn1,n2,…,nr(r≥2) are determined.     

一类变换图的连通性

本文定义了一类由给定的一个３－正则平面偶图的全体完美匹配所构成的变换图，并证明了该变换图是连通的．由此可得出结论：从任一给定的３－正则平面偶图的完美匹配出发，通过一种所谓的旋转运算，就可以生成全部其它的完美匹配．     

恰有两个主特征值的图与图的剖分

大量研究表明,图的主特征值的数量与图的结构有着密切关系.通过恰有两个主特征值的图的特征定义了2-邻域k-剖分图,研究了恰有两个主特征值的图与2-邻域k-剖分图之间的关系;同时给出一个2-邻域k-剖分图在k=2,3时为等部剖分的条件.     

Graph Sharing Game and the Structure of Weighted Graphs with a Forbidden Subdivision

In the graph sharing game, two players share a connected graph G with nonnegative weights assigned to the vertices claiming and collecting the vertices of G one by one, while keeping the set of all claimed vertices connected through the whole game. Each player wants to maximize the total weight of the vertices they have gathered by the end of the game, when the whole G has been claimed. It is proved that for any class of graphs with an odd number of vertices and with forbidden subdivision of a fixed graph (e.g., for the class of planar graphs with an odd number of vertices), there is a constant such that the first player can secure at least the proportion of the total weight of G whenever . Known examples show that such a constant does no longer exist if any of the two conditions on the class (an odd number of vertices or a forbidden subdivision) is removed. The main ingredient in the proof is a new structural result on weighted graphs with a forbidden subdivision.     

Graph splicing systems

In this paper, extended graph splicing systems are defined. It is shown that when strings are represented as linear graphs, any recursively enumerable set can be generated by an extended graph splicing system. It is also shown that the computational completeness of extended graph splicing systems can be proved under some constraints too.     

Graph Designs for all Graphs with Six Vertices and Eight Edges

Graph designs for all graphs with six vertices and eight edges are discussed. The existence of these graph designs are completely solved except in two possible cases of order 32.     

Orientable Hamilton Cycle Embeddings of Complete Tripartite Graphs II: Voltage Graph Constructions and Applications

In an earlier article the authors constructed a hamilton cycle embedding of in a nonorientable surface for all and then used these embeddings to determine the genus of some large families of graphs. In this two‐part series, we extend those results to orientable surfaces for all . In part II, a voltage graph construction is presented for building embeddings of the complete tripartite graph on an orientable surface such that the boundary of every face is a hamilton cycle. This construction works for all such that p is prime, completing the proof started by part I (which covers the case ) that there exists an orientable hamilton cycle embedding of for all , . These embeddings are then used to determine the genus of several families of graphs, notably for and, in some cases, for .     

变换图的正则性和谱半径

在前人对八种变换图研究的基础上,探讨了变换后满足正则性的原图的性质,得到了如下结果:G~( )及G~(---)是正则图当且仅当G是正则图;G~( -)和G~(-- )为正则图的充要条件是G为C_n、K_(2,n-2)或K_4;G~( - )和G~(- -)是正则图当且仅当G为C_5、K_7、K_2、K_(3,3)或G_0;G~(- )和G~( --)是正则的当且仅当G是(n-1)/2-正则图．同时还讨论了变换图的谱半径上界,并对这些上界进行了估计．     

循环分布图最大边数猜想的一个反例

令ｆ（ｎ）为恰有ｎ个顶点，任意两个循环长度都不相等的图的最多边数．１９７５年，Ｅｒｄｏｓ提出确定ｆ（ｎ）的问题（见［１］Ｐ２７４，Ｐｒｏｂｌｅｍ１１）．１９８６年，Ｙ．Ｓｈｉ证明了对任意自然数ｎ≥３，有ｆ（ｎ）≥ｎ＋８ｎ－２３＋１／２［］，且当３≤ｎ≤１７时，等号成立．进而猜想：对于任何自然数ｎ≥３，上述等式都成立．本文对该猜想给出一个反例．     

Optimal Space Distributed Order-Preserving Lists

A move-to-front list is a distributed data object that provides an abstraction of a temporal ordering on a set of processes in a distributed system. We present a lower bound and a matching upper bound of Θ(log²n) bits on the space per processor needed to implement such a list using single-writer multiple-reader registers. A generalization is also discussed.