一类图的特征多项式与匹配多项式

本文对一类具有对称轴的图A_n(n≥0),得到了它的特征多项式及匹配多项式的精确表达式;同时还得到A_(?)的完美匹配数。     

一类图的圈多项式

对任一个简单图G,我们构选出一类图M_(n≥1)。本文研究了图M_(?)的(?)多项式C(M_(?);w)的消去性质,并得C(M_(?);w)的递推关系表达式及C(M_(?);w)的具体表达式。     

THE CONSTRUCTION OF 133-CUBIC GRAPHS

We present a method to construct all,but one,133-cubic graphs.1.PrliminariesLet G be a nontrivial loopless graph with vertex—set V(G)and edge-setE(G),denoted as V and E respectively.A subgraph L of G is called a maxi-mum bipartite Subgraph,denoted as MBS,if L has a maximum number of     

三个图类的完美匹配计数(英文)

对一个具有偶数个顶点的图,计算它的完美匹配数是一个广泛而且深入地研究着的课题。对大量的图类,这个课题的研究已取得许多重要而且漂亮的结果。特别地,计算那些代表着某些有机化合物的图类的完美匹配数问题在理论和应用上都有着重要意义。本文讨论了三个图类的完美匹配计数,并对所有可能的情况给出完美匹配数或计数公式。     

两类图的匹配多项式

本文得到两类图—广义polyphenylene和广义共轭图链一的匹配多项式的精确表达式。特别地,对任意整数n≥0,我们得到polyphenyene M_n,pentagonal链C_n与苯链B_n的匹配多项式的精确表达式,对苯链B_n,Farrel等只得到n≤7的表达式(见文献[3])。     

论abc—三次图

G.Malle在《论最大二部分子图》一文中提出了关于abc—三次图的一些问题,他指出了111—三次图是连通二部分三次图,并证明了不含三角形的图是222—三次图的充要条件是图为彼得松图或十二面体图,他还指出,对其它abc—三次图的特征是尚未解决的问题。本文解决了在“无三角形”限制下abc—三次图的存在性及最小图,以及不加任何限制的abc—三次图的存在性及最小图。本文及我们的[5][6][7]三文基本上解决了G.Malle提出的问题,同时也证实了他关于“可能某些abc—三次图不存在”的说法, 一、无三角形abc—三次图的存在性及最小图本文使用[1]及[2]的有关术语及记号。图G的子图H称为G的最大二部分子图,若对G的任意二部分子图H′,都有ε(H′)≤ε(H),这里ε表示图的棱数。     

133—三次图的结构

在[1]中引入了abc—三次图的概念,但仅讨论了两类特殊abc—三次图的结构,本文的目的是解决133一三次图的结构问题。我们用G表示一个连通、无自环、非K_4的三次图,L表示G的最大二部分子图,若S是G的顶点集V(G)的一个子集,则K=[S,]表示G的一个棱截,截指标c(K,L)定义为: c(K,L)=|K∩L|-|K-L|=|L|-|KL|,其中“”表示对称差。本文引用的其它概念与记号见[1]、[2]、[3]。为了叙述方便,我们将133—三次图G的最大二部分子图L的顶点分划集X、Y以两种不同的染色,两个顶点不同色即指它们分属L的不同顶点分划集合。     

一个组合问题

给定两个不交非空有限集合X_1,X_2,|X_i|=a_i(i=1,2).我们考虑这样的集合B:B由三类元素构成.第一类是X_1×X_2的无序2-元组元素;第二,三类分别是X_1,X_2的元素(称为1-元组元素).对任意x∈X_i(i=1,2),x一定要在B的某类元素中出现;而且,若x出现在某个2-元组元素(x,y)或者(y,x)中,则它就不能再出现在其它2-元组元素中,x也不能作为B的一个1-元组元素。由上述的B的性质可见,B是由X_1,X_2依某种方式得到的,而且B的元素个数至少是max{a_1,a_2},至多是a_i+a_2.如果B恰好有m个元素,则称B为X_1,X_2的一个势为m的合并.本文将讨论势为m的     

有向圈半强积的哈密尔顿圈

设有向图 D_1=(V_1,A_1),D_2=(V_2 A_2).称有向图 D_2:D_2=(V,A) 为 D_1,D_2的半强积,如果 V=V_1×V_2,A={((u_1,v_1),(u_2,v_2))|u_1=u_2且(v_1,v_2)∈A_2或者(u_1,u_2)∈A_1且(v_1,v_2)∈A_2}.     

关于自中心图的运算

确定自中心图的特征是一个很困难的问题,已有一些工作通过不同的途径确定了某些自中心图类的特性。本文试图通过几种关于自中心图的运算来反映自中心图之间的某些联系,并给出几个图例来说明对某些图运算,自中心性质是不保持的。本文考虑的都是简单图,由于不连通图总是自中心图。故除个别情况外,本文主要讨论的都是连通图。对任一个简单图G,△(G)表示G中顶点的最大度数,v(G)表示G的顶点数目,V(G)表示G的顶点集合,E(G)表示G的边集合。设u、v是V(G)的两个