Hypernetworks in a directed hypergraph

Recently novel distributed approaches to the formation of collaborative networked organizations have been proposed. Some of them make use of logical–formal structures (i.e., hypernetworks and hyperpaths) based on concepts related to directed hypergraphs in order to formally represent competitive inter-cluster and collaborative intra-cluster relationships.     

The largest two Laplacian eigenvalues of a graph

In this article, we present lower bounds for the largest eigenvalue, the second largest eigenvalue and the sum of the two largest eigenvalues of the Laplacian matrix of a graph.     

面向光子网格任务调度的迭代列表算法

光子网格中任务和通信的联合调度是一个非确定性多项式难题.为了进一步优化调度长度,本文在扩展列表算法的基础上,提出一种迭代列表调度算法.该算法通过扩展列表算法产生一个初始调度序列,并通过迭代的方式不断估计调度过程中子任务之间的通信时间;然后重新计算子任务的权重,调整子任务的调度序列,达到改善调度长度的目的.仿真实验表明,迭代调度算法对于大部分的实例能够有效地减少任务的调度长度,并且更加适用于数据密集型的任务调度.     

USING NETWORK ANALYSIS TO CHARACTERIZE FOREST STRUCTURE

Abstract Network analysis quantifies different structural properties of systems of interrelated parts using a single analytical framework. Many ecological phenomena have network‐like properties, such as the trophic relationships of food webs, geographic structure of metapopulations, and species interactions in communities. Therefore, our ability to understand and manage such systems may benefit from the use of network‐analysis techniques. But network analysis has not been applied extensively to ecological problems, and its suitability for ecological studies is uncertain. Here, we investigate the ability of network analysis to detect spatial patterns of species association in a tropical forest. We use three common graph‐theoretic measures of network structure to quantify the effect of understory tree size on the spatial association of understory species with trees in the canopy: the node degree distribution (NDD), characteristic path length (CPL), and clustering coefficient (CC). We compute the NDD, CPL, and CC for each of seven size classes of understory trees. For significance testing, we compare the observed values to frequency distributions of each statistic computed from randomized data. We find that the ability of network analysis to distinguish observed patterns from those representing randomized data strongly depends on which aspects of structure are investigated. Analysis of NDD finds no significant difference between random and observed networks. However, analysis of CPL and CC detected nonrandom patterns in three and one of the seven size classes, respectively. Network analysis is a very flexible approach that holds promise for ecological studies, but more research is needed to better understand its advantages and limitations.     

Total and fractional total colourings of circulant graphs

In this paper, the total chromatic number and the fractional total chromatic number of circulant graphs are studied. For cubic circulant graphs we give upper bounds on the fractional total chromatic number and for 4-regular circulant graphs we find the total chromatic number for some cases and we give the exact value of the fractional total chromatic number in most cases.     

关于二部图和欧拉图的列表着色

设G-（V．E）是二部图．D是G的一个定向具有出度序列（dD^＋（v）｜v∈V）．设fD（v）=dD^＋（v）＋1是定义在V上的整数函数．在本文中我们利用代数方法证明了G是fD-可选的，并由此推出G是（[（（△（G））/2]＋1）-可选的．2d-正则偶图是（d＋1）-可选的．定义了欧拉图的半度-可选概念．并给出了一类半度-可选的欧拉非偶图．最后，提出了刻化半度-可选的欧拉图．     

Strong Endomorphism Monoid of Graph Union

ＳｔｒｏｎｇＥｎｄｏｍｏｒｐｈｉｓｍＭｏｎｏｉｄｏｆＧｒａｐｈＵｎｉｏｎ＊）ＬｉＷｅｉｍｉｎ（李为民）（ＤｅｐａｒｔｍｅｎｔｏｆＭａｔｈｅｍａｔｉｃｓ，ＳｈａｎｇｈａｉＪｉａｏｔｏｎｇＵｎｉｖｅｒｓｉｔｙ，２００２４０）ＡｂｓｔｒａｃｔＴｈｅｓｔｒｏ...     

不可约圈与路之并补图的色唯一性

讨论了形如ｋＣＲＵｒＰＲ的一类图的补图的色性．在一定的条件下证明了这类图是色唯一的．本文推广了文［１］的结果．     

Recognizing Knödel graphs

Knödel graphs form a class of bipartite incident-graph of circulant digraphs. This class has been extensively studied for the purpose of fast communications in networks, and it has deserved a lot of attention in this context. In this paper, we show that there exists an O(n log⁵ n)-time algorithm to recognize Knödel graphs of order 2n. The algorithm is based on a characterization of the cycles of length six in these graphs (bipartite incident-graphs of circulant digraphs always have cycles of length six). A consequence of our result is that the circulant digraphs whose chords are the power of two minus one can be recognized in O(n log⁵ n) time.     

图有[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]因子。