蕴含三类导出子图的可图序列

对非负整数序列π=（d1,d2……,dn),0≤di≤n-1,本分别给出了它蕴含导出子图为几乎处处完全图,完全图去掉一个Hamilton圈的边,完全k-部图可图（即蕴含aw^1,Aw^2和Ar,r2…,rk-可图）的判别准则。     

蕴含W6-可图序列

摘要对于给定的图日,如果可图序列π有一个实现包含日作为子图,则称丌是蕴含H-可图的．本文给出了可图序列π蕴含W6-可图的一个充分条件,其中Wτ是τ个顶点的轮图．     

蕴含W_6-可图序列

对于给定的图H,如果可图序列π有一个实现包含H作为子图,则称π是蕴含H-可图的.本文给出了可图序列π蕴含W_6-可图的一个充分条件,其中W_r是r个顶点的轮图.     

图的度序列

图的度序列是图论研究中一个重要的课题．至今已发表了４００余篇文章．本文概述这一课题的某些进展，其中包括了可图序列的判准、蕴含Ｐ可图序列和强迫Ｐ可图序列的一些主要结论，同时列出了一些有待进一步研究的问题．     

可图序列偏序集的极小元

ｎ项非增非负整数序列是可图的,若是某个阶简单图的度序列．所有项和为２ｍ、迹为ｆ的ｎ项可图序列的集合Ｇ_ｎ,ｍ,ｆ在优超关系下是一个偏序集．本文刻划了偏序集Ｇ_ｎ,ｍ,ｆ的极小元,并确定各种可图序列偏序集中极小元的个数．     

Kotzig有向图的度偶序列

1.引言 设T_n是n阶竞赛图,V={v_1,v_2,…,v_n}是T_n的顶点集合。设扩v∈V,T_n中所有被v占优的顶点个数s(v)是v在T_n中的得分,记s(v_i)=s_i,i=1,2,…,n.将v_1,v_2,…,v_n重新排列,使s_1≤s_2≤…≤s_n,则S=(s_1,s_2,…,s_n)即是T_n的得分向量。 在Bondy与Murty的名著《图论及其应用》一书的末尾处列举了50个图论中未解决的问题,其中第45问题是:刻划所有n-1阶子竞赛图都同构的n阶竞赛图。这个问题是Kotzig 1973年提出的(见[1])。作者、黄国勋与林毓材研究了这个问题。文献     

极值图论与度序列

本文简要概述极值图论与度序列的最新研究进展，同时提出了一些有待进一步解决的问题和猜想．     

关于蕴含_3C_l可图序列的极值问题(英文)

设σ（3Cl，n）是具有下述性质的最小正偶数，每个项和至少为σ（3Cl，n）的n项可图序列。都有一个实现含有长为3，4，…，l的圈．本文确定了当7≤l≤8且n≥l以及当l=9且n≥12时响σ（3Cl，n）的值．     

蕴含K6-Z6-可图序列的刻划

对于给定的图日,若可图序列π有一个实现G以H为其子图,则称π为蕴含日一可图的．在本文,作者刻划了蕴含K6-Z6-可图序列．     

关于蕴含Ar,s—可图序列的注记

设G＝（V（G）,E（G）是n阶简单图,其顶点集V（G）＝{v1,…,vr,vr 1,…,vr s,…,vn},n={d1,…,dr 1,…,dr s,…,dn}是G的度序列,且vi的度为dio称G具有性质Ar,s,如果{v1,…,vr,vr 1,…,vr x}的导出子图是完全二部图Kr,s,且{v1,…,vr}和{vr 1,…,vr s}是Kr,s顶点集的二部划分,序列π={d1,…,dr,dr 1,…,dr s,…,dn}称为是蕴含Ar,s－可图的序列判别准则。     

连通图的度序列及连通平面图的低度点个数

美国数学家Bondy给出了一个非负整数序列为简单图的度序列的充要条件.本文对此进行了发展,证明了一个正整数序列为连通简单图的度序列的充要条件;然后在此基础上又探讨了平面图的低度点个数问题并定义了描述连通平面图的低度点个数的一个概念φ(n,m),并对某些低阶平面图求出了φ(n,m)的值.最后给出了φ(n,m)的上下界.     

图中的度序列

给出了一个非减的非负整数序列是某个图的度序列的一个新刻划.     

实现同一度序列的图的最大团数

图G中最大完全子图的阶数称为G的团效．ω(π)和γ(π)分别表示实现度序列π=(d_1,d_2,…,d_n)的图的最大团数和最小团数．Erds,Jacobson和Lehel开始考虑确定具有相同度序列π的图的可能的团数问题．他们证明了对于充分大的n,有ω(π)-γ(π)-n一2n~(2/3)．在本文中,我们首先估计了一类特殊可图序列的ω(π)之值,其次我们建立了一个估计任意可图序列π的ω(π)之值的算法．     

一类无标度随机图的度序列

本文从-个新的角度对-类随机图的度序列进行了分析.证明了此模型度分布的存在性,得到了网络规模比较大的情况下度为七的节点所占比例数的表达式.此外,我们还将模型扩展到每个时间步增加边数为随机变量的情形,得到了类似的结论.     

门槛图与度极大图

证明了门槛图与度极大图是一类图的两种不同说法,同时用图的对角限制极左矩阵刻画这一类图的结构。     

图的度序列不等式

用代数的方法证明了有关图度序列的几个不等式，并且得到了其相应的极图。     

给定度序列图的覆盖成本和反向覆盖成本的研究

具有n个顶点且度序列为(m,2,…,2,1,…,1)(1的重数为m)的连通图不止一个(这些图均为树),而每个树对应唯一一个段序列(l1,l2,…,lm).通过对任意一树移动最长段的悬挂点到最短段悬挂点的方式得到另一树,比较前后两树的覆盖成本和反向覆盖成本,给出了具有最小覆盖成本和反向覆盖成本的极树,并且进一步给出了取得...     

Fitting Height and Character Degree Graphs

Given a group G, Γ(G) is the graph whose vertices are the primes that divide the degree of some irreducible character and two vertices p and q are joined by an edge if pq divides the degree of some irreducible character of G. By a definition of Lewis, a graph Γ has bounded Fitting height if the Fitting height of any solvable group G with Γ(G)=Γ is bounded (in terms of Γ). In this note, we prove that there exists a universal constant C such that if Γ has bounded Fitting height and Γ(G)=Γ then h(G)≤C. This solves a problem raised by Lewis. Research supported by the Spanish Ministerio de Educación y Ciencia, MTM2004-06067-C02-01 and MTM2004-04665, the FEDER and Programa Ramón y Cajal.     

半无爪可迹图的度和条件

可迹图即为一个含有Hamilton路的图.令$N[v]=N(v)\cup\{v\}$, $J(u,v)=\{w\in N(u)\cap N(v):N(w)\subseteq N[u]\cup N[v]\}$.若图中任意距离为2的两点$u,v$满足$J(u,v)\neq \emptyset$,则称该图为半无爪图.令$\sigma_{k}(G)=\min\{\sum_{v\in S}d(v):S$为$G$中含有$k$个点的独立集\},其中$d(v)$表示图$G$中顶点$v$的度.本论文证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{3}(G)\geq {n-2}$,则图$G$为可迹图; 文中给出一个图例,说明上述结果中的界是下确界; 此外,我们证明了若图$G$为一个阶数为$n$的连通半无爪图,且$\sigma_{2}(G)\geq \frac{2({n-2})}{3}$,则该图为可迹图.