折叠交叉立方体的分支边连通度

r-分支连通度(边连通度)是衡量大型互连网络可靠性和容错性的一个重要参数.设G是连通图且r是非负整数,如果G中存在某种点子集(边子集)使得G删除这种点子集(边子集)后得到的图至少有r个连通分支.则所有这种点子集(边子集)中基数最小的点子集(边子集)的基数称为图G的r-分支连通度(边连通度).n-维折叠交叉立方体FCQn是由交叉立方体CQn增加2n-1条边后所得.该文利用r-分支边连通度作为可靠性的重要度量,对折叠交叉立方体网络的可靠性进行分析,得到了折叠交叉立方体网络的2-分支边连通度,3-分支边连通度,4分支边连通度.确定了折叠交叉立方体FCQn的r-分支边连通度.     

广义I型连通级小极大分式问题的对偶

在I型弧连通和广义I型弧连通假设下,建立了极大极小分式优化问题的对偶模型,并提出了弱对偶定理、强对偶定理和严格逆对偶定理.     

具有完美匹配树的代数连通度的排序

Jason等确定了阶数为n的具有完美匹配树的最大的代数连通度以及相应的极图．本文确定了阶数为n的具有完美匹配树的第二大到第五大的代数连通度以及达到这些数值的图（或图类）．     

随机图的广义3-连通度

图的广义连通度的概念是由Chartrand等人引入的.令S表示图G的一个非空顶点集,κ(S)表示图G中连结S的内部不交树的最大数目.那么,对任意一个满足2≤r≤n的整数r,定义G的广义r-连通度为所有κ(S)中的最小值,其中S取遍G的顶点集合的r-元子集.显然,κ_2(G)=κ(G),即为图G的顶点连通度.所以广义连通度是经典连通度的一个自然推广.本文研究了随机图的广义3-连通度,证明了对任一给定的整数k,k≥1,p=(log n+(k+1)log long n-log lon logn)/n是关于性质κ_3(G(n,p))≥k的紧阈值函数.我们得到的结果可以看作是Bollobas和Thomason给出的关于经典连通度结果的推广.     

复合图及其连通度和临界度

本文确定了H(G)的点-连通度及H(G)关于点-连通度的临界度;确确定了H(G)的边-连通度及某种H(G)关于边-连通度的临界度。     

一类混合图的结构及其特征空间

主要讨论具有如下性质的一类连通混合图G:其所有非奇异圈恰有一条公共边,且除了该公共边的端点外,任意两个非奇异圈没有其它交点.本文给出了图G的结构性质,建立了其最小特征值λ1(G)(以及相对应的特征向量)与某个简单图的代数连通度(以及Fiedler向量)之间联系,并应用上述联系证明了λ1(■)≤α(G),其中G是由G通过对其所有无向边定向而获得,α(■)为■的代数连通度.     

关于凝聚度的探讨

图是由点和边组成的，对于一个连通图Ｇ，是否可以将点的结论推广到边？从而更好地研究图。本文就是将连通图Ｇ的点的凝聚度负点的最小截集的唯一性推广到边上，进而推广到边的凝聚度负集上，使对图的研究从点、边同时考虑，从而更全面、更方便研究图的性质。     

最小最大树划分的近似算法与最小和树划分的精确算法

本文研究把连通赋权图的点集划分成p个子集,要求每个点子集的导出子图都连通,并且使得所得到的p个子图的最小支撑树中权重最大者的权重达到最小(最小最大树划分问题),或者使得所得到的p个子图的最小支撑树权重之和达到最小(最小和树划分问题)．文中给出了最小最大树划分问题的强NP困难性证明,并给出了一个多项式时间算法,该算法是最小最大树划分问题的竞争比为p的近似算法,同时是最小和树划分问题的精确算法．     

关于Mbius立方体网格的连通度(英文)

图的连通度、超连通性和限制连通度是度量互连网络容错性的重要参数 .该文考虑n维M bius立方体网络MQn,证明了它的点和边连通度都为n ,当n是任何正整数时它是超连通的 ,当n≠ 2时它是超边连通的 ,当n≥ 3时它的限制点连通度和当n≥ 2时的限制边连通度都为 2n- 2 .     

扰动模糊命题逻辑的代数结构及其广义重言式性质

着眼于扰动模糊命题逻辑的代数结构,为研究二维扰动模糊命题逻辑最大子代数I2R及其广义重言式提供了一些代数理论基础,最后研究了子代数间广义重言式的关系.     

Algebraic connectivity of weighted trees under perturbation

We investigate how the algebraic connectivity of a weighted tree behaves when the tree is perturbed by removing one of its branches and replacing it with another. This leads to a number of results, for example the facts that replacing a branch in an unweighted tree by a star on the same number of vertices will not decrease the algebraic connectivity, while replacing a certain branch by a path on the same number of vertices will not increase the algebraic connectivity. We also discuss how the arrangement of the weights on the edges of a tree affects the algebraic connectivity, and we produce a lower bound on the algebraic connectivity of any unweighted graph in terms of the diameter and the number of vertices. Throughout, our techniques exploit a connection between the algebraic connectivity of a weighted tree and certain positive matrices associated with the tree.     

On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

On operations in which graphs are appended to trees

We consider the effects on the algebraic connectivity of various graphs when vertices and graphs are appended to the original graph. We begin by considering weighted trees and appending a single isolated vertex to it by adding an edge from the isolated vertex to some vertex in the tree. We then determine the possible set vertices in the tree that can yield the maximum change in algebraic connectivity under such an operation. We then discuss the changes in algebraic connectivity of a star when various graphs such as trees and complete graphs are appended to its pendant vertices.     

Characteristic vertices of weighted trees via perron values

We consider a weighted tree T with algebraic connectivity μ, and characteristic vertex v. We show that μ and its associated eigenvectors can be described in terms of the Perron value and vector of a nonnegative matrix which can be computed from the branches of T at v. The machinery of Perron-Frobenius theory can then be used to characterize Type I and Type II trees in terms of these Perron values, and to show that if we construct a weighted tree by taking two weighted trees and identifying a vertex of one with a vertex of the other, then any characteristic vertex of the new tree lies on the path joining the characteristic vertices of the two old trees.     

Spectral characterization of some weighted rooted graphs with cliques

The level of a vertex in a rooted graph is one more than its distance from the root vertex. A generalized Bethe tree is a rooted tree in which vertices at the same level have the same degree. We characterize completely the eigenvalues of the Laplacian, signless Laplacian and adjacency matrices of a weighted rooted graph G obtained from a weighted generalized Bethe tree of k levels and weighted cliques in which

(1)

the edges connecting vertices at consecutive levels have the same weight,

(2)

each set of children, in one or more levels, defines a weighted clique, and

(3)

cliques at the same level are isomorphic.

These eigenvalues are the eigenvalues of symmetric tridiagonal matrices of order Moreover, we give results on the multiplicity of the eigenvalues, on the spectral radii and on the algebraic conectivity. Finally, we apply the results to the unweighted case and some particular graphs are studied.     

Perron components and algebraic connectivity for weighted graphs

The algebraic connectivity of a connected graph is the second-smallest eigenvalue of its Laplacian matrix, and a remarkable result of Fiedler gives information on the structure of the eigenvectors associated with that eigenvalue. In this paper, we introduce the notion of a perron component at a vertex in a weighted graph, and show how the structure of the eigenvectors associated with the algebraic connectivity can be understood in terms of perron components. This leads to some strengthening of Fiedler's original result, gives some insights into weighted graphs under perturbation, and allows for a discussion of weighted graphs exhibiting tree-like structure.     

On heavy paths in 2-connected weighted graphs

A weighted graph is a graph in which every edge is assigned a non-negative real number. In a weighted graph, the weight of a path is the sum of the weights of its edges, and the weighed degree of a vertex is the sum of the weights of the edges incident with it. In this paper we give three weighted degree conditions for the existence of heavy or Hamilton paths with one or two given end-vertices in 2-connected weighted graphs.     

Computing tight upper bounds on the algebraic connectivity of certain graphs

A generalized Bethe tree is a rooted unweighted tree in which vertices at the same level have the same degree. Let B be a generalized Bethe tree. The algebraic connectivity of:

the generalized Bethe tree B,

a tree obtained from the union of B and a tree T isomorphic to a subtree of B such that the root vertex of T is the root vertex of B,

a tree obtained from the union of r generalized Bethe trees joined at their respective root vertices,

a graph obtained from the cycle C_r by attaching B, by its root, to each vertex of the cycle, and

a tree obtained from the path P_r by attaching B, by its root, to each vertex of the path,

is the smallest eigenvalue of a special type of symmetric tridiagonal matrices. In this paper, we first derive a procedure to compute a tight upper bound on the smallest eigenvalue of this special type of matrices. Finally, we apply the procedure to obtain a tight upper bound on the algebraic connectivity of the above mentioned graphs.

     

A divide-and-conquer bound for aggregate’s quality and algebraic connectivity

We establish a divide-and-conquer bound for the aggregate’s quality and algebraic connectivity measures, as defined for weighted undirected graphs. Aggregate’s quality is defined on a set of vertices and, in the context of aggregation-based multigrid methods, it measures how well this set of vertices is represented by a single vertex. On the other hand, algebraic connectivity is defined on a graph, and measures how well this graph is connected. The considered divide-and-conquer bound for aggregate’s quality relates the aggregate’s quality of a union of two disjoint sets of vertices to the aggregate’s quality of the two sets. Likewise, the bound for algebraic connectivity relates the algebraic connectivity of the graph induced by a union of two disjoint sets of vertices to the algebraic connectivity of the graphs induced by the two sets.     

Limit laws in the generalized random graphs with random vertex weights

In this note we investigate the number of edges and the vertex degree in the generalized random graphs with vertex weights, which are independent and identically distributed random variables.