序列平行图的最小填充

起源于稀疏矩阵计算和其它应用领域的一个图G的最小填充问题就是在G中寻找一个边数| F |最小的添加边集F,使得G+F是弦图.这里最小值| F |称为图G的填充数,表示为f(G).对一般图来说,这个问题是NP-困难问题.一些特殊图类的最小填充问题已被研究.本文给出了序列平行图G的最小填充数的具体值.     

弦图的补图的最小填充

从图论观点讲,最小填充问题就是在一个图G中添加边集F,使得图G的母图G F是一个弦图而且所添边的边数| F|是最小的,其中最小值| F|称为图G的填充数,表示为f( G) .对一般图来说,最小填充问题是NP-困难的,但是对一些特殊图类来说,这个问题是在多项式时间内可解的.本文给出了弦图的补图-G的填充数f(-G) .     

谈谈线性图的平面嵌入

[1、2]中对线性图的平面嵌入问题给出了一个新的解法。同国外已有的解法比较,这个解法具有简捷、易算、理论性较强的长处。为了便于读者更好地掌握这个解法,我们在此将[1、2]中某些主要结果的论述改写一下。 所谓一个线性图,是由一些(闭)棱道构成的,其中任意两棱道至多在端点相交。一个需要解决的问题是:给了一个线性图G,问G可不可以画在平面R~2上而不增加新的交点?又,如果可以画的话,请给出一个画法。我们称这个问题为线性图的平面嵌入问题。 研究平面嵌入问题时,我们可以对线性图G做一些假设而不失一般性。首先我们假     

最小填充问题的可分解性

起源于稀疏矩阵计算和其它应用领域的图G的最小填充问题是在图G中寻求一个内含边数最小的边集F使得G F是弦图.这里最小值|F|称为图G的填充数,表示为f(G).作为NP-困难问题,该问题的降维性质已被研究,其中包括它的可分解性.基本的可分解定理是:如果图G的一个点割集S是一个团,则G经由S是可分解的.作为推广,如果S是一个"近似"团(即只有极少数边丢失的团),则G经由S是可分解的.本文首先给出基本分解定理的另外一个推广:如果S是G的一个极小点割集且G-S含有至少|S|个分支,则G经由S是可分解的;其次,给出了这个新推广定理的一些应用.     

图的（k，d）-着色问题的一个近似算法

本文讨论了图的(k,d)-着色问题的算法,并给出了一个由四层神经元组成的神经网络算法.当一个图的循环色数已知时(不妨设为k/d),可以利用该算法成功地求出这个图的一个可行(k,d)-着色方案;当一个图的循环色数未知时,可以利用该算法求出这个图的循环色数的近似值.     

幂零Fuzzy矩阵的一些结论及幂零度的求法

本文给出计算幂零Fuzzy矩阵的幂零度的两个办法,同时给出一个有有向Hamilton路的有向图的一个充分条件.     

具有小的负惯性指数的图（英文）

设G是有n个点的图,在G的所有特征根中,正特征根的个数和负特征根的个数分别称为图G的正惯性指数和负惯性指数,分别记为p(G)和n(G).这两个参数密切联系与图G的零度,而图的零度是具有重要化学应用的图参数,特别是对分子图,它已经被大量的研究,这篇文章的主要目的是刻画具有小的负惯性指数的图.利用图的点繁殖运算,刻画了具有n(G)≤2的所有图,也刻画了具有n(G)≤3的带有悬挂点的所有图.     

图的消去割宽问题

图搜索问题在组合最优化学科中是一个著名的NP-完全问题.现在我们给这个问题一个限制性条件：图中的边在一次性被搜索后立即堵塞,使得这些边在以后的图搜索过程中不再被搜索.该问题起源于流行病的预防、管道的保养和维护等领域. 在这个条件限制下,图搜索问题可以转化为图的消去割宽问题.本文主要研究了图的消去割宽的多项式时间算法、基本性质以及消去割宽和其它图论参数如树宽、路宽的关系,得到了一些特殊图类的消去割宽值.     

在WDM环网中疏导率为12的分插复用器数目最小化问题

在WDM网中的一个重要问题是使网络的费用最小化.我们的目的是最小化网络中ADM的个数.这个问题的模型是分拆一个完全图的边成一些子图,使每个子图至多有C条边(这里C是疏导率),并且这些子图的点数之和最小.本文对于给定的C,使用图论和设计理论的工具得到了一些求ADM个数(即A(C,N))的方法.也给出了当C=12并且WDM环网的点数N≡0,16(mod 24)时,问题的最优解(即A(C,N)=N(N-1)/4).     

二部图的单特征值

一个图的特征值通常指的是它的邻接矩阵的特征值,在图的所有特征值中,重数为1的特征值即所谓的单特征值具有特殊的重要性.确定一个图的单特征值是一个比较困难的问题,主要是没有一个通用的方法.1969年,Petersdorf和Sachs给出了点传递图单特征值的取值范围,但是对于具体的点传递图还需要根据图本身的特性来确定它的单特征值.给出一类正则二部图,它们是二面体群的凯莱图,这类图的单特征值中除了它的正、负度数之外还有0或者±1,而它们恰好是Petersdorf和Sachs所给出的单特征值范围内的中间取值.     

零维数等于1的单圈图

The nullity of a graph G is defined to be the multiplicity of the eigenvalue zero in its spectrum. In this paper we characterize the unicyclic graphs with nullity one in aspect of its graphical construction.     

混合图的Hermitian邻接矩阵的零维数

A mixed graph means a graph containing both oriented edges and undirected edges. The nullity of the Hermitian-adjacency matrix of a mixed graph G, denoted by ηH(G),is referred to as the multiplicity of the eigenvalue zero. In this paper, for a mixed unicyclic graph G with given order and matching number, we give a formula on ηH(G), which combines the cases of undirected and oriented unicyclic graphs and also corrects an error in Theorem 4.2 of [Xueliang LI, Guihai YU. The skew-rank of oriented graphs. Sci. Sin. Math., 2015, 45:93-104(in Chinese)]. In addition, we characterize all the n-vertex mixed graphs with nullity n-3, which are determined by the spectrum of their Hermitian-adjacency matrices.     

On the nullity of graphs with pendant trees

The nullity of a graph is defined as the multiplicity of the eigenvalue zero in the spectrum of the adjacency matrix of the graph. We investigate a class of graphs with pendant trees, and express the nullity of such graph in terms of that of its subgraphs. As an application of our results, we characterize unicyclic graphs with a given nullity.     

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

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.     

The maximum multiplicity of the largest k-th eigenvalue in a matrix whose graph is acyclic or unicyclic

Given a graph $G$ we are interested in studying the symmetric matrices associated to $G$ with a fixed number of negative eigenvalues. For this class of matrices we focus on the maximum possible nullity. For trees this parameter has already been studied and plenty of applications are known. In this work we derive a formula for the maximum nullity and completely describe its behavior as a function of the number of negative eigenvalues. In addition, we also carefully describe the matrices associated with trees that attain this maximum nullity. The analysis is then extended to the more general class of unicyclic graphs. Further our work is applied to re-describing all possible partial inertias associated with trees, and is employed to study an instance of the inverse eigenvalue problem for certain trees.     

单圈图的零度的一个注记

The number of zero eigenvalues in the spectrum of the graph G is called its nullity and is denoted by η(G).In this paper,we determine the all extremal unicyclic graphs achieving the fifth upper bound n-6 and the sixth upperbound n-7.     

A technique for computing the zero forcing number of a graph with a cut-vertex

The zero forcing number of a graph is the minimum size of a zero forcing set. This parameter is useful in the minimum rank/maximum nullity problem, as it gives an upper bound to the maximum nullity. Results for determining graphs with extreme zero forcing numbers, for determining the zero forcing number of graphs with a cut-vertex, and for determining the zero forcing number of unicyclic graphs are presented.     

On the nullity and the matching number of unicyclic graphs

Let G be a graph with n vertices and ν(G) be the matching number of G. Let η(G) denote the nullity of G (the multiplicity of the eigenvalue zero of G). It is well known that if G is a tree, then η(G)=n-2ν(G). Tan and Liu [X. Tan, B. Liu, On the nullity of unicyclic graphs, Linear Alg. Appl. 408 (2005) 212-220] proved that the nullity set of all unicyclic graphs with n vertices is {0,1,…,n-4} and characterized the unicyclic graphs with η(G)=n-4. In this paper, we characterize the unicyclic graphs with η(G)=n-5, and we prove that if G is a unicyclic graph, then η(G) equals , or n-2ν(G)+2. We also give a characterization of these three types of graphs. Furthermore, we determine the unicyclic graphs G with η(G)=0, which answers affirmatively an open problem by Tan and Liu.     

On the nullity of graphs with pendent vertices

The nullity of a graph G, denoted by η(G), is the multiplicity of the eigenvalue zero in its spectrum. Cheng and Liu [B. Cheng, B. Liu, On the nullity of graphs, Electron. J. Linear Algebra 16 (2007) 60-67] characterized the extremal graphs attaining the upper bound n-2 and the second upper bound n-3. In this paper, as the continuance of it, we determine the extremal graphs with pendent vertices achieving the third upper bound n-4 and fourth upper bound n-5. We then proceed recursively to construct all graphs with pendent vertices which satisfy η(G)>0. Our results provide a unified approach to determine n-vertex unicyclic (respectively, bicyclic and tricyclic) graphs which achieve the maximal and second maximal nullity and characterize n-vertex extremal trees attaining the second and third maximal nullity. As a consequence we, respectively, determine the nullity sets of trees, unicyclic graphs, bicyclic graphs and tricyclic graphs on n vertices.     

Line graphs: Their maximum nullities and zero forcing numbers

The maximum nullity over a collection of matrices associated with a graph has been attracting the attention of numerous researchers for at least three decades. Along these lines various zero forcing parameters have been devised and utilized for bounding the maximum nullity. The maximum nullity and zero forcing number, and their positive counterparts, for general families of line graphs associated with graphs possessing a variety of specific properties are analysed. Building upon earlier work, where connections to the minimum rank of line graphs were established, we verify analogous equations in the positive semidefinite cases and coincidences with the corresponding zero forcing numbers. Working beyond the case of trees, we study the zero forcing number of line graphs associated with certain families of unicyclic graphs.