蕴含K4＋P2-可图序列的刻划

对于给定的图H,若存在可图序列π的一个实现包含H作为子图,则称π为蕴含H-可图的．Gould等人考虑了下述极值问题的变形：确定最小的偶整数σ（H,n）,使得每个满足σ（π）≥σ（H,n）的n项可图序列π=（d1,d2,…,dn）是蕴含H-可图的,其中σ（π）=∑di．本文刻划了蕴含K4＋P2-可图序列,其中K4＋P2是向致的一个顶点添加两条悬挂边后构成的简单图．这一刻划导出σ（K4＋P2,n）的值．     

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

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

蕴含W6-可图序列

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

蕴含W_6-可图序列

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

γ-可图序列与γ-完全子图

一个r-图是一个无环的无向图,其中任何两个顶点之间至多被r条边连接.一个m+1个顶点的r-完全图,记为K_(m+1)^((r)),是一个m+1个顶点的r-图,其中任何两个顶点之间恰好被r条边连接.一个非增的非负整数序列π=(d_1,d_2,…,d_n)称为是r-可图的如果它是某个n个顶点的r-图的度序列.一个r-可图序列π称为是蕴含(强迫)K_(m+1)((r)),是一个m+1个顶点的r-图,其中任何两个顶点之间恰好被r条边连接.一个非增的非负整数序列π=(d_1,d_2,…,d_n)称为是r-可图的如果它是某个n个顶点的r-图的度序列.一个r-可图序列π称为是蕴含(强迫)K_(m+1)^((r))可图的如果π有一个实现包含K_(m+1)((r))可图的如果π有一个实现包含K_(m+1)^((r))作为子图(π的每一个实现包含K_(m+1)((r))作为子图(π的每一个实现包含K_(m+1)^((r))作为子图).设σ(K_(m+1)((r))作为子图).设σ(K_(m+1)^((r)),n)(τ(K_(m+1)((r)),n)(τ(K_(m+1)^((r)),n))表示最小的偶整数t,使得每一个r-可图序列π=(d_1,d_2,…,d_n)具有∑_(i=1)((r)),n))表示最小的偶整数t,使得每一个r-可图序列π=(d_1,d_2,…,d_n)具有∑_(i=1)ⁿ d_i≥t是蕴含(强迫)K_(m+1)n d_i≥t是蕴含(强迫)K_(m+1)^((r))-可图的.易见,σ(K_(m+1)((r))-可图的.易见,σ(K_(m+1)^((r)),n)是Erds等人的一个猜想从1-图到r-图的扩充且τ(K_(m+1)((r)),n)是Erds等人的一个猜想从1-图到r-图的扩充且τ(K_(m+1)^((r)),n)是经典Turan定理从1-图到r-图的扩充.本文给出了蕴含K_(m+1)((r)),n)是经典Turan定理从1-图到r-图的扩充.本文给出了蕴含K_(m+1)^((r))的r-可图序列的两个简单充分条件.此两个条件包含了Yin和Li在[Discrete Math.,2005,301:218-227]中的两个主要结果和当n≥max{m((r))的r-可图序列的两个简单充分条件.此两个条件包含了Yin和Li在[Discrete Math.,2005,301:218-227]中的两个主要结果和当n≥max{m²+3m+1-[(m2+3m+1-[(m²+m)/r],2m+1+[m/r]]}时,σ(K_(m+1)2+m)/r],2m+1+[m/r]]}时,σ(K_(m+1)^((r)),n)之值.此外,我们还确定了当n≥m+1时,τ(K_(m+1)((r)),n)之值.此外,我们还确定了当n≥m+1时,τ(K_(m+1)^((r)),n)之值.     

图的度序列

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

一类新的泛圈图

本文所说的图都是简单无向图。未定义的术语和记号参见[2]。设 G=(V,E)的 n 阶图(n≥3),若 G 中含有 Hamilton 圈,则称 G 是 H-图。若G 中含有从3到 n 的所有长度的圈,则称 G 为泛圈图。如下两个定理是众所周知的。定理1 (Ore,1960)。若在 n 阶图 G 中,有uv(?)E(G)(?)d(u) d(v)≥n,则 G 是 H-图。     

给定P3的无桥图的定向直径

设G是一个无向多重图,G的定向直径是指G的所有强连通定向中直径的最小值.Dankelmann,Guo,Surmacs [J.Graph Theory,2018,88:5-17]证明了n阶无桥图G的定向直径至多为n-Δ+3,这里Δ是G的最大度.设H是G的一个生成子图,定义■,利用上述结论他们还证明了,给定边e的无桥图G的定向直径至多为n-|N_G(e)|+5,以及给定无桥子图H的无桥图G的定向直径至多为n-|N_G(H)|+3.设P₃=uvw是G的一条长为2的路.易见P3包含两条边且这两条边均是P3的桥.本文利用将一条路收缩为一点的方法证明了给定P3的无桥图G的定向直径的上界为n-|N_G(P₃)|+5.特别地,若P3在一个4圈上或P3不在一个圈上但uv,vw分别在一个3圈上,定向直径至多为n-|N_G(P₃)|+4.最后举例说明了上述上界是紧的.     

关于简单MCD图

设G是阶为n的简单图，若G中没有两个等长圈且具有最大可能的边数，则称G为简单MCD图。本文通过引进路分解概念给出了两个关于图中圈数的结果并应用它们证明了下述定理：若G是简单MCD图，则G不是2连通可平面图且对所有整数n，除七个例外，G不是阶为n的含有同胚于K4的2连通图。     

汉米尔顿图泛圈性的奥尔型条件

本文所说的图是简单图,未定义的术语见[1,2].n 阶图 G,n≥3,若有长为 n 的圈,则说 G 是汉米尔顿图;若对每个 k,3≤k≤n,G 含有长为 k 的圈,则说 G 是泛圈图.定理1.在 n 阶图 G 中,若对任何点对 x,y∈V(G),xy(?)E(G),都有 d(x)+d(y)≥n,则 G 是汉米尔顿图.     

可图序列偏序集的极小元

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

3-连通3-正则图中的可序子集

图G的k元点集X={x1,x2,…,xk}被称为G的k-可序子集,如果X的任意排列都按序排在G的某个圈上.称G是k-可序图,如果G的每一个k元子集都是G的k-可序子集.称G为k-可序Hamilton图,如果X的任意排列都位于G的Hamilton圈上.研究了3-连通3-正则图的可序子集的存在性问题.     

三度边正则图的三个无限族

图X称为边正则图，若X的自同构群Aut(X)在X的边集上的作用是正则的．本文考察了三度边正则图与四度Cayley图的关系，给出了一个由四度Cayley图构造三度边正则图的方法，并且构造了边正则图的三个无限族．     

On potentially <Emphasis Type="Italic">H</Emphasis>-graphic sequences

For given a graph H, a graphic sequence π = (d ₁, d ₂,..., d _n) is said to be potentially H-graphic if there is a realization of π containing H as a subgraph. In this paper, we characterize the potentially (K ₅ − e)-positive graphic sequences and give two simple necessary and sufficient conditions for a positive graphic sequence π to be potentially K ₅-graphic, where K _r is a complete graph on r vertices and K _r-e is a graph obtained from K _r by deleting one edge. Moreover, we also give a simple necessary and sufficient condition for a positive graphic sequence π to be potentially K ₆-graphic. Project supported by National Natural Science Foundation of China (No. 10401010).     

Spectral characterization of line graphs of starlike trees

Two graphs are said to be A-cospectral if they have the same adjacency spectrum. A graph G is said to be determined by its adjacency spectrum if there is no other non-isomorphic graph A-cospectral with G. A tree is called starlike if it has exactly one vertex of degree greater than 2. In this article, we prove that the line graphs of starlike trees with maximum degree at least 12 are determined by their adjacency spectra.     

ON CONNECTED FACTORS IN K_(1,3)-FREE GRAPHS

1.IntroductionWeconsiderfinitesimplegraphs,andfollowBondyandMurtyl'lforgeneralterminologyandnotation.LetG=(V(G),E(G))beagraphwithavertexsetV(G)andanedgesetE(G).ForavertexvEV(G),N(v,G)denotesthesetofneighborsofvinG,anddG(v)=IN(v,G)l.Foravertexsubset(resp.subgraph)HofG,G--HdenotesthesubgraphofGobtainedfromGbydeletingthevenicesinHtogetherwiththeedgesincidelltwiththem.IfAisanedgesubsetofGandHasubgraphofG,thenH AdenotesthesubgraphofGobtainedfromHbyaddingtheedgesinAtogetherwiththeven…     

Homomorphism bounds for oriented planar graphs

If is a class of oriented graphs (directed graphs without opposite arcs), then an oriented graph is a homomorphism bound for if there is a homomorphism from each graph in to H. We find some necessary conditions for a graph to be a homomorphism bound for the class of oriented planar graphs and prove that such a graph must have maximum degree at least 16; thus there exists an oriented planar graph with oriented chromatic number at least 17. © 2007 Wiley Periodicals, Inc. J Graph Theory 55: 175–190, 2007     

环面图上的一个Lebesgue型定理及其在线性染色中的应用

设c是图G的一个顶点染色, 如果c的任意两个色类都导出一个最大度至多为2的无圈子图,则称c为G的一个无圈染色. 我们首先证明了环面图上的一个Lebesgue 型定理, 作为其应用证明了对任一个围长不小于5 的环面图G, 除非△(G) = 4 而且G有一个子图H使得H的每一个面都是与三个3度点和二个4度点相关的5度面, H一定是(「(△(G))/2」+ 4)- 线性列表可染色的. 这一结果推广和改进了一些已知结论.