非连通图G1∪G2及G1∪G2∪K2的优美性

将k-优美图的概念进行了推广，引入了k-l优美图及标号间距的概念，并以此为基础，分别推出了一般情形下判定非连通图G1∪G2及G1∪G2∪K2是优美图的两个充分条件；同时得出了图（C3VK^-n）∪st（m）∪K2是优美图，其中k、l为自然数，l〈k，C3是长为3的圈，Kn为n个顶点的完全图，K^-n是Kn的补图，St（m）表示m＋1个顶点的星形树，C3VK^-n是C3与K^-n的联图．     

图有[a,b]因子的邻域条件

不含有图K1，R的图称为K1,r-free图，设G是一个具有顶点集V（G）的图，设n(≥3),a和b是整数，使得b≥a≥1，若b是奇数，设b≥n-1。我们证明了每个连通的K1,r-free图G在b|V(G)|为偶数，它的最小度至少是a n-1,|V(G）≥ （2(a b)-1)(a b-1)/b，以及|NG(x）∪NG（y)|≥a|V(G)|a b对V的任意两个不邻接的点x和y都成立时，G有一个[a,b]因子。     

图类αK_a∪βCP(b)中的一类特殊整谱图

图G是一个简单图,图G的补图记为G,如果G的谱完全由整数组成,就称G是整谱图.鸡尾酒会图CP(n)=K_(2n)-nK2(K_(2n是完全图)和完全图K_a都是整谱图.μ_1表示图类αK_a∪βCP(b)的一个主特征值,确定了当μ_1=2a并且a-1>2b-2时,图类αK_a∪βCP(b)中的所有的整谱图.     

一个伴随等价定理的推广及其简证

记 Gr为任意图 G的 r个拷贝中的对应点 ( r个 )分别与星图 Sr+ 1 的 r个 1度点粘接后得到的图 ,又记 H r为该图 G的相应点与星图 Sr+ 1 的 r度点粘接后得到的图 .如果 G不含三角形 ,则图 ( r- 1) K1 ∪ Gr和图 ( r- 1) G∪ H r伴随等价 ,进而它们的补图色等价     

图类￣(αKa∪βCP(b))中的整谱图

设图G是一个简单图,图G的补图记为(G),如果G的谱都是整数,就称G是整谱图.鸡尾酒会图CP(n)=K2n-nK2(K2n是2n阶完全图)和完全图Ka都是整谱图[1].本文确定了图类￣αKa∪βCP(b)中的所有整谱图.     

树的Nordhaus-Gaddum类型谱半径的排序

给出了n阶树的Nordhaus-Gaddum类型谱半径即图及其补图的谱半径之和的可达上界:ρ(T) ρ(Tc)≤■ n-2,等号成立当且仅当T K1,n-1,其中Tc为T的补图,K1,n-1为n阶星图.同时证明了对于n阶双星图S(a,b)的Nordhaus-Gaddum类型谱半径随a的值单调上升,其中[n-1/2]≤a≤n-3.     

[αCP（a）∪βCP（b）]^-中的一类特殊整谱图

图G是一个简单，图G的补图记为G^-，如果G的谱完全由整数组成，就称G是整谱图，鸡尾酒会图G=CP（n）=K2n-nK2（K2n是完全图）.本文确定了当μ1^-=ab＋1时，图类[αCP（a）∪βCP（b）]^-中的所有整谱图.     

图类aKa,a\βCP(b)中的整谱图

设图G是一个简单图,图G的补图记为G,如果G的谱都是整数.就称G是整谱图.鸡尾酒会图CP(n)=K2n-nK2(K2n是2n阶完全图)和完全二部图K…都是整谱图.确定了图类 aKa,a∪βCP中的所有的整谱图.     

一个关于图是[a,b;n]-均匀的度条件

设t,a,b和n为整数且1≤a＜b,t≥3以及n≥1.如果G的导出子图不含有K1,t,则该图G称为K1,t-无爪图.如果对于图G中含有n条边的任意匹配M,都在G中有[a,b]-因子F包含M以及在G中有另一个[a,b]-因子F'不包含M,则图G称为[a,b;n]-均匀图.给出了K1,t-无星图G是[a,b;n]-均匀图的度条件.进一步,指出本文中的结果在某种意义上说是最佳的.     

非连通图G_1uG_2及G_1uG_2uK_2的优美性

将k-优美图的概念进行了推广,引入了k～l 优美图及标号间距的概念,并以此为基础, 分别推出了一般情形下判定非连通图G_1 ∪G_2及G_1 ∪G_2 ∪K_2是优美图的两个充分条件;同时得出了图(C_3 ∨(?)_n)∪St(m)∪K_2是优美图,其中k、l 为自然数,l相似文献   

图的邻接矩阵的行列式与积和式的递推表达式

设A(G)是简单图G的邻接矩阵,H是由G的独立边和不交圈组成的生成子图的集合,e是H中某个图的独立边,C是H中图的圈,且e∈E(C).记G-e是G的删边子图,G\W是从G中删去导出子图W中的顶点及其关联边后得到的图.那么A(G)的行列式为detA(G)=detA(G-e)-detA(G\e)-2(-1)~(|V(C)|)detA(G\C)A(G)的积和式为perA(G)=perA(G-e)+perA(G\e)+2perA(G\C)这里,C取遍H中图的经过边e的圈.     

最大度与最小度相差不超过2的图的平衡judicious划分

图G的顶点集V(G)的一个二部划分V_1和V_2叫做平衡二部划分,如果||V_1|-|V_2||≤1成立.Bollobas和Scott猜想:每一个有m条边且最小度不小于2的图,都存在一个平衡二部划分V_1,V_2,使得max{e(V_1),e(V_2)}≤m/3,此处e(V_i)表示两顶点都在V_i(i=1,2)中的边的条数.他们证明了这个猜想对正则图(即△(G)=δ(G))成立.颜娟和许宝刚证明了每个(k,k-1)-双正则图(即△(G)-δ(G)≤1)存在一个平衡二部划分V_1,V_2,使得每一顶点集的导出子图包含大约m/4条边.这里把该结论推广到最大度和最小度相差不超过2的图G.     

Hamilton非二部图的弱泛圈性

图G称为弱泛圈图是指G包含了每个长为t(g(V)≤l≤c(G))的圈,其中g(G),c(v)分别是G的围长与周长.1997年Brandt提出以下猜想:边数大于[n2/4]-n 5的n阶非二部图为弱泛圈图.1999年Bollobas和Thomason证明了边数不小于[n2/4]-n 59的n阶非二部图为弱泛圈图.作者证明了如下结论:设G是n阶Hamilton非二部图,若G的边数不小于[n2/4]-n 12,则G为弱泛圈图.     

完全对换网络的限制连通度

完全对换网络是基于 Cayley 图模型的一类重要互连网络. 一个图 G 的 k-限制点(边)连通度是使得 G-F 不连通且每个分支至少有 k 个顶点的最小点(边)子集 F 的基数, 记作 \kappa_{k}(\lambda_{k}). 它是衡量网络可靠性的重要参数之一, 也是图的容错性的一种精化了的度量. 一般地, 网络的 k-限制点(边)连通度越大, 它的连通性就越好. 证明了完全对换网络 CT_{n} 的 2-限制点(边)连通度和 3-限制点(边)连通度, 具体来说: 当 n\geq4 时, \kappa_{2}(CT_{n})=n(n-1)-2, \kappa_{3}(CT_{n})=\frac{3n(n-1)}{2}-6; 当 n\geq3 时, \lambda_{2}(CT_{n})=n(n-1)-2, \lambda_{3}(CT_{n})=\frac{3n(n-1)}{2}-4.     

平衡子欧拉符号图及符号线图

符号图$S=(S^u,\sigma)$是以$S^u$作为底图并且满足$\sigma: E(S^u)\rightarrow\{+,-\}$. 设$E^-(S)$表示$S$的负边集. 如果$S^u$是欧拉的(或者分别是子欧拉的, 欧拉的且$|E^-(S)|$是偶数, 则$S$是欧拉符号图(或者分别是子欧拉符号图, 平衡欧拉符号图). 如果存在平衡欧拉符号图$S''$使得$S''$由$S$生成, 则$S$是平衡子欧拉符号图. 符号图$S$的线图$L(S)$也是一个符号图, 使得$L(S)$的点是$S$中的边, 其中$e_ie_j$是$L(S)$中的边当且仅当$e_i$和$e_j$在$S$中相邻,并且$e_ie_j$是$L(S)$中的负边当且仅当$e_i$和$e_j$在$S$中都是负边. 本文给出了两个符号图族$S$和$S''$,它们应用于刻画平衡子欧拉符号图和平衡子欧拉符号线图. 特别地, 本文证明了符号图$S$是平衡子欧拉的当且仅当$\not\in S$, $S$的符号线图是平衡子欧拉的当且仅当$S\not\in S''$.     

5-正则图的全控制数的一个注记

设G是不含孤立点的图,S是G的一个顶点子集,若G的每一个顶点都与S中的某顶点邻接,则称S是G的全控制集.G的最小全控制集所含顶点的个数称为G的全控制数,记为γt(G).Thomasse和Yeo证明了若G是最小度至少为5的n阶连通图,则γt(G)≤17n/44.在5-正则图上改进了Thomasse和Yeo的结论,证明了若G是n阶5-正则图,则,γt(G)≤106n/275.     

Graph Sparsification by Universal Greedy Algorithms

Graph sparsification is to approximate an arbitrary graph by a sparse graph and is useful in many applications, such as simplification of social networks, least squares problems, and numerical solution of symmetric positive definite linear systems. In this paper, inspired by the well-known sparse signal recovery algorithm called orthogonal matching pursuit (OMP), we introduce a deterministic, greedy edge selection algorithm, which is called the universal greedy approach (UGA) for the graph sparsification problem. For a general spectral sparsification problem, e.g., the positive subset selection problem from a set of $m$ vectors in $\mathbb{R}^n$, we propose a nonnegative UGA algorithm which needs $O(mn^2+ n^3/\epsilon^2)$ time to find a $\frac{1+\epsilon/\beta}{1-\epsilon/\beta}$-spectral sparsifier with positive coefficients with sparsity at most $\lceil\frac{n}{\epsilon^2}\rceil$, where $\beta$ is the ratio between the smallest length and largest length of the vectors. The convergence of the nonnegative UGA algorithm is established. For the graph sparsification problem, another UGA algorithm is proposed which can output a $\frac{1+O(\epsilon)}{1-O(\epsilon)}$-spectral sparsifier with $\lceil\frac{n}{\epsilon^2}\rceil$ edges in $O(m+n^2/\epsilon^2)$ time from a graph with $m$ edges and $n$ vertices under some mild assumptions. This is a linear time algorithm in terms of the number of edges that the community of graph sparsification is looking for. The best result in the literature to the knowledge of the authors is the existence of a deterministic algorithm which is almost linear, i.e. $O(m^{1+o(1)})$ for some $o(1)=O(\frac{(\log\log(m))^{2/3}}{\log^{1/3}(m)})$. Finally, extensive experimental results, including applications to graph clustering and least squares regression, show the effectiveness of proposed approaches.     

Antimagic Labelings of Join Graphs

An antimagic labeling of a graph with q edges is a bijection from the set of edges of the graph to the set of positive integers \({\{1, 2,\dots,q\}}\) such that all vertex weights are pairwise distinct, where a vertex weight is the sum of labels of all edges incident with the vertex. The join graph G + H of the graphs G and H is the graph with \({V(G + H) = V(G) \cup V(H)}\) and \({E(G + H) = E(G) \cup E(H) \cup \{uv : u \in V(G) {\rm and} v \in V(H)\}}\). The complete bipartite graph K _m,n is an example of join graphs and we give an antimagic labeling for \({K_{m,n}, n \geq 2m + 1}\). In this paper we also provide constructions of antimagic labelings of some complete multipartite graphs.     

Turán-type bounds for distance graphs

A lower bound is obtained for the number of edges in a distance graph G in an infinitesimal plane layer ?² × [0, ε] ^d , which relates the number of edges e(G), the number of vertices ν(G), and the independence number α(G). It is proved that \(e\left( G \right) \geqslant \frac{{19\nu \left( G \right) - 50\alpha \left( G \right)}}{3}\). This result generalizes a previous bound for distance graphs in the plane. It substantially improves Turán’s bound in the case where \(\frac{1}{5} \leqslant \frac{{\alpha \left( G \right)}}{{\nu \left( G \right)}} \leqslant \frac{2}{7}\).     

移位交换网的最优路由算法

移位交换网是重要的互联网络之一 ,在并行计算中有着广泛应用 .然而 ,它缺少任意点对间的最短路由算法 .已有的路由算法都不能保证其任意节点对间都是最短路由 .文中给出了一个最短路由算法 ,也是最优路由算法 ,它使得从源节点到目的节点的任何信息都是沿最短路由传输 .同时 ,我们还得到了任意节点对间的距离公式