关于图的反符号圈控制数

本文研究了图的反符号圈控制的问题.利用分类和反证的方法,获得了满足反符号圈控制数为负边数加4的连通图的刻画和完全二部分图的反符号圈控制数.     

图的强符号圈控制数

本文研究了图的强符号圈控制数γ′_(ssc)(G).利用最大独立集最大匹配等方法,刻画了满足γ′_(ssc)(G)=|E|-2的所有连通图,给出了γ′_(ssc)(G)的一个下界,求出了两类特殊图的强符号圈控制数.     

双圈图的零度与其匹配数之间的关系

Let G be a graph with n(G) vertices and m(G) be its matching number.The nullity of G,denoted by η(G),is the multiplicity of the eigenvalue zero of adjacency matrix of G.It is well known that if G is a tree,then η(G) = n(G)-2m(G).Guo et al.[Jiming GUO,Weigen YAN,Yeongnan YEH.On the nullity and the matching number of unicyclic graphs.Linear Alg.Appl.,2009,431:1293 1301]proved that if G is a unicyclic graph,then η(G)equals n(G)-2m(G)-1,n(G)-2m(G),or n(G)-2m(G) +2.In this paper,we prove that if G is a bicyclic graph,then η(G) equals n(G)-2m(G),n(G)-2m(G)±1,n(G)-2m(G)±2or n(G)-2m(G) + 4.We also give a characterization of these six types of bicyclic graphs corresponding to each nullity.     

简单图圈基长度的最大值

图的圈基是图的一个重要结构,一个圈基的长度是该圈基中所有圈的长度之和,本讲座了简单图的圈基长度的最大值,得到了如下结果：设基圈数为k,顶点数为n的简单图的圈基长度最大值为C^*,i)若k≥4且n ≥k 2时,C^*-kn;Ⅱ）若k=2,3,则对任意n≥4,C^*=kn-1,Ⅲ）若n(n≥5）为奇数,则对k(k≥4）的所有可能值,C^*=kn。     

三圈图的无符号拉普拉斯谱半径

假设图G的点集是V(G)={v_1,v_2,…,v_n},用d_(v_i)(G)表示图G中点v_i的度,令A(G)表示G的邻接矩阵,D(G)是对角线上元素等于d_(v_i)(G)的n×n对角矩阵,Q(G)=D(G)+A(G)是G的无符号拉普拉斯矩阵,Q(G)的最大特征值是G的无符号拉普拉斯谱半径.现确定了所有点数为n的三圈图中无符号拉普拉斯谱半径最大的图的结构.     

几类图的符号控制

设G=(V,E)是一个图,一个函数f:V→{-1,+1}如果满足Σv∈N[υ]f(ν)≥1对于每个点u∈V成立,则称f为图G的一个符号控制函数,图G的符号控制数γs(G)定义为γs(G)=min{Σv∈vf(v)|f为图G的符号控制函数},类似地,可定义图G的上符号控制数Γs(G).研究了几类特殊图的符号控制问题,获得了完全l等部图和乘积图P_3×P_n的符号控制数,并确定了P_2×P_n和P_3×P_n的上符号控制数.     

关于图的符号控制数的下界

图的符号控制数的研究有许多应用背景，但图的符号控制数的计算是NP完全问题，因而确定其上下界有重大意义。本文在[5]的基础上，引进了新参数δ^*(G)，全面改进了[5]所给出的符号控制数的下界，并给出了一些可达下界的图。     

两类图的符号控制数

图G的符号控制数γs(G)有着许多重要的应用背景,因而确定其精确值有重要意义.Cm表示m个顶点的圈,n-Cm和n·Cm分别表示恰有一条公共边或一个公共顶点的n个Cm的拷贝.给出了n-Cm和n·Cm的符号控制数.     

图的符号边控制数

图的符号边控制数有着许多重要的应用背景.已知它的计算是NP-完全问题,因而确定其精确值有重要意义.本文确定了图F*n+1、H n和P*n的符号边控制数.     

符号图的符号线图的无零流

本文研究了符号图的符号线图的无零流问题.利用数学归纳法以及分析符号图结构等方法,获得了当符号图的底图为简单图且没有2度点时,其符号线图允许一个无零4-流的结果.特别地,如果符号图的底图为简单图且没有2度点和4度点,那么它的符号线图允许一个无零3-流.验证了对具有上述结构的符号图的符号线图,Bouchet 6-流猜想是成立的.同时我们研究了连通的符号圈的符号线图是否是流允许的.     

零度为$n-7$的双圈符号图

Let Γ be a signed graph and A(Γ) be the adjacency matrix of Γ. The nullity ofΓ is the multiplicity of eigenvalue zero in the spectrum of A(Γ). In this paper, the connected bicyclic signed graphs(including simple bicyclic graphs) of order n with nullity n-7 are completely characterized.     

基圈数为5的2-连通平图的构造

所有的2-连通平图可通过收缩2度点变换成无2度点的、基圈数不变的2-连通平图.本文给出了基圈数为5的、无2度点的所有2-连通平图.     

关于图的符号星控制数

设G=(V,E)是一个图,u∈V,则E(u)表示u点所关联的边集.一个函数f:E→{-1,1}如果满足■f(e)≥1对任意v∈V成立,则称f为图G的一个符号星控制函数,图G的符号星控制数定义为γ'_(ss)(G)=min{■f(e):f为图G的一个符号星控制函数}.给出了几类特殊图的符号星控制数,主要包含完全图,正则偶图和完全二部图.     

完全多部图的符号边控制数的界

$f: E(G)rightarrow{-1,1}$称为图$G =(V,E)$的一个符号边控制函数 (简称SEDF),如果$f[e]=f(N[e])=sum_{e''in N[e]}f(e'')geq1$对于图$G$的每条边$ein E$都成立. $w(f)=sum_{ein E}f(e)$称为函数$f$的权. $G$的符号边控制数$gamma_{s},''(G)$是指$G$的所有符号边控制函数的最小权.本文对完全多部图的符号边控制数进行研究.对于完全$r$-部图, 当$r$为偶数并且各部的顶点数相同的情况下,我们得到了这一参数的若干下界和上界.     

图的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符号边控制数.