Stable network topologies using the notion of covering

An alternative perspective to evaluate networks and network evolution is introduced, based on the notion of covering. For a particular node in a network covering captures the idea of being outperformed by another node in terms of, for example, visibility and possibility of information gathering. In this paper, we focus on networks where these subdued network positions do not exist. We call these networks stable. Within this set we identify the minimal stable networks, which frequently have a ‘bubble-like’ structure. Severing a link in such a network results in at least one of the nodes being covered. In a minimal stable network therefore all nodes cooperate to avoid that one of the nodes ends up in a subdued position. Our results can be applied to, for example, the design of (covert) communication networks and the dynamics of social and information networks.     

The Threshold for the Erdos, Jacobson and Lehel Conjecture to Be True

Let σ（k, n） be the smallest even integer such that each n-term positive graphic sequence with term sum at least σ（k, n） can be realized by a graph containing a clique of k ＋ 1 vertices. Erdos et al. （Graph Theory, 1991, 439-449） conjectured that σ（k, n） = （k - 1）（2n- k） ＋ 2. Li et al. （Science in China, 1998, 510-520） proved that the conjecture is true for k 〉 5 and n ≥ （k2） ＋ 3, and raised the problem of determining the smallest integer N（k） such that the conjecture holds for n ≥ N（k）. They also determined the values of N（k） for 2 ≤ k ≤ 7, and proved that [5k-1/2] ≤ N（k） ≤ （k2） ＋ 3 for k ≥ 8. In this paper, we determine the exact values of σ（k, n） for n ≥ 2k＋3 and k ≥ 6. Therefore, the problem of determining σ（k, n） is completely solved. In addition, we prove as a corollary that N（k） -= [5k-1/2] for k ≥6.     

聚合物流动诱导结晶研究进展

在外力作用下,半结晶聚合物的结晶形态、结晶动力学等与静态条件下相比,均发生了较大的变化,并继而影响到成型制品的性能.自上世纪六十年代人们从溶液中发现外力诱导结晶现象以来,相继开展了大量相关的理论和实验研究,提出了一些模型,随着测试手段的改进,流动诱导结晶研究取得了较大的进展,但仍存在许多争议.本文回顾了围绕聚合物流动诱导结晶所开展的工作,重点综述了流动诱导结晶形态变化、分子量及其分布、剪切速率、温度等因素对聚合物结晶动力学的影响,并指出了今后的研究方向.     

随机BA模型的度分布

本文将马氏链首达概率方法应用于一个随机BA模型,得到这个模型度分布的精确表达式,并严格证明了度分布的存在性,同时说明择优连接对无标度特性的产生至关重要。     

随机增长网络的度分布

增长和择优机制是无标度网络中的两种重要的演化机制,在分析BA模型的基础上,提出了一种新的节点增长方式,即考虑了新增节点的连边数是随机变量的情况,从而建立了随机增长网络模型,并利用随机过程理论得到了在这种增长方式下网络的度分布,结果表明这个网络是无标度网络。     

Weak cycle partition involving degree sum conditions

Let G be a graph of order n and k a positive integer. A set of subgraphs H={H₁,H₂,…,H_k} is called a k-degenerated cycle partition (abbreviated to k-DCP) of G if H₁,…,H_k are vertex disjoint subgraphs of G such that and for all i, 1≤i≤k, H_i is a cycle or K₁ or K₂. If, in addition, for all i, 1≤i≤k, H_i is a cycle or K₁, then H is called a k-weak cycle partition (abbreviated to k-WCP) of G. It has been shown by Enomoto and Li that if |G|=n≥k and if the degree sum of any pair of nonadjacent vertices is at least n−k+1, then G has a k-DCP, except G≅C₅ and k=2. We prove that if G is a graph of order n≥k+12 that has a k-DCP and if the degree sum of any pair of nonadjacent vertices is at least , then either G has a k-WCP or k=2 and G is a subgraph of K₂∪K_n−2∪{e}, where e is an edge connecting V(K₂) and V(K_n−2). By using this, we improve Enomoto and Li’s result for n≥max{k+12,10k−9}.     

On the combinatorics of an origami model

We consider the problem of how the assembly process of an origami model, made up of similar pieces, can be completed given that at each step there are several choices. A result is given in the language of graphs that provides a sufficient condition under which assembly of the model will never fail.     

Subgraph induced by the set of degree 5 vertices in a contraction critically 5-connected graph

An edge of a 5-connected graph is said to be contractible if the contraction of the edge results in a 5-connected graph. A 5-connected graph with no contractible edge is said to be contraction critically 5-connected. Let G be a contraction critically 5-connected graph and let H be a component of the subgraph induced by the set of degree 5 vertices of G. Then it is known that |V(H)|≥4. We prove that if |V(H)|=4, then , where stands for the graph obtained from K₄ by deleting one edge. Moreover, we show that either |N_G(V(H))|=5 or |N_G(V(H))|=6 and around H there is one of two specified structures called a -configuration and a split -configuration.     

Graphs of given degree and diameter obtained as abelian lifts of dipoles

We derive an upper bound on the number of vertices in regular graphs of given degree and diameter arising as regular coverings of dipoles over abelian groups.     

On the explicit solutions of forms of the Sylvester and the Yakubovich matrix equations

In this paper, we consider the explicit solutions of two matrix equations, namely, the Yakubovich matrix equation V−AVF=BW and Sylvester matrix equations AV−EVF=BW,AV+BW=EVF and AV−VF=BW. For this purpose, we make use of Kronecker map and Sylvester sum as well as the concept of coefficients of characteristic polynomial of the matrix A. Some lemmas and theorems are stated and proved where explicit and parametric solutions are obtained. The proposed methods are illustrated by numerical examples. The results obtained show that the methods are very neat and efficient.