Clique Numbers of Random Subgraphs of Some Distance Graphs

We consider a class of graphs G(n, r, s) = (V (n, r),E(n, r, s)) defined as follows:

$$V(n,r) = \{ x = ({x_{1,}},{x_2}...{x_n}):{x_i} \in \{ 0,1\} ,{x_{1,}} + {x_2} + ... + {x_n} = r\} ,E(n,r,s) = \{ \{ x,y\} :(x,y) = s\} $$

where (x, y) is the Euclidean scalar product. We study random subgraphs G(G(n, r, s), p) with edges independently chosen from the set E(n, r, s) with probability p each. We find nontrivial lower and upper bounds on the clique number of such graphs.

     

On Stability of the Independence Number of a Certain Distance Graph

Problems of Information Transmission - We study the asymptotic behavior of the independence number of a random subgraph of a certain (r, s)-distance graph. We provide upper and lower...     

Graph Characterization by Counting Sink Star Subgraphs

In this paper, we study the polynomial coefficients of the reduced Bartholdi zeta function for characterizing simple unweighted graphs and demonstrate how to use these coefficients for clustering graphs. The polynomial coefficients of the reduced Bartholdi zeta function are invariant to vertex order permutations and also carry information about counting the sink star subgraphs in a symmetric digraph of G. We also investigate the advantages of the reduced Bartholdi coefficients over other spectral methods such as the Ihara zeta function and Laplacian spectra. Experimental results indicate that the proposed method is more effective than the other spectral approaches, and compared to the Ihara zeta function, it has less sensitivity to structural noises such as omitting an edge.     

用PB实现随机取数

本文介绍了PowerBuilder中的随机函数，以及随机函数中“种子”（Seed)的选取方法，并且给出了实现随机取数的算法框图和程序。     

Verification of Random Graph Transformation Systems

In this paper we describe some statistical results obtained by the verification of random graph transformation systems (GTSs). As a verification technique we use over-approximation of GTSs by Petri nets. Properties we want to verify are given by markings of Petri nets. We also use counterexample-guided abstraction refinement approach to refine the obtained approximation. A software tool (Augur) supports the verification procedure. The idea of the paper is to see how many of the generated systems can be successfully verified using this technique.     

Planar Graph Coloring Avoiding Monochromatic Subgraphs: Trees and Paths Make It Difficult

We consider the problem of coloring a planar graph with the minimum number of colors so that each color class avoids one or more forbidden graphs as subgraphs. We perform a detailed study of the computational complexity of this problem. We present a complete picture for the case with a single forbidden connected (induced or noninduced) subgraph. The 2-coloring problem is NP-hard if the forbidden subgraph is a tree with at least two edges, and it is polynomially solvable in all other cases. The 3-coloring problem is NP-hard if the forbidden subgraph is a path with at least one edge, and it is polynomially solvable in all other cases. We also derive results for several forbidden sets of cycles. In particular, we prove that it is NP-complete to decide if a planar graph can be 2-colored so that no cycle of length at most 5 is monochromatic.     

On the Grundy and b-Chromatic Numbers of a Graph

The Grundy number of a graph G, denoted by Γ(G), is the largest k such that G has a greedy k-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertexes of G. The b-chromatic number of a graph G, denoted by χ _b (G), is the largest k such that G has a b-colouring with k colours, that is a colouring in which each colour class contains a b-vertex, a vertex with neighbours in all other colour classes. Trivially χ _b (G),Γ(G)≤Δ(G)+1. In this paper, we show that deciding if Γ(G)≤Δ(G) is NP-complete even for a bipartite graph G. We then show that deciding if Γ(G)≥|V(G)|?k or if χ _b (G)≥|V(G)|?k are fixed parameter tractable problems with respect to the parameter k.     

求解连通无向简图的所有连通子图的算法及其应用

讨论了求解连通无向简图的所有连通子图的算法,并将其应用于化学领域：如何将许多具有某种共同属性的物质的分子结构图形分解成子分子结构,进一步地试图找出存在于大多数具有该属性的物质中的子分子结构,并讨论这样的子分子结构导致物质具有该共同属性的概率。     

实现公共随机数同步的方法

实现公共随机数同步是仿真中获得输出估计量差衰减的关键，对随机变量分布函数的单调逼近能有效实现同步，并由此提出实现同步的方法。理论和实例显示所提方法行之有效的。     

关于Bubblesort-star网络的距离控制数

对于任意的正整数l,连通图G的顶点子集D被称为距离l-控制集,是指对于任意顶点v(∈)D,D中至少含有一个顶点u,使得u和v在G中的距离不超过l.图G的距离l-控制数是指G中所有距离l-控制集的最小基数,1-控制数常常称为控制数.给出了Bubblesort-star网络的控制数、距离2-控制数和距离3-控制数的界,而且针对某些低维Bubblesort-star网络的这几类控制数给出了更好的界.     

General Independence Sets in Random Strongly Sparse Hypergraphs

We analyze the asymptotic behavior of the j-independence number of a random k-uniform hypergraph H(n, k, p) in the binomial model. We prove that in the strongly sparse case, i.e., where \(p = c/\left( \begin{gathered} n - 1 \hfill \\ k - 1 \hfill \\ \end{gathered} \right)\) for a positive constant 0 < c ≤ 1/(k ? 1), there exists a constant γ(k, j, c) > 0 such that the j-independence number α _j (H(n, k, p)) obeys the law of large numbers \(\frac{{{\alpha _j}\left( {H\left( {n,k,p} \right)} \right)}}{n}\xrightarrow{P}\gamma \left( {k,j,c} \right)asn \to + \infty \) Moreover, we explicitly present γ(k, j, c) as a function of a solution of some transcendental equation.     

结点可同名的连通无向图的子图研究

给出了求解结点可同名的连通无向图的所有边极大连通子图的算法,并将其应用于化学领域: 将许多具有某种共同属性的物质的分子结构图形分解成子分子结构,进一步地试图找出存在于大多数具有该属性的物质中的子分子结构,并讨论这样的子分子结构导致物质具有该共同属性的可能性.     

结点可同名的连通无向图的子图研究

给出了求解结点可同名的连通无向图的所有边极大连通子图的算法,并将其应用于化学领域:将许多具有某种共同属性的物质的分子结构图形分解成子分子结构,进一步地试图找出存在于大多数具有该属性的物质中的子分子结构,并讨论这样的子分子结构导致物质具有该共同属性的可能性。     

基于环境噪声的真随机数的产生

为了提供一种简便和有效的真随机数生成方法,通过分析环境噪声数据的统计特性,提出同余法和正负法将声音波形数据进行处理。去除声波数据的周期性、连续性、相关性,提取其随机性。同真随机数采集系统设计相关的电路噪声问题以及采集速度问题也作了讨论。用此思路构建的真随机数采集系统原型已经能够用来产生性能较佳的真随机数,证明了设计思路和处理方法的正确有效性。     

Random Geometric Graph Diameter in the Unit Ball

The unit ball random geometric graph has as its vertices n points distributed independently and uniformly in the unit ball in , with two vertices adjacent if and only if their ℓ_p-distance is at most λ. Like its cousin the Erdos-Renyi random graph, G has a connectivity threshold: an asymptotic value for λ in terms of n, above which G is connected and below which G is disconnected. In the connected zone we determine upper and lower bounds for the graph diameter of G. Specifically, almost always, , where is the ℓ_p-diameter of the unit ball B. We employ a combination of methods from probabilistic combinatorics and stochastic geometry.     

Some Indices of Alphabet Overlap Graph

The undirected de Bruijn graph is often used as the model of communication network for its useful properties,such as short diameter,small maximum vertex degree.In this paper,we consider the alphabet overlap graph G(k,d,s): the vertex set V = {v|v = (v1 ...vk);vi ∈ {1,2,...,d},i = 1,2,...,k};they are distinct and two vertices u = (u1 ...uk) and v = (v1 ...vk) are adjacent if and only if us+i = vi or vs+i = ui (i = 1,2,...,k s).In particular,when s = 1,G(k,d,s) is just an undirected de Bruijn graph.First,we give a formula to calculate the vertex degree of G(k,d,s).Then,we use the corollary of Menger’s theorem to prove that the connectivity of G(k,d,s) is 2ds 2d2s k for s k/2.     

C语言中互不相同随机数的应用研究

文章对随机数的应用问题进行了详细的分析,给出了一种实现的算法,并用C语言实现。通过该问题的C实现,可使学习者清晰地观测到解决该问题的全过程。     

An Efficient Generation Method for Uniformly Distributed Random Numbers

The problem of constructing efficient methods for generating uniformly distributed random numbers from nonuniformly distributed ones with a given arbitrarily small error is considered. An estimate of the complexity of these methods is given as a function of the error, which is measured as the deviation of numbers generated from uniformly distributed. Methods whose complexity is lower in order than that of known methods are proposed.     

双私钥双随机数认证方案

计算机网络是一个开放的系统,也正是由于其开放性导致计算机网络中存在相当多的安全漏洞和安全威胁,网络中的各类资源很容易被人非法访问和复制.因此对网络资源访问者的合法身份进行认证就显得非常重要.1981年,Lamport提出了一种基于密码表的用户认证方案.此方案可以抵抗重传攻击,然而,当存储在主机的口令一旦遭到攻击者的攻击,方案将无任何安全可言.智能卡可以作为一种更有效的用以认证身份的个人持有物,许多基于智能卡的认证方案被提出.首先对Das的双线性对身份认证方案进行了详细分析,针对其存在时钟同步问题,易遭受伪造攻击等安全隐患,提出了一种基于双线性对并利用智能卡完成的交互认证方案.为防止在认证过程中被伪造攻击,提出双私钥双随机数的方法,增强了认证系统的安全性,可安全地完成用户和远程系统间的交互认证.