pqr阶Cayley图的符号星控制数

根据文献(徐保根.图的控制与染色理论.华中科技大学出版社,2013.)中图的符号星控制数的概念,当群Γ的换位子群珚Γ阶数为qr时,确定了pqr(2相似文献   

pqr阶Cayley图的反符号星控制数

当群Γ的换位子群Γ的阶数为qr时,根据图的反符号星控制数的概念,确定了pqr阶群Γ上Cayley图X(Γ,M)的反符号星控制数γrss(X(Γ,M)),其中2pqr,且p,q,r为互异的素数,M表示群Γ的极小生成集.     

pq阶Cayley图的符号星控制数

设G=(V,E)是一个没有孤立顶点的图,如果一个函数f:E→{-1,1},满足f(E(v))≥1,v∈V(G),则称f为图G的一个符号星控制函数.图G的符号星控制数定义为:γss(G)=min{f(E)|f为G的反符号星控制函数},论文确定了pq(2pq,且p、q为互异的素数)阶群Q上Cayley图X(Q,M)的符号星控制数γss(X(Q,M))=(p-1)q+1,M表示群Q的极小生成集.     

Hamilton二部图的一个充分条件

证明了当设G=(X,Y;E)是连通二部图,｜X｜=｜Y｜=n!5,且δ(G)≥2,若NC2≥n-1,则G是Hamilton图。     

二部置换图的无圈控制集算法

设G=(V,E)为简单无向图,S V称为G的无圈控制集,如果S控制G并且导出子图〈S〉不含有圈.该文证明了二部置换图的无圈控制数等于其控制数(γa(G)=γ(G)),利用此结论证明了无圈控制集问题在二部置换图上具有线性时间求解算法.     

部分射影平面上的完全弧

射影平面PG(r,q)是一种关联关系,其关联图X(I)是二部图,射影平面上的完全弧可以由它的关联图来刻画.以关联图的形式,对r=2,q=2,4,5 给出了射影平面PG(2,q)部分完全弧的刻画.     

关于图的符号边全控制

设γ’st(G)表示图G的符号边全控制数,给出了一般图G和超立方体的符号边全控制数的一个下界和一个上界,计算了等完全二部图的符号边全控制数的精确值。     

几类图的强符号控制数

本文对几类特殊图的强符号控制函数及强符号控制数进行了研究,给出了完全图、完全二部图、路及圈的强符号控制数.     

Erd(o)s和Rousseau的一个图论计数引理推广

在Erdos和Rousseau关于给定边数的图中所含子图为二部图Kn,n的一个计数定理的基础上,给出了m-部图情形的结论,它在m=2时比已有结论有些许改进.设自然数n≥2,证明了一个含有q条边的m-部图中至多可以诱导出A(m,n,q)个完全m一部图Km(n)作为子图,其中A(m,n,q)=eq-(m-1)(m-1)!n(e2q-n2)mn/2(2m-2-m)(m-1)n/2.     

关于一类(g,f)-2-覆盖图的研究

一个图G称为(g,f)-2-覆盖图,如果G的任何两条边都属于它的一个(g,f)-因子,得到了如下结论:(1)当g≤f时,一个二部图是(g,f)-2-覆盖图的一个充分必要条件;(2)当f(X)=f(Y)时,一个二部图是f-2-覆盖图的一个充分必要条件及其简单判别准则.     

Minus domination number in cubic graph

An upper bound is established on the parameter Γ -(G) for a cubic graph G and two infinite families of 3-connected graphs G k, G * k are constructed to show that the bound is sharp and, moreover, the difference Γ -(G * k)-γ s(G * k) can be arbitrarily large, where Г -(G * k) and γ s(G * k) are the upper minus domination and signed domination numbers of G * k, respectively. Thus two open problems are solved.     

关于图的控制数Vizing's定理的推广

对任意图G,设G的阶为n,边数为q,最大度为Δ,·5x」表示不大于x的最大整数,证明了G的控制数γ满足不等式q≤·5[n-γ)(n-γ 2)-Δ(2n-2γ-3Δ 2)]/ 2」,而且也刻画了该不等式的极图特征,从而推广了Vizing's定理.     

关于图的Fractional控制数

研究了图的 Fractional 控制问题,主要给出了关于联图的 Fractional 控制数的1个上界,由此确定了几类特殊联图的 Fractional 控制数,并推广了部分已知的结果。     

强乘积图与字典乘积图的控制数

证明了:1)图G和H的强乘积图GH的控制数γ(GH)≤γ(G)γ(H),并举例说明此上界是可以达到的;2)若γ(H)=1,则G与H的字典乘积图的控制数γ(G H)=γ(G);若G不含孤立点并且γ(H)≥2,则γ(G H)=γt(G),其中γt表示图的全控制数.     

关于点赋权图的赋权控制数的一个上界

点赋权图Gw=（V,E,W）是指对简单图G的顶点集作一个赋权函数W：V→R^＋。在图G所有的控制集D V（G）（V（G）／D中的任意顶点v都与D中的点关联）中最小的权和W（D）称为图Gw的赋权控制数。记作γw（Gw）。证明了对基数为N,平均权为W^-的图Gw,其赋权控制数γw（Gw）≤Nw^-1δ＋1^——1＋1n（δ＋1）。     

广义Petersen图P(n,1)和P(n,2)的意大利控制数

在图G=（V, E）中,f为从顶点集合V到｛0,1,2｝的映射,如果满足所有 f（v）=0的顶点v其邻域中至少有一个被赋值为2的顶点或者至少有两个被赋值为1的顶点,则 f 称为图G的意大利控制函数。图G中所有顶点的函数值之和为f 的权重。权重的最小值为图G的意大利控制数。确定图的意大利控制数是NP （non?deterministic polynomial） 困难的。通过构造可递推的意大利控制函数,计算出广义Petersen图P（n,1）和P（n,2）意大利控制数的上界。利用袋装法和控制代价函数法分别证明出P（n,1）和P（n,2）意大利控制数的下界。最终确定了P（n,1）和P（n,2）意大利控制数的精确值。     

独立控制双临界图

图G称为独立控制双临界的,如果去掉图中任何两点都使得独立控制数降低。首先讨论了一些特殊图类是独立控制双临界的,然后研究了独立控制双临界图的性质, 最后给出了从较小的独立控制双临界图构造一个独立控制双临界图的方法。     

控制圆点临界图的若干性质

对于图G,如果收缩任意一条边,它的控制数下降,则称图G是圆点临界图.如果粘贴图G中任意两个顶点,它的控制数下降,则称图G是全圆点临界图.证明了对于k-正则图,当k为奇数时不存在2-全圆点临界图;当k为偶数时当且仅当此图为k+2阶图时其为2-全圆点临界图.还对是否存在不含临界点的k-全圆点临界图(k≥4)进行了研究,并得出结论:存在不含临界点的4-全圆点临界图和5-全圆点临界图.     

一些卡方积图的符号星控制数

设G=(V,E)是一个没有孤立顶点的图,如果一个函数f:E→{+1,-1},对一切v∈V(G)满足∑e∈E(v)f(e)≥1成立,则称f为图G的一个符号星控制函数。图G的符号星控制数定义为γ’ss(G)=min{∑e∈E(v)f(e)∣f为G的符号星控制函数}。在图的符号星控制概念的基础上,确定了两类特殊图的符号星控制数。     

图的弱罗马控制

图的弱罗马控制数是图的弱罗马控制函数的最小权,记为γr(G).用逻辑推理和逐步分析法,刻画了弱罗马控制数等于最小控制数加1的图(即γr(G)=γ(G)+1)的特征.