3连通图的可去边数

设 e是 3连通图 G的一条边 ,如果 G- e是某个 3连通图的剖分 ,则称 e是 G的可去边 .本文给出了 3连通图的可去边数依赖于极大半轮的下界以及达到下界的极图 .     

C2(4,k) 中的强支撑可迹图

设2≤h≤3,l0,k≥0是整数,C_h(l,k)是由h-边连通简单图组成的集合,图G∈C_h(l,k)当且仅当对图G的任意一个二边割或三边割X,图G-X的每个分支都至少有︱V(G)-k︱/l个点.设e=u_1v_1和e'=u_2v_2是图G的两条边.若e≠e',G(e,e')是将图G中的边e=u_1v_1和e'=u_2v_2分别用路u_1v_ev_1和u_2v_e'v_2替换得到的图(其中,v_e,v_e'是不在V(G)中的两个新的点).若e=e',G(e,e')是将图G中的边e=u_1v_1用路u_1v_ev_1替换得到的图,也记作G(e).若对任意的e,e'∈E(G),G(e,e')都有支撑(v_e,v_e')迹,则称图G是强支撑可迹的.作者证明了,若图G∈C_2(4,k)且|V(G)|5k,则要么图G是强支撑可迹图,要么存在e,e'∈E(G),使得G(e,e')可以收缩成一个有限图类F中的图.当k=4时,F被完全确定了.     

关于几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m＜n)使对每个l∈{3,4,…,n} -{m},G恰有一个长为l的圈且不含长为m的圈,则称G是几乎唯一泛圈图,用(?)k表示具有n k条边和恰有1/2(k 1)(k 2)个圈的简单H图的集合,用(?)_k~*表示具有n k条边恰有2~k k个圈的简单外可平面H图的集合,本文确定了(?)_k和(?)_k~*中所有几乎唯一泛圈图,并证明这些图都是简单MCD图,本文还构造了50个含有同胚于K_4的子图的几乎唯一泛圈图,并提出了若干问题和猜想。     

3-连通3-正则图生成树外的可去边

G是3-连通图，e是G中的一条边．若G-e是3-连通图的一个剖分，则称e是3-连通图的可去边．否则，e是G中不可去边．本给出3-连通3-正则图中生成树外可去边的分布情况及数目．     

一类几乎唯一泛圈图

设G是阶为n的简单Hamilton图．若存在m(3(?)m相似文献   

零和Ramsey数R(C_3,Z_3)的下界——(3)

Bialostocki和Dierker给出了古典Ramaey定理下列有趣的推广:设G是一个有m条边的图,整数k≥2,且k|m,Z_k表示k阶循环群。定义R(G,Z_k)表示一个极小整数t,使得对K_t的边的任意Z_k—染色(即一个泛函C:E(K_t)→Z_k),K_t中都存在一个同构于G的子图具有下列性质 sum from e∈E(G) C(e)≡0(mod k)。本文证明R(C_3,Z_3)≥11。     

图的k符号边控制数

设G=(V,E)是一个图,一个函数f:E→{-1,+1},如果对于G中至少k条边e有sum from e'∈N[e]f(e')≥1成立,则称f为图G的一个k符号边控制函数.一个图的k符号边控制数定义为γ_(ks)^/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)/(G)=min{∑_(e∈E(G))f(e)|f为图G的一个k符号边控制函数}.主要给出了一个图G的k符号边控制数γ_(ks)^/(G)的若干新下限,并确定了路和圈的k符号边控制数.     

一类混合图的结构及其特征空间

主要讨论具有如下性质的一类连通混合图G:其所有非奇异圈恰有一条公共边,且除了该公共边的端点外,任意两个非奇异圈没有其它交点.本文给出了图G的结构性质,建立了其最小特征值λ1(G)(以及相对应的特征向量)与某个简单图的代数连通度(以及Fiedler向量)之间联系,并应用上述联系证明了λ1(■)≤α(G),其中G是由G通过对其所有无向边定向而获得,α(■)为■的代数连通度.     

点可迁图的限制边连通性

3限制边割是连通图的一个边割, 它将此图分离成阶不小于3的连通分支. 图G的最小3限制边割所含的边数称为此图的3限制边连通度, 记作λ\-3(G). 它以图G的3阶连通点导出 子图的余边界的最小基数ξ_3(G)为上界. 如果λ_3(G)=ξ_3(G), 则称图G是极大3限制边连通的 . 已知在某种程度上,3限制边连通度较大的网络有较好的可靠性. 作者在文中证明: 如果k正则连通点可迁图的 围长至少是5, 那么它是是极大3限制边连通的.     

极小2-连通图的一个性质

圣1.基本概念与记号 设口是一个图,我们分别用厂(G),E(‘)表示图‘的顶点及边集合,分别用‘-e及G+e表示从图召中删去边e及增加边e以速接G中不相邻两点所得的图,用G·e表示从口通过收缩边e所得到的图。若S二E(G),用G〔夕]表示‘的边导出子图。 若图‘是2一速通的,但任意的e任E(G),G一e不是2一速通的,则称图G是一个极小2一速通图〔“’。 由此定义易见极小2一速通图一定是一个简单图。 本文分别用 t(G),c(G)表示图G的支撑树及圈的数目,分别用te(G),t百(G)表示图‘中含边e及不合边e的支撑树数目,分别用c,(G),叮(‘)表示G中含边e及不含…     

图的距离无符号拉普拉斯谱半径的关于色数的下界

Let G be a connected graph on n vertices with chromatic number k, and let ρ(G)be the distance signless Laplacian spectral radius of G. We show that ρ(G) ≥ 2n + 2「n k」- 4,with equality if and only if G is a regular Tur′an graph.     

On Non-Essential Edges in 3-Connected Graphs

 An edge e in a simple 3-connected graph is deletable (simple-contractible) if the deletion G\e (contraction G/e) is both simple and 3-connected. Suppose a, b, and c are three non-negative integers. If there exists a simple 3-connected graph with exactly a edges which are deletable but not simple-contractible, exactly b edges which are simple-contractible but not deletable, and exactly c edges which are both deletable and simple-contractible, then we call the triple (a, b, c) realizable, and such a graph is said to be an (a, b, c)-graph. Tutte's Wheels Theorem says the only (0, 0, 0)-graphs are the wheels. In this paper, we characterize the (a, b, c) realizable triples for which at least one of a + b≤2, c=0, and c≥16 holds. Received: February 12, 1997 Revised: February 13, 1998     

最大度与最小度相差不超过2的图的平衡judicious划分

图G的顶点集V(G)的一个二部划分V_1和V_2叫做平衡二部划分,如果||V_1|-|V_2||≤1成立.Bollobas和Scott猜想:每一个有m条边且最小度不小于2的图,都存在一个平衡二部划分V_1,V_2,使得max{e(V_1),e(V_2)}≤m/3,此处e(V_i)表示两顶点都在V_i(i=1,2)中的边的条数.他们证明了这个猜想对正则图(即△(G)=δ(G))成立.颜娟和许宝刚证明了每个(k,k-1)-双正则图(即△(G)-δ(G)≤1)存在一个平衡二部划分V_1,V_2,使得每一顶点集的导出子图包含大约m/4条边.这里把该结论推广到最大度和最小度相差不超过2的图G.     

不含某些子图的k连通图中的k可收缩边

最近Ando等证明了在一个$k$($k\geq 5$ 是一个整数) 连通图 $G$ 中,如果 $\delta(G)\geq k+1$, 并且 $G$ 中既不含 $K^{-}_{5}$,也不含 $5K_{1}+P_{3}$, 则$G$ 中含有一条 $k$ 可收缩边.对此进行了推广,证明了在一个$k$连通图$G$中,如果 $\delta(G)\geq k+1$,并且 $G$ 中既不含$K_{2}+(\lfloor\frac{k-1}{2}\rfloor K_{1}\cup P_{3})$,也不含 $tK_{1}+P_{3}$ ($k,t$都是整数,且$t\geq 3$),则当 $k\geq 4t-7$ 时, $G$ 中含有一条 $k$ 可收缩边.     

图的上可嵌入性与独立顶点的新度和

Let G be a k(k ≤3)-edge connected simple graph with minimal degree ≥ 3,girth g,r=g12.For any independent set {a1,a2 , . . . , a 6/(4 k)} of G,if,then G is up-embeddable.     

关于一些图类的L(1,2)-边标号

For a graph G and two positive integers j and k, an m-L(j, k)-edge-labeling of G is an assignment on the edges to the set {0,..., m}, such that adjacent edges receive labels differing by at least j, and edges which are distance two apart receive labels differing by at least k. The λ′j,k-number of G is the minimum m of an m-L(j, k)-edge-labeling admitted by G.In this article, we study the L(1, 2)-edge-labeling for paths, cycles, complete graphs, complete multipartite graphs, infinite ?-regular trees and wheels.     

An Extension of the Win Theorem: Counting the Number of Maximum Independent Sets

Win proved a well-known result that the graph G of connectivity κ(G) withα(G) ≤κ(G) + k-1(k ≥ 2) has a spanning k-ended tree, i.e., a spanning tree with at most k leaves. In this paper, the authors extended the Win theorem in case when κ(G) = 1 to the following: Let G be a simple connected graph of order large enough such that α(G) ≤ k + 1(k ≥ 3) and such that the number of maximum independent sets of cardinality k + 1 is at most n-2k-2. Then G has a spanning k-ended tree.     

图的平面Turán数和平面anti-Ramsey数

在所有顶点数为$n$且不包含图$G$作为子图的平面图中,具有最多边数的图的边数称为图$G$的平面Turán数,记为$ex_{_\mathcal{P}}（n,G）$。给定正整数$n$以及平面图$H$,用$\mathcal{T}_n （H）$来表示所有顶点数为$n$且不包含$H$作为子图的平面三角剖分图所组成的图集合。设图集合$\mathcal{T}_n （H）$中的任意平面三角剖分图的任意$k$边染色都不包含彩虹子图$H$,则称满足上述条件的$k$的最大值为图$H$的平面anti-Ramsey数,记作$ar_{_\mathcal{P}}（n,H）$。两类问题的研究均始于2015年左右,至今已经引起了广泛关注。全面地综述两类问题的主要研究成果,以及一些公开问题。     

5连通图中的可去边

An edge e of a k-connected graph G is said to be a removable edge if G O e is still k-connected, where G e denotes the graph obtained from G by deleting e to get G - e, and for any end vertex of e with degree k - 1 in G- e, say x, delete x, and then add edges between any pair of non-adjacent vertices in NG-e （x）. The existence of removable edges of k-connected graphs and some properties of 3-connected and 4-connected graphs have been investigated [1, 11, 14, 15]. In the present paper, we investigate some properties of 5-connected graphs and study the distribution of removable edges on a cycle and a spanning tree in a 5- connected graph. Based on the properties, we proved that for a 5-connected graph G of order at least 10, if the edge-vertex-atom of G contains at least three vertices, then G has at least （3│G│ ＋ 2）/2 removable edges.     

树的L(3,2,1)-标号问题

An L(3,2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all non-negative integers(labels) such that |f(u)-f(v)|≥3 if d(u,v)=1,|f(u)-f(v)≥2 if d(u,v)=2 and |f(u)-f(v)|≥1 if d(u,v)=3.For a non-negative integer k,a k-L(3,2,1)-labeling is an L(3,2,1)-labeling such that no label is greater than k.The L(3,2,1)-labeling number of G,denoted by λ_(3,2,1)(G), is the smallest number k such that G has a k-L(3,2,1)-labeling.In this article,we characterize the L(3,2,1)-labeling numbers of trees with diameter at most 6.