几类有趣图的奇优美性和奇强协调性

对于简单图G=〈V,E〉,如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1}满足:1)对任意的u,v∈V,若u≠v,则f(u)≠f(v);2)max{f(v)|v∈V}=2|E|-1;3)对任意的e_1,e_2∈E,若e_1≠e_2,则g(e_1)≠g(e_2),此处g(e)=|f(u)+f(v)|,e=uv;4)|g(e)|e∈E}={1,3,5,…,2|E|-1},则称G为奇优美图,f称为G的奇优美标号.设G=〈V,E〉是一个无向简单图.如果存在一个映射f:V(G)→{0,1,2,…,2|E|-1},满足:1)f是单射;2)■uv∈E(G),令f(uv)=f(u)+f(v),有{f(uv)|uv∈E(G)}={1,3,5,…,2|E|-1},则称G是奇强协调图,f称为G的.奇强协调标号或奇强协调值.给出了链图、升降梯等几类有趣图的奇优美标号和奇强协调标号.     

关于P_(r,(2s-1))的奇优美标号

对于简单图G=〈V,E〉,如果存在一个映射f:V(G)→{0,1,2,…,2 |E|-1}满足1)对任意的u,v∈V,若u≠v,则(u)≠f(v);2)max{f(v)|v∈V}=2|E|-1;3)对任意的e_1,e_2∈E,若e_1≠e_2,则g(e_1)≠g(e_2),此处g(e)=|f(u)+f(v)|,e=uv;4){g(e)|e∈E}={1,3,5,…,2|E|-1},则称G是奇优美图,f称为G的奇优美标号.Gnanajoethi提出了一个猜想:每棵树都是奇优美的.证明了图P_(r,(2s-1)是奇优美图.     

伪完全二分图PK_(n,n)奇优美标号的计算机实现

给出了伪完全二分图PK_(n,n)的定义及性质,提出了该类图的奇优美标号算法,证明了算法的正确性及时间复杂度,从而证明了伪完全二分图的奇优美性.并给出了伪完全二分图PK_(n,n),当n=3,4,5的一种标号方法.     

探讨斐波纳契对虾树的优美性

具有完美匹配M的n阶树T是强优美的,如果对任意uv∈M,存在树T的一个优美标号f,使得f(u)+f(u)=n-1.给出了二分奇优美树和强优美树的概念,证明了斐波纳契对虾树是二分奇优美和强优美树.     

图P^3n的奇优美标号算法

本文讨论了图P^3n的奇优美性,给出了图只奇优美标号算法．     

探索金鱼图的奇优美性

给出了奇优美图和二分奇优美图的概念,并定义了金鱼图,证明了在鱼头为不同图形的情况下,金鱼图仍然是奇优美的,且是二分奇优美的.还证明了:对一个奇优美图H和一棵二分奇优美树T,用一条边连接T的一个顶点和H的标号基点u_0后所得到的金鱼图仍是奇优美图.     

灯笼图的奇优美标号

提出了灯笼图、多向灯笼图、复杂灯笼图,研究了它们的奇优美性,证明灯笼图是二分奇优美图、超级边魔幻图和超级反魔幻图.     

积图P_n×P_m的奇优美性和奇强协调性

给出了积图P_n×P_m的奇优美标号和奇强协调标号.     

具有匹配对网络模型的优美性

在当今网络研究中,人们需要将某些特殊的图分解为指定的结构.优美图可以被运用到图分解中.得到一些构造优美图的可算法化的方法,并构造较为复杂的优美图.     

几类有向图的奇优美标号

给出了有向奇优美图的定义并讨论了直径较小的、特殊图类的有向图的奇优美标号,得到了一些相关结论和猜想.     

(向量)R_n和(向量)G_n的有向优美性

优美图可用在图论中的某些H-分解问题中,很多人研究无向图的优美标号.研究有向优美标号,通过对阶数奇偶性的讨论,给出了n(≥2)阶有向路(向量)P_n和n(≥3)阶有向(向量)C_n圈是有向优美的充分条件.     

探讨几类具有完全图核心的网络模型的优美性

在复杂网络研究中,人们需要建立网络模型,无标度图就是这样的一种网络模型.我们发现具有完全图核心的网络模型可以演变成无标度图.具有完全图核心的几种网络模型的优美性得到研究.     

Complexity of networks I: The set‐complexity of binary graphs

The balance between symmetry and randomness as a property of networks can be viewed as a kind of “complexity.” We use here our previously defined “set complexity” measure (Galas et al., IEEE Trans Inf Theory 2010, 56), which was used to approach the problem of defining biological information, in the mathematical analysis of networks. This information theoretic measure is used to explore the complexity of binary, undirected graphs. The complexities, Ψ, of some specific classes of graphs can be calculated in closed form. Some simple graphs have a complexity value of zero, but graphs with significant values of Ψ are rare. We find that the most complex of the simple graphs are the complete bipartite graphs (CBGs). In this simple case, the complexity, Ψ, is a strong function of the size of the two node sets in these graphs. We find the maximum Ψ binary graphs as well. These graphs are distinct from, but similar to CBGs. Finally, we explore directed and stochastic processes for growing graphs (hill‐climbing and random duplication, respectively) and find that node duplication and partial node duplication conserve interesting graph properties. Partial duplication can grow extremely complex graphs, while full node duplication cannot do so. By examining the eigenvalue spectrum of the graph Laplacian we characterize the symmetry of the graphs and demonstrate that, in general, breaking specific symmetries of the binary graphs increases the set‐based complexity, Ψ. The implications of these results for more complex, multiparameter graphs, and for physical and biological networks and the processes of network evolution are discussed. © 2011 Wiley Periodicals, Inc. Complexity, 17,51–64, 2011     

Complexity of networks II: The set complexity of edge‐colored graphs

We previously introduced the concept of “set‐complexity,” based on a context‐dependent measure of information, and used this concept to describe the complexity of gene interaction networks. In a previous paper of this series we analyzed the set‐complexity of binary graphs. Here, we extend this analysis to graphs with multicolored edges that more closely match biological structures like the gene interaction networks. All highly complex graphs by this measure exhibit a modular structure. A principal result of this work is that for the most complex graphs of a given size the number of edge colors is equal to the number of “modules” of the graph. Complete multipartite graphs (CMGs) are defined and analyzed. The relation between complexity and structure of these graphs is examined in detail. We establish that the mutual information between any two nodes in a CMG can be fully expressed in terms of entropy, and present an explicit expression for the set complexity of CMGs (Theorem 3). An algorithm for generating highly complex graphs from CMGs is described. We establish several theorems relating these concepts and connecting complex graphs with a variety of practical network properties. In exploring the relation between symmetry and complexity we use the idea of a similarity matrix and its spectrum for highly complex graphs. © 2012 Wiley Periodicals, Inc. Complexity, 2012     

Modularity in random regular graphs and lattices

Given a graph G, the modularity of a partition of the vertex set measures the extent to which edge density is higher within parts than between parts; and the modularity of G is the maximum modularity of a partition.We give an upper bound on the modularity of r-regular graphs as a function of the edge expansion (or isoperimetric number) under the restriction that each part in our partition has a sub-linear numbers of vertices. This leads to results for random r-regular graphs. In particular we show the modularity of a random cubic graph partitioned into sub-linear parts is almost surely in the interval (0.66, 0.88).The modularity of a complete rectangular section of the integer lattice in a fixed dimension was estimated in Guimer et. al. [R. Guimerà, M. Sales-Pardo and L.A. Amaral, Modularity from fluctuations in random graphs and complex networks, Phys. Rev. E 70 (2) (2004) 025101]. We extend this result to any subgraph of such a lattice, and indeed to more general graphs.     

Stochastic kronecker graphs

A random graph model based on Kronecker products of probability matrices has been recently proposed as a generative model for large‐scale real‐world networks such as the web. This model simultaneously captures several well‐known properties of real‐world networks; in particular, it gives rise to a heavy‐tailed degree distribution, has a low diameter, and obeys the densification power law. Most properties of Kronecker products of graphs (such as connectivity and diameter) are only rigorously analyzed in the deterministic case. In this article, we study the basic properties of stochastic Kronecker products based on an initiator matrix of size two (which is the case that is shown to provide the best fit to many real‐world networks). We will show a phase transition for the emergence of the giant component and another phase transition for connectivity, and prove that such graphs have constant diameters beyond the connectivity threshold, but are not searchable using a decentralized algorithm. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 38, 453–466, 2011     

Distance and routing labeling schemes for non-positively curved plane graphs

Distance labeling schemes are schemes that label the vertices of a graph with short labels in such a way that the distance between any two vertices u and v can be determined efficiently (e.g., in constant or logarithmic time) by merely inspecting the labels of u and v, without using any other information. Similarly, routing labeling schemes are schemes that label the vertices of a graph with short labels in such a way that given the label of a source vertex and the label of a destination, it is possible to compute efficiently (e.g., in constant or logarithmic time) the port number of the edge from the source that heads in the direction of the destination. In this paper we show that the three major classes of non-positively curved plane graphs enjoy such distance and routing labeling schemes using O(log²n) bit labels on n-vertex graphs. In constructing these labeling schemes interesting metric properties of those graphs are employed.     

小度数循环图的计数

循环图已被用于平行计算，网络等方面．循环图研究的一个基本问题是对互不同构的循环图进行计数．对于给定的一个正整数ｎ，用Ｃ（ｎ，ｋ）表示互不同构的具有几个顶点，度数为ｋ的连通循环图的个数．文中给出了度数为 ４和５的循环图的一般结构，并对ｎ＝ｐａｑｂ（ｐ，ｑ皆为素数，ａ，ｂ＞０），给出了Ｃ（ｎ，４）的计算公式．