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).     

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.     

The k-Diameter of a Kind of Circulant Graph

The terminology and notion in this paper are similar to Ref.[1], all graphs discussed here are finite and simple. The diameter d(G) of a graph G is the maximal distance between pairs of vertices of G. The connectivity of G is the minimum number of vertices needed to be removed in order to disconnect the graph. When a network is modeled as a graph,a vertex represents a node of processor (or a station) and an edge between two vertices is the link (or connection) between those two processors. I…     

(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)-递归极大平面图的结构。     

An extension of the channel-assignment problem: L(2, 1)-labelings of generalized Petersen graphs

The channel-assignment problem involves assigning frequencies represented by nonnegative integers to radio transmitters such that transmitters in close proximity receive frequencies that are sufficiently far apart to avoid interference. In one of its variations, the problem is commonly quantified as follows: transmitters separated by the smallest unit distance must be assigned frequencies that are at least two apart and transmitters separated by twice the smallest unit distance must be assigned frequencies that are at least one apart. Naturally, this channel-assignment problem can be modeled with vertex labelings of graphs. An L(2, 1)-labeling of a graph G is a function f from the vertex set V(G) to the nonnegative integers such that |f(x)-f(y)|/spl ges/2 if d(x,y)=1 and |f(x)-f(y)|/spl ges/1 if d(x,y)=2. The /spl lambda/-number of G, denoted /spl lambda/(G), is the smallest number k such that G has an L(2, 1)-labeling using integers from {0,1,...,k}. A long-standing conjecture by Griggs and Yeh stating that /spl lambda/(G) can not exceed the square of the maximum degree of vertices in G has motivated the study of the /spl lambda/-numbers of particular classes of graphs. This paper provides upper bounds for the /spl lambda/-numbers of generalized Petersen graphs of orders 6, 7, and 8. The results for orders 7 and 8 establish two cases in a conjecture by Georges and Mauro, while the result for order 6 improves the best known upper bound. Furthermore, this paper provides exact values for the /spl lambda/-numbers of all generalized Petersen graphs of order 6.     

The L(2,1)-labeling and operations of graphs

Motivated by a variation of the channel assignment problem, a graph labeling analogous to the graph vertex coloring has been presented and is called an L(2,1)-labeling. More precisely, an L(2,1)-labeling of a graph G is a function f from the vertex set V(G) to the set of all nonnegative integers such that |f(x)-f(y)| /spl ges/ 2 if d(x,y)=1 and |f(x)-f(y)| /spl ges/ 1 if d(x,y) = 2. The L(2,1)-labeling number /spl lambda/(G) of G is the smallest number k such that G has an L(2,1)-labeling with max{f(v):v/spl isin/V(G)}=k. A conjecture states that /spl lambda/(G) /spl les/ /spl Delta//sup 2/ for any simple graph with the maximum degree /spl Delta//spl ges/2. This paper considers the graphs formed by the Cartesian product and the composition of two graphs. The new graph satisfies the conjecture above in both cases(with minor exceptions).     

分析方法在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数渐近上界问题中的应用。     

Identifying and locating-dominating codes: NP-completeness results for directed graphs

Let G=(V, A) be a directed, asymmetric graph and C a subset of vertices, and let B/sub r//sup -/(v) denote the set of all vertices x such that there exists a directed path from x to v with at most r arcs. If the sets B/sub r//sup -/(v) /spl cap/ C, v /spl isin/ V (respectively, v /spl isin/ V/spl bsol/C), are all nonempty and different, we call C an r-identifying code (respectively, an r-locating-dominating code) of G. In other words, if C is an r-identifying code, then one can uniquely identify a vertex v /spl isin/ V only by knowing which codewords belong to B/sub r//sup -/(v), and if C is r-locating-dominating, the same is true for the vertices v in V/spl bsol/C. We prove that, given a directed, asymmetric graph G and an integer k, the decision problem of the existence of an r-identifying code, or of an r-locating-dominating code, of size at most k in G, is NP-complete for any r/spl ges/1 and remains so even when restricted to strongly connected, directed, asymmetric, bipartite graphs or to directed, asymmetric, bipartite graphs without directed cycles.     

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.     

Grid Colorings in Steganography

A proper vertex coloring of a graph is called rainbow if, for each vertex v, all neighbors of v receive distinct colors. A k-regular graph G is called rainbow (or domatically full) if it admits a rainbow (k+1)-coloring. The d-dimensional grid graph G_d is the graph whose vertices are the points of Zopf^d and two vertices are adjacent if and only if their l₁-distance is 1. We use a simple construction to prove that G_d is rainbow for all d ges 1. We discuss an important application of this result in steganography     

Generation of vertex connected subgraphs for multi-input multi-output reliability networks

In this paper, the problem of evaluation of reliability (probability of success) of a network consisting of several inputs and outputs is studied. Edges are assumed to be perfect and vertices are assigned the probabilities of success. A new concept called “vertex connected subgraph” is introduced for this purpose. This concept is useful even for dense graphs because they are of the order of 2^(v-k-1) which is independent of e, where ν(e) is the number of vertices (edges) and k is the number of outputs of a graph.     

Secret-Sharing Schemes for Very Dense Graphs

A secret-sharing scheme realizes a graph if every two vertices connected by an edge can reconstruct the secret while every independent set in the graph does not get any information on the secret. Similar to secret-sharing schemes for general access structures, there are gaps between the known lower bounds and upper bounds on the share size for graphs. Motivated by the question of what makes a graph “hard” for secret-sharing schemes (that is, they require large shares), we study very dense graphs, that is, graphs whose complement contains few edges. We show that if a graph with \(n\) vertices contains \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) -n^{1+\beta }\) edges for some constant \(0 \le \beta <1\), then there is a scheme realizing the graph with total share size of \(\tilde{O}(n^{5/4+3\beta /4})\). This should be compared to \(O(n^2/\log (n))\), the best upper bound known for the total share size in general graphs. Thus, if a graph is “hard,” then the graph and its complement should have many edges. We generalize these results to nearly complete \(k\)-homogeneous access structures for a constant \(k\). To complement our results, we prove lower bounds on the total share size for secret-sharing schemes realizing very dense graphs, e.g., for linear secret-sharing schemes, we prove a lower bound of \(\Omega (n^{1+\beta /2})\) for a graph with \(\left( {\begin{array}{c}n\\ 2\end{array}}\right) -n^{1+\beta }\) edges.     

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.     

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.     

关于无重复分解产生树的定理

本文定义了一种二分图,称之为互补划分图。利用此图容易证明有关互补划分的定理,并可得到一个判别是否是本性互补划分的较弱的条件。     

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     

可k—重图序列的充要条件与实现算法

每对顶点之间至多有Ｋ条边相连接且无自环的图称为Ｋ－重图；一个非负整数序列π＝（ｄ１，ｄ２……，ｄｐ）称为可Ｋ－重图序列的，如果存在某个Ｋ－重图Ｇ，使得它的度序列π（Ｇ）＝π。本文对于可Ｋ－重图序列的基本特性进行了为详细地研究。引入一种称为向量与正整数的减法运算，并对这种运算的基本性质进行了详细地研究。在此基础上获得一个非负整数序列π＝（ｄ１，ｄ２……，ｄｐ）是可Ｋ－重图的充要条件；进而给出了可Ｋ－     

Performance analysis of grammar-based codes revisited

The compression performance of grammar-based codes is revisited from a new perspective. Previously, the compression performance of grammar-based codes was evaluated against that of the best arithmetic coding algorithm with finite contexts. In this correspondence, we first define semifinite-state sources and finite-order semi-Markov sources. Based on the definitions of semifinite-state sources and finite-order semi-Markov sources, and the idea of run-length encoding (RLE), we then extend traditional RLE algorithms to context-based RLE algorithms: RLE algorithms with k contexts and RLE algorithms of order k, where k is a nonnegative integer. For each individual sequence x, let r/sup *//sub sr,k/(x) and r/sup *//sub sr|k/(x) be the best compression rate given by RLE algorithms with k contexts and by RLE algorithms of order k, respectively. It is proved that for any x, r/sup *//sub sr,k/ is no greater than the best compression rate among all arithmetic coding algorithms with k contexts. Furthermore, it is shown that there exist stationary, ergodic semi-Markov sources for which the best RLE algorithms without any context outperform the best arithmetic coding algorithms with any finite number of contexts. Finally, we show that the worst case redundancies of grammar-based codes against r/sup *//sub sr,k/(x) and r/sup *//sub sr|k/(x) among all length- n individual sequences x from a finite alphabet are upper-bounded by d/sub 1/loglogn/logn and d/sub 2/loglogn/logn, respectively, where d/sub 1/ and d/sub 2/ are constants. This redundancy result is stronger than all previous corresponding results.     

一种计算Ad hoc网络K-终端可靠性的线性时间算法

研究计算Ad hoe网络K-终端可靠性的线性时间算法,可以快速计算Ad hoe网络K-终端可靠性。为了计算Ad hoe网络分级结构尽终端可靠性,可以采用无向概率图表示Ad hoe网络的分级结构。每个簇头由已知失效率的结点表示,并且当且仅当两个簇相邻时,两个结点间的互连由边表示。这个概率图的链路完全可靠,并且已知结点的失效率。此图的K-终端可靠性为给定K-结点集是互连的概率。文中提出了基于合适区间图计算尽终端可靠性的一种线性时间算法。本算法可用来计算Ad hoe网络的K-终端可靠性。其时间复杂度为O（｜V｜＋｜E｜）。     

The empirical distribution of rate-constrained source codes

Let X = (X/sub 1/,...) be a stationary ergodic finite-alphabet source, X/sup n/ denote its first n symbols, and Y/sup n/ be the codeword assigned to X/sup n/ by a lossy source code. The empirical kth-order joint distribution Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rceil/(x/sup k/,y/sup k/) is defined as the frequency of appearances of pairs of k-strings (x/sup k/,y/sup k/) along the pair (X/sup n/,Y/sup n/). Our main interest is in the sample behavior of this (random) distribution. Letting I(Q/sup k/) denote the mutual information I(X/sup k/;Y/sup k/) when (X/sup k/,Y/sup k/)/spl sim/Q/sup k/ we show that for any (sequence of) lossy source code(s) of rate /spl les/R lim sup/sub n/spl rarr//spl infin//(1/k)I(Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rfloor/) /spl les/R+(1/k)H (X/sub 1//sup k/)-H~(X) a.s. where H~(X) denotes the entropy rate of X. This is shown to imply, for a large class of sources including all independent and identically distributed (i.i.d.). sources and all sources satisfying the Shannon lower bound with equality, that for any sequence of codes which is good in the sense of asymptotically attaining a point on the rate distortion curve Q/spl circ//sup k/[X/sup n/,Y/sup n//spl rfloor//spl rArr//sup d/P(X/sup k/,Y~/sup k/) a.s. whenever P(/sub X//sup k//sub ,Y//sup k/) is the unique distribution attaining the minimum in the definition of the kth-order rate distortion function. Consequences of these results include a new proof of Kieffer's sample converse to lossy source coding, as well as performance bounds for compression-based denoisers.