The k-Diameter of a Kind of Circulant Graph

The diameter of a graph G is the maximal distance between pairs of vertices of G. When a network is modeled as a graph, diameter is a measurement for maximum transmission delay. The k-diameter dk(G) of a graph G, which deals with k internally disjoint paths between pairs of vertices of G, is a extension of the diameter of G. It has widely studied in graph theory and computer science. The circulant graph is a group-theoretic model of a class of symmetric interconnection network. Let Cn(i, n/2) be a circulant graph of order n whose spanning elements are i and n/2, where n4 and n is even. In this paper, the diameter, 2-diameter and 3-diameter of the Cn(i, n/2) are all obtained if gcd(n,i)=1, where the symbol gcd(n,i) denotes the maximum common divisor of n and i.     

k-Diameter of Circulant Graph with Degree 3

Parameters k-distance and k-diameter are extension of the distance and the diameter in graph theory. In this paper, the k-distance dk(x,y) between the any vertices x and y is first obtained in a connected circulant graph G with order n(n is even) and degree 3 by removing some vertices from the neighbour set of the x. Then, the k-diameters of the connected circulant graphs with order n and degree 3 are given by using the k-diameter dk(x,y).     

k-Diameter of Circulant Graph with Degree 3

Parameters k-distance and k-diameter are extension of the distance and the diameter in graph theory. In this paper, the k-distance dk （x,y） between the any vertices x and y is first obtained in a connected circulant graph G with order n （n is even） and degree 3 by removing some vertices from the neighbour set of the x. Then, the k-diameters of the connected circulant graphs with order n and degree 3 are given by using the k-diameter dk （x,y）.     

Total Coloring of G×Pn and G×Cn

It is proved that if G is a (△+1)-colorable graph, so are the graphs G×Pn and C×Cn, where Pn and Cn are respectively the path and cycle with n vertices, and △ the maximum edge degree of the graph. The exact chromatic numbers of the product graphs Pr1×Pr1×...×Prn× and C3k×C2m1×C2m2×...×C2mn are also presented. Thus the total coloring conjecture is proved to be true for many other graphs.     

Maximizing the Mean Number of Communicating Vertex Pairs in Series-Parallel Networks

A communication network can be modelled as a probabilistic graph where each of b edges represents a communication line and each of n vertices represents a communication processor. Each edge e (vertex v) functions with probability Pe (pv). If edges fail independently with uniform probability p and vertices do not fail, the probability that the network is connected is the probabilistic connectedness and is a standard measure of network reliability. The most reliable maximal series-parallel networks by this measure are those with exactly two vertices of degree two. However, as p becomes small, or n becomes large, the probability that even the most reliable series-parallel network is connected falls very quickly. Therefore, we wish to optimize a network with respect to another reliability measure, mean number of communicating vertex pairs. Experimental results suggest that this measure varies with p, with the diameter of the network, and with the number of minimum edge cutsets. We show that for large p, the most reliable series-parallel network must have the fewest minimum edge cutsets and for small p, the most reliable network must have maximum pairs of adjacent edges. We present a construction which incrementally inproves the communicating vertex pair mean for many networks and demonstrates that a fan maximizes this measure over maximal series parallel networks with exactly two edge cutsets of size two.     

(k,l)-递归极大平面图的结构

对于一个平面图G实施扩3-轮运算是指在G的某个三角形面xyz内添加一个新顶点v,使v与x, y, z均相邻,最后得到一个阶为|V(G)|+1的平面图的过程。一个递归极大平面图是指从平面图K₄出发,逐次实施扩3-轮运算而得到的极大平面图。 所谓一个(k,l)-递归极大平面图是指一个递归极大平面图,它恰好有k个度为3的顶点,并且任意两个3度顶点之间的距离均为l。该文对(k,l)-递归极大平面图的存在性问题做了探讨,刻画了(3,2)-及(2,3)-递归极大平面图的结构。     

On the capacity of network coding for random networks

We study the maximum flow possible between a single-source and multiple terminals in a weighted random graph (modeling a wired network) and a weighted random geometric graph (modeling an ad-hoc wireless network) using network coding. For the weighted random graph model, we show that the network coding capacity concentrates around the expected number of nearest neighbors of the source and the terminals. Specifically, for a network with a single source, l terminals, and n relay nodes such that the link capacities between any two nodes is independent and identically distributed (i.i.d.) /spl sim/X, the maximum flow between the source and the terminals is approximately nE[X] with high probability. For the weighted random geometric graph model where two nodes are connected if they are within a certain distance of each other we show that with high probability the network coding capacity is greater than or equal to the expected number of nearest neighbors of the node with the least coverage area.     

Generalized Kasami Sequences: The Large Set

In this correspondence, new binary sequence families F^k of period 2ⁿ-1 are constructed for even n and any k with gcd(k,n)=2 if n/2 is odd or gcd(k,n)=1 if n/2 is even. The distribution of their correlation values is completely determined. These families have maximum correlation 2^n/2+1 and family size 2^3n/2 + 2^n/2 for odd n/2 or 2^3n/2+2^n/2-1 for even n/2. The proposed families include the large set of Kasami sequences, where the k is taken as k=n/2+1.     

求二部图的最大匹配图的一种算法

 一个图的最大匹配图是以这个图的最大匹配集作为顶点集,两个顶点相邻当且仅当这两个最大匹配恰有一条边不同.本文首先对Gallai Edmonds结构定理中的三部分顶点在二部图中进行了详细刻画.然后讨论了构造最大匹配图问题的计算复杂性.最后深入研究了二部图最大匹配图的结构性质并给出了构造二部图的最大匹配图的一种算法.     

L(j, k)-Labelings of Kronecker Products of Complete Graphs

For positive integers j ges k, an L(j, k)-labeling of a graph G is an integer labeling of its vertices such that adjacent vertices receive labels that differ by at least j and vertices that are distance two apart receive labels that differ by at least k. We determine lambda^j _k(G) for the case when G is a Kronecker product of finitely many complete graphs, where there are certain conditions on j and k. Areas of application include frequency allocation to radio transmitters.     

Class of Hamiltonian-partitionable networks

It is shown that, if the graph G of a network N is the sum of n Hamiltonian circuits, the product G×G of G with itself is the sum of 2n Hamiltonian circuits. For example, C×C, where C is a circuit, is the sum of two Hamiltonian circuits, and K2n+1×K2n+1, where K2n+1 is the complete graph of order 2n+1, is the sum of 2n such circuits.     

Topology Management in Directional Antenna-Equipped Ad Hoc Networks

With fully directional communications, nodes must track the positions of their neighbors so that communication with these neighbors is feasible when needed. Tracking process introduces an overhead, which increases with the number of discovered neighbors. The overhead can be reduced if nodes maintain only a subset of their neighbors; however, this may increase the length of paths between node pairs in the network. In this work, we study the tradeoffs between node degree and path stretch. We first design a topology control algorithm to optimize this tradeoff. Assuming that nodes communicate with their directional neighbors using circular directional transmissions, we model the original graph as a unit disk graph (UDG). Given a UDG G, our algorithm finds a sparse subgraph G' with a maximum degree of 6, and connecting each node pair u,v by a path of length hops_{G'}(u,v)=O(hops_G(u,v)+logDelta), where Delta is the maximum degree in G, hops_{G}(u,v) denotes length of the shortest path between u, v in G. We show that this result is near-optimal. Based on the insights gained from this design, we next construct a simpler, more practical scheme that integrates fully-directional neighbor discovery and maintenance with topology control strategy. We simulate both algorithms and compare their performances.     

Nonlinear Index Coding Outperforming the Linear Optimum

The following source coding problem was introduced by Birk and Kol: a sender holds a word x isin {0, 1}ⁿ, and wishes to broadcast a codeword to n receivers, R_n,..., R_n. The receiver R_i is interested in x_i, and has prior side information comprising some subset of the n bits. This corresponds to a directed graph G on n vertices, where i j is an edge R_i Ri knows the bit x_j. An index code for G is an encoding scheme which enables each Ri to always reconstruct x_i, given his side information. The minimal word length of an index code was studied by Bar-Yossef, Birk, Jayram, and Kol (FOCS'06). They introduced a graph parameter, minrk₂(G), which completely characterizes the length of an optimal linear index code for G. They showed that in various cases linear codes attain the optimal word length, and conjectured that linear index coding is in fact always optimal. In this work, we disprove the main conjecture of Bar-Yossef, Birk, Jayram, and Kol in the following strong sense: for any epsiv > 0 and sufficiently large n, there is an n-vertex graph G so that every linear index code for G requires codewords of length at least n^epsiv and yet a nonlinear index code for G has a word length of ne. This is achieved by an explicit construction, which extends Alon's variant of the celebrated Ramsey construction of Frankl and Wilson. In addition, we study optimal index codes in various, less restricted, natural models, and prove several related properties of the graph parameter minrk(G).     

The forwarding index of communication networks

A network is defined as an undirected graph and a routing which consists of a collection of simple paths connecting every pair of vertices in the graph. The forwarding index of a network is the maximum number of paths passing through any vertex in the graph. Thus it corresponds to the maximum amount of forwarding done by any node in a communication network with a fixed routing. For a given number of vertices, each having a given degree constraint, we consider the problem of finding networks that minimize the forwarding index. Forwarding indexes are calculated' for cube networks and generalized de Bruijn networks. General bounds are derived which show that de Bruijn networks are asymptotically optimal. Finally, efficient techniques for building large networks with small forwarding indexes out of given component networks are presented and analyzed.     

Decomposition constructions for secret-sharing schemes

The paper describes a very powerful decomposition construction for perfect secret-sharing schemes. The author gives several applications of the construction and improves previous results by showing that for any graph G of maximum degree d, there is a perfect secret-sharing scheme for G with information rate 2/(d+1). As a corollary, the maximum information rate of secret-sharing schemes for paths on more than three vertices and for cycles on more than four vertices is shown to be 2/3     

The Maximum Throughput of A Wireless Multi-Hop Path

In this paper, the maximum end-to-end throughput that can be achieved on a wireless multi-hop path is investigated analytically. The problem is modeled using the conflict graph, where each link in the multi-hop path is represented uniquely by a vertex in the conflict graph and two vertices are adjacent if and only if the associated links mutually interfere. Using the conflict graph and the linear programming formulations of the problem, we analyzed the maximum end-to-end throughput of a wireless multi-hop path a) in a simple scenario where nodes are optimally placed and each node can only interfere with the transmission of its adjacent nodes along the path, and b) in a more complicated scenario where nodes are randomly placed and each node can interfere with the transmission of any number of nearby nodes along the path in both a) an error free radio environment and b) an erroneous radio environment. The maximum end-to-end throughputs for each of the above four scenarios are obtained analytically. We show that the maximum achievable end-to-end throughput is determined by the throughput of its bottleneck clique, where a clique is a maximal set of mutually adjacent vertices in the associated conflict graph. Further our analysis suggests the optimum scheduling algorithm that can be used to achieve the maximum end-to-end throughput and that it is convenient to use the (maximal) independent sets as the basic blocks for the design of scheduling algorithms. The findings in this paper lay guidelines for the design of optimum scheduling algorithms. They can be used to design computationally efficient algorithms to determine the maximum throughput of a wireless multi-hop path and to design a scheduling algorithm to achieve that throughput.     

图的最大权团的DNA计算

给定顶点赋权的无向图,图的最大权团问题是寻找每个顶点都相邻的顶点子集(团)具有最大权.这个问题是寻找无权图的最大团问题的推广.图的最大团和最大权团都是著名的NP-完全问题,没有非常有效的算法.1994年Adleman博士首先提出用DNA计算解决NP-完全问题,使得NP-完全问题的求解可能得到解决.本文给出了基于质粒技术的无向图的最大权团问题的DNA算法,依据Head T等的实验手段,本文提出的算法是有效并且可行的.     

分析方法在Ramsey数估值中的应用

“Yusheng等人曾给出-个独立数的下界公式：α（G）≥Nfa＋1（d）,其中fa（x）=∫0^1（1-t）1/a dt/（a＋（x-a）·t）。为了得到r（H,Kn）的上界,可以考虑建立不合H作为子图的临界图G的独立数的下界。即通过对临界图G及其邻域导出子图e的平均次数的分析,得出G的阶（顶点数）Ⅳ与n之间的不等式关系。再利用函数五（x）的分析性质得出当n趋于无穷大时,N＋1的最小可能渐近表达式,即为r（H,Kn）的渐近上界。主要介绍这种分析方法在解决Kk＋Kt,“K1＋Cm”,“Km．t”等图形和完全图Ramsey数渐近上界问题中的应用。     

Three-step heuristic algorithm for optimal PLA column folding

A three-step heuristic algorithm for PLA column folding is presented, which is significantly faster than the earlier works and provides nearly optimal results. The three steps are: (i) min-cut partition of vertices in the column intersection graph; (ii) determination of product order using Fiduccia's min-net cut algorithm; and (iii) head-tail pairing for deciding column folding pairs