拟阵基图的连通性

设 E 是有限元素的集合,M 是 E 上的拟阵,B 是M 的基集,记 M=(E,B).对任意的S_1、S_2■E,令 S_1-S_2={e|e∈S_1,e■S_2},S_1+S_2={e|e∈S_1或 e∈S_2},若 S={e},则简记为 S=e.图 G 的顶点及边集合分别记为 V(G)、E(G).拟阵 M 的基图 G=B(M)使 V(G)={b|b∈B},对任意的 b、b′∈V(G),bb′∈E(G)当且仅当|b-b′|-1.拟阵的基图是图的树图概念的推广,它在实际中有重要应用.文献[1]证明了:任意一个拟阵的基图如果至少     

极小k边连通图的一个极值问题

本文只讨论单纯图。所有符号的意义均同于[2]。依照[1]给出定义 如图 G=(V,E)具有性质:λ(G)=k,而对(?)e∈E 均有λ(G-e)=k-1,则称 G 为极小 k 边连通图。设已给图 G=(V,E),如果 A,B(?)V,且 A∩B=φ,则记[A,B]={xy↓x∈A,y∈B,xy∈E}。如果 S(?)E,|S|=k,且 G-S=G_1 U G_2 V(G_1)∩V(G_2)=φ,V(G_1)≠φ,     

关于Simon和Murty猜想的证明

我们沿用书[1]中的记号和术语。设G=(V,E)是简单有限无向图,其中V=V(G),E=E(G)分别是G的顶点集合和棱集合。v(G)=|V(G)|,ε(G)=|E(G)|。设x,y∈V(G),x和y之间的距离d_G(x,y)定义为G中最短(x,y)路(path)的长度;如果x和y在G中不连通,则定义d_G(x,y)=∞。G的直径diam(G)定义为G中最大的距离,即     

完全图全符号控制数的较小上界和下确界

设图G=G(V,E),令函数f∶V∪E→{-1,1},f的权w(f)=∑x∈V∪Ef[x],对V∪E中任一元素,定义f[x]=∑y∈NT[x]f(y),这里NT[x]表示V∪E中x及其关联边、邻点的集合.图G的全符号控制函数为f∶V∪E→{-1,1},满足对所有的x∈V∪E有f[x]1,图G的全符号控制数γT(G)就是图G上全符号控制数的最小权,称其f为图G的γT-函数.本文得到了完全图全符号控制数的一个较小上界和下确界.     

对于X-join不可分解的无三角形的图

本文中的图都是有限简单图.仅含一个点的图叫作平凡图,不含边的图叫作空图.V(G)与 E(G)分别表示图 G 的点的集合与边的集合.有时以 G 代替 V(G),以 x∈G代替 x∈V(G).对 x∈G,N_G(x)={y∈G|xy∈E(G)}叫作 x 的邻域.下面的概念是 Sabidussi 引入的:令{G_x|x∈X}是图的一个族,指标取自另一个图 X.令#表示 X 中的邻接关系,⊥_x表示 G_x 中的邻接关系,则这一族图的 X-join 是指图 G,G=(?)(G_x×{x}),且 G 中的邻接关系⊥定义为:对 G 中任两个点(a,r)与(b,s),(a,r)⊥(b,s)当且仅当 r#s 或r=s 且 a⊥_rb.     

有向路和有向圈的控制集数

1引言设G=(V,E)为无向图．子集D (?)V(G)是无向图G的控制集,如果对于任意的y,∈V(G)-D,都存在x∈D,使xy∈E(G)．G的控制集D是G的分裂控制集,如果G中由V(G)-D导出的子图G〈V(G)-D〉是不连通的．G的一个控制集D是G的一个强(弱)控制集,若dG(x)≥d_G(y)(d_G(x)≤d_G(y)),其中d_G(x)表示G中与点x关联的边数．对于有向图H=(V,A),子集D(?)V(H)称为H的控制集,如果对于任意的y∈     

不含三角形的图的λ3-最优性的充分条件

设G=(V,E)是一个连通图,边集S(?)E是一个3-限制性边割,如果G-S是不连通的并且G-S的每个分支至少有三个点.图G的3-限制性边连通度λ_3(G)是G中最小的一个3-限制性边割的基数.图G是λ_3(G)连通的,如果3-限制性边割存在.G是λ_3-最优的,如果λ_3(G)=ξ_3(G),其中ξ_3(G)=min{|[U,(?)]|:U(?)V,|U|=3 and G[U]是连通的).G[U]表示V的子集U的导出子图,(?)=V\U表示U的补.[U,(?)]是一条边的一个端点在U中另一个端点在(?)中的边的集合.本文给出了不含三角形的图是λ_3-最优的一些充分条件.     

The fractional metric dimension of permutation graphs

Let G =(V(G), E(G)) be a graph with vertex set V(G) and edge set E(G). For two distinct vertices x and y of a graph G, let RG{x, y} denote the set of vertices z such that the distance from x to z is not equa l to the distance from y to z in G. For a function g defined on V(G) and for U■V(G), let g(U) =∑s∈Ug(s). A real-valued function g : V(G) → [0, 1] is a resolving function of G if g(RG{x, y}) ≥ 1 for any two distinct vertices x, y ∈ V(G). The fractional metric dimension dimf(G)of a graph G is min{g(V(G)) : g is a resolving function of G}. Let G1 and G2 be disjoint copies of a graph G, and let σ : V(G1) → V(G2) be a bijection. Then, a permutation graph Gσ =(V, E) has the vertex set V = V(G1) ∪ V(G2) and the edge set E = E(G1) ∪ E(G2) ∪ {uv | v = σ(u)}. First,we determine dimf(T) for any tree T. We show that 1 dimf(Gσ) ≤1/2(|V(G)| + |S(G)|) for any connected graph G of order at least 3, where S(G) denotes the set of support vertices of G. We also show that, for any ε 0, there exists a permutation graph Gσ such that dimf(Gσ)- 1 ε. We give examples showing that neither is there a function h1 such that dimf(G) h1(dimf(Gσ)) for all pairs(G, σ), nor is there a function h2 such that h2(dimf(G)) dimf(Gσ) for all pairs(G, σ). Furthermore,we investigate dimf(Gσ) when G is a complete k-partite graph or a cycle.     

n-double图的连通性

设Gl=(V1,E1),G2=(V2,E2)是两个连通图,直积(direct product)(也称为Kronecker product,tensor product和cross product) G1(×)G2的点集为V(G1(×)G2)=V(G1)(×)V(G2),边集为E(G1(×)G2)={(u1,v1)(u2,v2)∶ulu2∈E(G1),vlv2∈E(G2)}.简单图G的n-double图Dn[G]=G(×)Tn,其中n个点的全关系图Tn是完全图Kn在每个点加上一个自环得到的图.在本文中,我们研究了Dn[G]的(边)连通性,超(边)连通性.     

二分(0,mf-m+1)-图的正交(0,f)-因子分解

设G=(X,Y,E(G))是一个二分图,分别用V(G)=XUY和E(G)表示G的顶点集和边集.设f是定义在V(G)上的整数值函数且对(A)x∈V(G)有f(x)≥k.设H_1,H_2,…,H_k是G的k个顶点不相交的子图,且|E(H_i)|=m,1≤i≤k.本文证明了每个二分(0,mf-m+1)-图G有一个(0,f)-因子分解正交于Hi(i=1,2,…,k).