de Bruijn图的(1,2)-步竞争图

设D=(V,A)是一个有向图.有向图D的(1,2)-步竞争图是关于V(D)的无向图,表示为C_(1,2)(D).若边{x,y}∈E(C_(1,2)(D)),当且仅当存在一个顶点z≠x,y,使得d_(D-y)(x,z)≤1且d_(D-x)(y,z)≤2或者d_(D-x)(y,z)≤1且d_(D-y)(x,z)≤2.在2000年,Cho等人给出了m-步竞争图的定义.主要研究了deBruijn图的(1,2)-步竞争图,并给出了deBruijn图中的弧为C_(1,2)(D)的边的一个刻画.     

正则多部竞赛图的控制图

设D=(vA)是一个有向图,x,y∈V(D),记O(x)是x控制的顶点的集合,如果O(x)∪O(y)∪{x,y}=V(D),则称x和y控制D.有向图D的控制图记为dom(D),它是—个无向图,顶点集是V(D),且对x,y∈V(D),xy是dom(D)的一条边当且仅当x和y控制D.1998年,Fisher等人首次提出控制图的概念,并完全刻画了竞赛图的控制图.本文研究正则多部竞赛图的控制图,并给出了—个无向图是某个正则多部竞赛图的控制图的一个刻画.     

正则多部竞赛图的竞争指数

设D是一个有向图,若存在无向图G满足:(1)G的顶点集与D的顶点集相同;(2)任取D中的两个顶点x,y,其在G中相邻当且仅当存在D中顶点z,使得D中包含一条从x到z的长为m的有向途径和一条从y到z的长为m的有向途径,则称G为D的m步竞争图,记为G=C~m(D).2004年,Cho和Kim首次提出竞争指数的概念.若对于某个正整数r和所有非负整数i,存在最小正整数q,使C~(q+i)(D)=C~(q+i+r)(D),则称整数q为D的竞争指数,记为cindex(D).2008年,Kim给出了竞赛图的竞争指数的上界.2009年,Akelbek和Kirkland给出了本原有向图的竞争指数.文中研究并计算了正则多部竞赛图的竞争指数.     

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

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∈     

关于加权距离正则图和立方图

令G=(V,E)是简单的连通k-正则图;w_1相似文献   

偶图中过给定独立边集的圈

这里考虑的一切图均为简单的,以V(G),E(G)分别表示图G的节点集和边集。设H是G的子图,x∈V(H),用d_H(x)表示H中与节点x相邻节点的个数。如果e=(x,y)∈E(H),x,y是e的端点,则让d_H(e)=d_H(x)+d_H(y)。设A、B是V(G)的两个节点不交的子集,用E(A:B)表示G中一端在A中另一端在B中边的个数。设M是G     

三路树P(m,n,t)是边幻图的证明(Ⅱ)

令简单图G=(V,E)是有p个顶点q条边的图.假设G的顶点和边由1,2,…,p+q所标号,且f:V ∪E→{1,2,…,p+q}是一个双射,如果对所有的边xy,f(x)+f(y)+f(xy)是常量,则称图G是边幻图(edge-magic).本文证明了三路树P(m,n,t)当n为偶数,t=n+2时也是边幻图.     

三路树P(m,n,t)是边幻图的证明(II)

令简单图G=(V,E)是有p个顶点q条边的图.假设G的顶点和边由1,2,…,p+q所标号,且f:V∪E→{1,2,…,p+q}是一个双射,如果对所有的边xy,f(x)+f(y)+f(xy)是常量,则称图G是边幻图(edge-magic).本文证明了三路树P(m,n,t)当n为偶数,t=n+2时也是边幻图.     

关于轮图优美标号的性质

设G=(V(G)),E(G))为p个顶点,q条边的连通简单图,以x和y为端点的边记作(x,y).定义1 称l为G的一个优美标号,如果l是一个单射:l:V(G)→{0,1,…,q}使得对所有边(x,y)∈E(G),由(?)(x,y)=|l(x)-l(y)|所定义的函数是一个—一对应.并称l(x)为顶点x的优美值.     

图的逆符号边控制数的上界

设G=(V,E)是一个图,对于图G的-个函数f:E→{-1,1},如果对任意e∈E(G),均有∑f(e')≤1,则称,为图G的一个逆符号边控制函数.图G的逆符号边控制数(～γ's)(G)=e'∈N[e]max{∑,(e)|f,为图G的一个逆符号边控制函数}.本文在定义了逆符号边控制数的基础上,得到了图e∈E的逆符号边控制数的几个上界.     

均衡二部图中含2k条指定边的k个独立圈及2-因子

得到了对于二部图G=(V_1,V_2;E),当|V_1|=|V_2|=n≥2k+1时的结果:对G中任意2k条独立边e_1,e_1~*,…,e_k,e_k~*,G中一定存在k个独立的4-圈C_1,C_2,…,C_k,使得对任意i∈{1,2,…,k}有{e_i,e_i~*}E(C_i).并在此基础上进一步证明了当|V_1|=|V_2|=n≥3k时若对任意两顶点x∈V_1,y∈V_2,都有d(x)+d(y)≥2n-k+1成立,则G有一个2-因子含有k+1个独立圈C_1,C_2,…,C_(k+1)使得对任意i∈{1,2,…,k}有{e_i,e_i~*}E(C_i)且|C_i|=4.     

图是超限制性边连通的充分条件

设G=（V,E）是连通图.边集S E是一个限制性边割,如果G-S是不连通的且G—S的每个分支至少有两个点.G的限制性连通度λ＇（G）是G的一个最小限制性边割的基数.G是λ＇-连通的,如果G存在限制性边割.G是λ＇-最优的,如果λ＇（G）=ζ（G）,其中ζ（G）是min{d（x）＋d（y）-2：xy是G的一条边}.进一步,如果每个最小的限制性边割都孤立一条边,则称G是超限制性边连通的或是超-λ＇.G的逆度R（G）=∑_（v∈V） 1/d（v）,其中d（v）是点v的度数.我们证明了G是λ＇-连通的且不含三角形,如果R（G）≤2＋1/ζ-ζ/（（2δ-2）（2δ-3））＋（n-2δ-ζ＋2）/（（n-2δ＋1）（n-2δ＋2））,则G是超-λ＇.     

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.     

有向P2-路图的结构性质

一个有向图D的有向Pk-路图Pk(D)是通过把D中的所有有向k长路作为点集;两点u= x1x2…xk+1,v=y1y2…yk+1之间有弧uv当xi=yi-1,i=2,3,…,k+1.明显地,当k=1时Pk(D)就是通常的有向线图L(D).在[1,2]中,P2-路图得到完整刻画.在[3]中,Broersma等人研究了有向...     

图的Augmented Zagreb 指数的界

Let G =(V, E) be a simple connected graph with n(n ≥ 3) vertices and m edges,with vertex degree sequence {d₁, d₂,..., d_n}. The augmented Zagreb index is defined as AZI =AZI(G)=∑ij∈E(didj/di+dj-2)³. Using the properties of inequality, we investigate the bounds of AZI for connected graphs, in particular unicyclic graphs in this paper, some useful conclusions are obtained.     

二分(mg,mf)-图中的(g,f)-因子

设G是一个二分图具有顶点集V（G）和边集E（G）。设g和f是定义在V（G）上的两个正整值函数使对任意的x∈V（G）有g(x)≤f(x)，G的一个（g,f）－因子H是G的一个生成子图满足g(x)≤dH(x)≤f(x）。若图G本身是一个（g,f）－因子，则称G是一个（g,f）－图。本文得到一个（mg,mf）－图具有特殊性质的（g,f）－因子的充分条件，从而推广了文献[6]中的一个结果。     

关于分数可消去图的若干结果

令G=(V(G),E(G))是一个图,并令9和f是两个定义在V(G)上的整数值函数且对所有的x∈V(G)有g(x)≤f(z)成立．若对G的每一条边e都存在G的一个分数(g,f)-因子G_h使得h(e)=0,其中h是G_h的示性函数,则称G是一个分数(g,f)-消去图,若在G中删去E′■E(G),|E′|=k后,所得图有分数完美匹配,则称G是分数k-边-可消去的。本文给出了图是1-可消去,2-可消去和k-边-可消去的与韧度和孤立韧度相关的充分条件。证明了这些结果在一定意义上是最好可能的．     

二分(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).     

有向图n·■_m的优美性

给定有向图D(V,E),如果存在一个单射f:V(D)→{0,1,…,|E|}使得对于每条有向边(u,v),诱导函数f′:E(D)→{1,2,…,|E|}是一个双射函数,其中,f′(u,v)=[f(v)-f(u)](mod(|E|+1)),则f称为有向图D(V,E)的优美标号,f′称为有向图D(V,E)的诱导的边的优美标号.本文讨论了有向图n.■m的优美性,并且证明了当m=23且n为偶数时,n.■m是优美有向图.     

单圈图的最大特征值的上界的改进

Let G（V, E） be a unicyclic graph, Cm be a cycle of length m and Cm G, and ui ∈ V（Cm）. The G - E（Cm） are m trees, denoted by Ti, i = 1, 2,..., m. For i = 1, 2,..., m, let eui be the excentricity of ui in Ti and ec = max{eui ： i = 1, 2 , m}. Let κ = ec＋1. Forj = 1,2,...,k- 1, let δij = max{dv ： dist（v, ui） = j,v ∈ Ti}, δj = max{δij ： i = 1, 2,..., m}, δ0 = max{dui ： ui ∈ V（Cm）}. Then λ1（G）≤max{max 2≤j≤k-2 （√δj-1-1＋√δj-1）,2＋√δ0-2,√δ0-2＋√δ1-1}. If G ≌ Cn, then the equality holds, where λ1 （G） is the largest eigenvalue of the adjacency matrix of G.