A Sufficient Condition for a Graph to Have a k-tree

 A k-tree of a connected graph is a spanning tree with maximum degree at most k. We obtain a sufficient condition for a graph to have a k-tree, as a generalization of the condition of E. Flandrin, H. A. Jung and H. Li [3] for traceability. We also extend early results of Y. Caro, I. Krasikov and Y. Roditty [2] and Min Aung and Aung Kyaw [4] for the maximal order of a tree with bounded maximum degree in a graph. Received: July 28, 1997 Final version received: April 13, 1998     

包含k-树图的毁裂度条件

连通图G的一个k-树是指图G的一个最大度至多是k的生成树.对于连通图G来说,其毁裂度定义为r(G)=max{ω(G-X)-|X|-m(G-X)|X■V(G),ω(G-X)1}其中ω(G-X)和m(G-X)分别表示G-X中的分支数目和最大分支的阶数.本文结合毁裂度给出连通图G包含一个k-树的充分条件;利用图的结构性质和毁裂度的关系逐步刻画并给出图G包含一个k-树的毁裂度条件.     

树与偏k—的乘积的树宽

本文确宇了一棵树与一个k-连通偏k-树的乘积图的树宽。其中,偏k-树是一个树宽为k的图。     

图的树宽的结构性结果

图G的树宽是使得G成为一个k-树的子图的最小整数k．树宽的算法性结果在图子式理论及有关领域中已有深入的研究．本文着重讨论其结构性结果，包括拓扑不变性、子式单调性、可分解性、刻画问题、与其它参数的关系及由此引伸出的性质．     

The chromatic number of oriented graphs

We introduce in this paper the notion of the chromatic number of an oriented graph G (that is of an antisymmetric directed graph) defined as the minimum order of an oriented graph H such that G admits a homomorphism to H. We study the chromatic number of oriented k-trees and of oriented graphs with bounded degree. We show that there exist oriented k-trees with chromatic number at least 2^k+1 - 1 and that every oriented k-tree has chromatic number at most (k + 1) × 2^k. For 2-trees and 3-trees we decrease these upper bounds respectively to 7 and 16 and show that these new bounds are tight. As a particular case, we obtain that oriented outerplanar graphs have chromatic number at most 7 and that this bound is tight too. We then show that every oriented graph with maximum degree k has chromatic number at most (2k - 1) × 2^2k-2. For oriented graphs with maximum degree 2 we decrease this bound to 5 and show that this new bound is tight. For oriented graphs with maximum degree 3 we decrease this bound to 16 and conjecture that there exists no such connected graph with chromatic number greater than 7. © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 191–205, 1997     

On extremal sizes of locally k-tree graphs

A graph G is a locally k-tree graph if for any vertex v the subgraph induced by the neighbours of v is a k-tree, k ⩾ 0, where 0-tree is an edgeless graph, 1-tree is a tree. We characterize the minimum-size locally k-trees with n vertices. The minimum-size connected locally k-trees are simply (k + 1)-trees. For k ⩾ 1, we construct locally k-trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an n-vertex locally k-tree graph is between Ω(n) and O(n ²), where both bounds are asymptotically tight. In contrast, the number of edges in an n-vertex k-tree is always linear in n.     

On a horizontal conformal Killing tensor of degreep in a sasakian space

Summary We deal with a horizontal conformal Killing tensor of degree p in a Sasakian space. After some preparations we prove that a horizontal conformal Killing tensor of odd degree is necessarily Killing. Moreover, we consider horizontal conformal Killing tensor of even degree. The form of the associated tensor is determined completely and a decomposition theorem is proved. Then we give the examples of a conformal Killing tensor of even degree and a special Killing tensor of odd degree with constant l. Entrata in Redazione il 17 luglio 1971.     

M-G-P型复杂网络中有寿命节点的进入退出机制

现实中复杂网络结构复杂,形式多样,处在高度动态变化的过程.为了更好地理解真实网络的演化,基于复杂网络的特性进行分析,建立了Poissotn连续时间增长节点具有寿命的M-G-P型复杂网络模型,模型中包括:新节点加入、节点老化和老节点退出等,基于齐次马尔可夫链对模型的度分布进行计算,得出M-G-P型网络的度分布符合幂律分布,模型和BA模型一样能产生指数γ=3的无标度网络,验证了导致无标度网络度分布特征起关键性作用的是链接的偏好特性.     

The Weierstrass semigroup of a pair of GaloisWeierstrass points with prime degree on a curve

We describe the Weierstrass semigroup of a Galois Weierstrass point with prime degree and the Weierstrass semigroup of a pair of Galois Weierstrass points with prime degree, where a Galois Weierstrass point with degree n means a total ramification point of a cyclic covering of the projective line of degree n.*Supported by Korea Research Foundation Grant (KRF-2003-041-C20010).**Partially supported by Grant-in-Aid for Scientific Research (15540051), JSPS.     

Measuring centrality by a generalization of degree

Network analysis has emerged as a key technique in communication studies, economics, geography, history and sociology, among others. A fundamental issue is how to identify key nodes, for which purpose a number of centrality measures have been developed. This paper proposes a new parametric family of centrality measures called generalized degree. It is based on the idea that a relationship to a more interconnected node contributes to centrality in a greater extent than a connection to a less central one. Generalized degree improves on degree by redistributing its sum over the network with the consideration of the global structure. Application of the measure is supported by a set of basic properties. A sufficient condition is given for generalized degree to be rank monotonic, excluding counter-intuitive changes in the centrality ranking after certain modifications of the network. The measure has a graph interpretation and can be calculated iteratively. Generalized degree is recommended to apply besides degree since it preserves most favourable attributes of degree, but better reflects the role of the nodes in the network and has an increased ability to distinguish among their importance.     

一类无标度随机图的度序列

本文从-个新的角度对-类随机图的度序列进行了分析.证明了此模型度分布的存在性,得到了网络规模比较大的情况下度为七的节点所占比例数的表达式.此外,我们还将模型扩展到每个时间步增加边数为随机变量的情形,得到了类似的结论.     

On a generalization of relative degree

We generalize the notion of relative degree for a controlled dynamical system (possibly, discrete). We show that the new notion of leading incomplete relative degree is uniquely determined for a broad class of “square” dynamical systems (i.e., systems with as many inputs as outputs), including controllable systems. If r is the vector of relative degree of a system in the classical sense, then it is so in the generalized sense as well. We indicate a constructive algorithm for computing the leading incomplete relative degree.     

Existence of a trade-off factorization of a partially 4-homogeneous graph

We consider a graph G with 2κ vertices of degree 5 and κ vertices of degree 2, all other vertices being of degree 4. In connection with the timetable optimization problem, we study necessary and sufficient conditions for the existence of a factorization of G into two skeleton subgraphs whose edge sets are disjoint and have the same cardinality and, for each vertex of the graph, the numbers of edges incident to this vertex in these subgraphs differ at most by unity.     

On a conjecture of Lempp

In this paper, we first prove that there exist computably enumerable (c.e.) degrees a and b such that , and for any c.e. degree u, if and u is cappable, then , so refuting a conjecture of Lempp (in Slaman [1996]); secondly, we prove that: (A. Li and D. Wang) there is no uniform construction to build nonzero cappable degree below a nonzero c.e. degree, that is, there is no computable function such that for all (i) , (ii) has a cappable degree, and (iii) unless Received: 19 Otober 1998     

The parametric degree of a rational surface

The parametric degree of a rational surface is the degree of the polynomials in the smallest possible proper parametrization. An example shows that the parametric degree is not a geometric but an arithmetic concept, in the sense that it depends on the choice of the ground field. In this paper, we introduce two geometric invariants of a rational surface, namely level and keel. These two numbers govern the parametric degree in the sense that there exist linear upper and lower bounds. Supported by the Austrian Science Fund (FWF) in the frame of the reseach projects SFB 1303 and P15551     

Fast computation of a rational point of a variety over a finite field

We exhibit a probabilistic algorithm which computes a rational point of an absolutely irreducible variety over a finite field defined by a reduced regular sequence. Its time-space complexity is roughly quadratic in the logarithm of the cardinality of the field and a geometric invariant of the input system. This invariant, called the degree, is bounded by the Bézout number of the system. Our algorithm works for fields of any characteristic, but requires the cardinality of the field to be greater than a quantity which is roughly the fourth power of the degree of the input variety.

     

Degree distribution of a scale-free random graph model

In this paper, we consider the degree distribution of a general random graph with multiple edges and loops from the perspective of probability. Based on the first-passage probability of Markov chains, we give a new and rigorous proof to the existence of the network degree distribution and obtain the precise expression of the degree distribution. The analytical results are in good agreement with numerical simulations.     

一类团体网络的拓扑结构

团体结构是很多现实网络所具有的一个共性，为了更好的研究这一类网络，我们提出了一个新的带有团体结构的网络模型，用平均场方法分析了此网络的内度和外度，发现此网络具有无标度特性。     

On automorphic factors of a compact Riemann surface

Summary Automorphic factors of degree n of a compact complex manifold are defined and the problem that ? Can every automorphic factor of degree n over a compact Riemann surface M be expressed as a product of a representation of the fundamental group of M and a certain canonical automorphic factor of M? ? is studied. The answer is found in affirmative for factors of degree1 and in negative for higher degree factors by explicit construction. Entrata in Redazione il 16 maggio 1972.     

Bipartite graphs without a skew star

A skew star is a tree with exactly three vertices of degree one being at distance 1, 2, 3 from the only vertex of degree three. In the present paper, we propose a structural characterization for the class of bipartite graphs containing no skew star as an induced subgraph and discuss some applications of the obtained result.