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 /spl Delta//sup 2/-conjecture for L(2,1)-labelings is true for direct and strong products of graphs

A variation of the channel-assignment problem is naturally modeled by L(2,1)-labelings of graphs. An L(2,1)-labeling of a graph G is an assignment of labels from {0,1,...,/spl lambda/} to the vertices of G such that vertices at distance two get different labels and adjacent vertices get labels that are at least two apart and the /spl lambda/-number /spl lambda/(G) of G is the minimum value /spl lambda/ such that G admits an L(2,1)-labeling. The /spl Delta//sup 2/-conjecture asserts that for any graph G its /spl lambda/-number is at most the square of its largest degree. In this paper it is shown that the conjecture holds for graphs that are direct or strong products of nontrivial graphs. Explicit labelings of such graphs are also constructed.     

Compression mappings on primitive sequences over Z/(p/sup e/)

Let Z/(p/sup e/) be the integer residue ring with odd prime p/spl ges/5 and integer e/spl ges/2. For a sequence a_ over Z/(p/sup e/), there is a unique p-adic expansion a_=a_/sub 0/+a_/spl middot/p+...+a_/sub e-1//spl middot/p/sup e-1/, where each a_/sub i/ is a sequence over {0,1,...,p-1}, and can be regarded as a sequence over the finite field GF(p) naturally. Let f(x) be a primitive polynomial over Z/(p/sup e/), and G'(f(x),p/sup e/) the set of all primitive sequences generated by f(x) over Z/(p/sup e/). Set /spl phi//sub e-1/ (x/sub 0/,...,x/sub e-1/) = x/sub e-1//sup k/ + /spl eta//sub e-2,1/(x/sub 0/, x/sub 1/,...,x/sub e-2/) /spl psi//sub e-1/(x/sub 0/,...,x/sub e-1/) = x/sub e-1//sup k/ + /spl eta//sub e-2,2/(x/sub 0/,x/sub 1/,...,x/sub e-2/) where /spl eta//sub e-2,1/ and /spl eta//sub e-2,2/ are arbitrary functions of e-1 variables over GF(p) and 2/spl les/k/spl les/p-1. Then the compression mapping /spl phi//sub e-1/:{G'(f(x),p/sup e/) /spl rarr/ GF(p)/sup /spl infin// a_ /spl rarr/ /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) is injective, that is, a_ = b_ if and only if /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) = /spl phi//sub e-1/(b_/sub 0/,...,b_/sub e-1/) for a_,b_ /spl isin/ G'(f(x),p/sup e/). Furthermore, if f(x) is a strongly primitive polynomial over Z/(p/sup e/), then /spl phi//sub e-1/(a_/sub 0/,...,a_/sub e-1/) = /spl psi//sub e-1/(b_/sub 0/,...,b_/sub e-1/) if and only if a_ = b_ and /spl phi//sub e-1/(x/sub 0/,...,x/sub e-1/) = /spl psi//sub e-1/(x/sub 0/,...,x/sub e-1/) for a_,b_ /spl isin/ G'(f(x),p/sup e/).     

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.     

Improved Bounds on the $L(2,1)$-Number of Direct and Strong Products of Graphs

The frequency assignment problem is to assign a frequency which is a nonnegative integer to each radio transmitter so that interfering transmitters are assigned frequencies whose separation is not in a set of disallowed separations. This frequency assignment problem can be modelled 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 set of all nonnegative integers such that $vert f(x)-f(y)vertgeq 2$ if $d(x,y)=1$ and $vert f(x)-f(y)vertgeq 1$ if $d(x,y)=2$ , where $d(x,y)$ denotes the distance between $x$ and $y$ in $G$. The $L(2,1)$ -labeling number $lambda(G)$ of $G$ is the smallest number $k$ such that $G$ has an $L(2,1)$-labeling with $max{f(v):vin V(G)}=k$. This paper considers the graph formed by the direct product and the strong product of two graphs and gets better bounds than those of KlavŽar and Špacapan with refined approaches.      

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.     

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

A nontrivial lower bound on the Shannon capacities of the complements of odd cycles

This article contains a construction for independent sets in the powers of the complements of odd cycles. In particular, we show that /spl alpha/(C~/sub 2n+3/(2/sup n/))/spl ges/2(2/sup n/)+1. It follows that for n/spl ges/0 we have /spl Theta/(C~/sub 2n+3/)>2, where /spl Theta/(G) denotes the Shannon (1956) capacity of graph G.     

Grammar-based lossless universal refinement source coding

A sequence y=(y/sub 1/,...,y/sub n/) is said to be a coarsening of a given finite-alphabet source sequence x=(x/sub 1/,...,x/sub n/) if, for some function /spl phi/, y/sub i/=/spl phi/(x/sub i/) (i=1,...,n). In lossless refinement source coding, it is assumed that the decoder already possesses a coarsening y of a given source sequence x. It is the job of the lossless refinement source encoder to furnish the decoder with a binary codeword B(x|y) which the decoder can employ in combination with y to obtain x. We present a natural grammar-based approach for finding the binary codeword B(x|y) in two steps. In the first step of the grammar-based approach, the encoder furnishes the decoder with O(/spl radic/nlog/sub 2/n) code bits at the beginning of B(x|y) which tell the decoder how to build a context-free grammar G/sub y/ which represents y. The encoder possesses a context-free grammar G/sub x/ which represents x; in the second step of the grammar-based approach, the encoder furnishes the decoder with code bits in the rest of B(x|y) which tell the decoder how to build G/sub x/ from G/sub y/. We prove that our grammar-based lossless refinement source coding scheme is universal in the sense that its maximal redundancy per sample is O(1/log/sub 2/n) for n source samples, with respect to any finite-state lossless refinement source coding scheme. As a by-product, we provide a useful notion of the conditional entropy H(G/sub x/|G/sub y/) of the grammar G/sub x/ given the grammar G/sub y/, which is approximately equal to the length of the codeword B(x|y).     

Minimum bias multiple taper spectral estimation

Two families of orthonormal tapers are proposed for multitaper spectral analysis: minimum bias tapers, and sinusoidal tapers {υ ^{(k/)}, where υ}sub n//sup (k/)=√(2/(N+1))sin(πkn/N+1), and N is the number of points. The resulting sinusoidal multitaper spectral estimate is Sˆ(f)=(1/2K(N+1))Σ_j=1^K |y(f+j/(2N+2))-y(f-j/(2N+2))|², where y(f) is the Fourier transform of the stationary time series, S(f) is the spectral density, and K is the number of tapers. For fixed j, the sinusoidal tapers converge to the minimum bias tapers like 1/N. Since the sinusoidal tapers have analytic expressions, no numerical eigenvalue decomposition is necessary. Both the minimum bias and sinusoidal tapers have no additional parameter for the spectral bandwidth. The bandwidth of the jth taper is simply 1/N centered about the frequencies (±j)/(2N+2). Thus, the bandwidth of the multitaper spectral estimate can be adjusted locally by simply adding or deleting tapers. The band limited spectral concentration, ∫_-w^w|V(f)|²df of both the minimum bias and sinusoidal tapers is very close to the optimal concentration achieved by the Slepian (1978) tapers. In contrast, the Slepian tapers can have the local bias, ∫_-½^½f ²|V(f)|²df, much larger than of the minimum bias tapers and the sinusoidal tapers     

Explicit construction of families of LDPC codes with no 4-cycles

Low-density parity-check (LDPC) codes are serious contenders to turbo codes in terms of decoding performance. One of the main problems is to give an explicit construction of such codes whose Tanner graphs have known girth. For a prime power q and m/spl ges/2, Lazebnik and Ustimenko construct a q-regular bipartite graph D(m,q) on 2q/sup m/ vertices, which has girth at least 2/spl lceil/m/2/spl rceil/+4. We regard these graphs as Tanner graphs of binary codes LU(m,q). We can determine the dimension and minimum weight of LU(2,q), and show that the weight of its minimum stopping set is at least q+2 for q odd and exactly q+2 for q even. We know that D(2,q) has girth 6 and diameter 4, whereas D(3,q) has girth 8 and diameter 6. We prove that for an odd prime p, LU(3,p) is a [p/sup 3/,k] code with k/spl ges/(p/sup 3/-2p/sup 2/+3p-2)/2. We show that the minimum weight and the weight of the minimum stopping set of LU(3,q) are at least 2q and they are exactly 2q for many LU(3,q) codes. We find some interesting LDPC codes by our partial row construction. We also give simulation results for some of our codes.     

High-speed (/spl ges/1 GHz) electrical and optical adding, mixing, and processing of square-wave signals with a transistor laser

This letter reports the common-emitter operation (gain /spl beta/=/spl Delta/I/sub C///spl Delta/I/sub B/>1, 20/spl deg/C, I/sub B/=36 mA, /spl lambda/=970 nm) of a dual-input transistor laser, arranged with a separate base contact on either side of a single emitter, that adds, mixes, and processes high-speed square-wave electrical inputs and delivers separate electrical and optical outputs. Applying a square-wave electrical input X/sub 1/(t) to one base contact and X/sub 2/(t) at a second base input, we obtain, with the pulsewidth modulated because of mixing, an electrical output proportional to /spl beta//spl times/[X/sub 1/(t)+X/sub 2/(t)] and a laser output tracking the electrical output (h/spl nu//spl times/f[X/sub 1/(t)+X/sub 2/(t)]) and exceeding it in bandwidth (pulse sharpness).     

Optimal linear identifying codes

Identifying codes can be used to locate malfunctioning processors. We say that a code C of length n is a linear (1,/spl les/l)-identifying code if it is a subspace of F/sub 2//sup n/ and for all X,Y/spl sube/F/sub 2//sup n/ such that |X|, |Y|/spl les/l and X/spl ne/Y, we have /spl cup//sub x/spl isin/X/(B(x)/spl cap/C)/spl ne//spl cup/y/spl isin/Y(B(y)/spl cap/C). Strongly (1,/spl les/l)-identifying codes are a variant of identifying codes. We determine the cardinalities of optimal linear (1,/spl les/l)-identifying and strongly (1,/spl les/l)-identifying codes in Hamming spaces of any dimension for locating any at most l malfunctioning processors.     

A note on density model size testing

Let (F/sub k/)/sub k/spl ges/1/ be a nested family of parametric classes of densities with finite Vapnik-Chervonenkis dimension. Let f be a probability density belonging to F/sub k//sup */, where k/sup */ is the unknown smallest integer such that f/spl isin/F/sub k/. Given a random sample X/sub 1/,...,X/sub n/ drawn from f, an integer k/sub 0//spl ges/1 and a real number /spl alpha//spl isin/(0,1), we introduce a new, simple, explicit /spl alpha/-level consistent testing procedure of the hypothesis {H/sub 0/:k/sup */=k/sub 0/} versus the alternative {H/sub 1/:k/sup *//spl ne/k/sub 0/}. Our method is inspired by the combinatorial tools developed in Devroye and Lugosi and it includes a wide range of density models, such as mixture models, neural networks, or exponential families.     

New class of nonlinear systematic error detecting codes

A code C detects error e with probability 1-Q(e),ifQ(e) is a fraction of codewords y such that y, y+e/spl isin/C. We present a class of optimal nonlinear q-ary systematic (n, q/sup k/)-codes (robust codes) minimizing over all (n, q/sup k/)-codes the maximum of Q(e) for nonzero e. We also show that any linear (n, q/sup k/)-code V with n /spl les/2k can be modified into a nonlinear (n, q/sup k/)-code C/sub v/ with simple encoding and decoding procedures, such that the set E={e|Q(e)=1} of undetected errors for C/sub v/ is a (k-r)-dimensional subspace of V (|E|=q/sup k-r/ instead of q/sup k/ for V). For the remaining q/sup n/-q/sup k-r/ nonzero errors, Q(e)/spl les/q/sup -r/for q/spl ges/3 and Q(e)/spl les/ 2/sup -r+1/ for q=2.     

Validity of the Kirchhoff approximation for electromagnetic wave scattering from fractal surfaces

Valid application of the Kirchhoff approximation (KA) for scattering from rough surfaces requires that the surface radius of curvature exceed approximately the electromagnetic wavelength /spl lambda/. Fractal surface models have characteristic features on arbitrarily small scales, thereby posing problems in application of the electromagnetic boundary conditions in general as well as in the evaluation of surface radius of curvature pertinent to KA. Experiments and numerical simulations show variations in scattering behavior that are consistent with scattering from progressively smoother surfaces with increasing wavelength, demonstrating surface smoothing effects in the wave-surface interaction. We hypothesize control of KA scattering from fractal surfaces by an effective average radius of curvature as a function of the smallest lateral scale /spl Delta/x contributing to scattering at /spl lambda/. Solution of =/spl lambda/ for /spl lambda/ is one possible method for approximating the limit of KA validity, assuming that /spl Delta/x[/spl lambda/] is known. Investigation of the validity of KA for the calculation of scattering from perfectly conducting Weierstrass-Mandelbrot and fractional Brownian process fractal surface models shows that for both models the region of applicability of KA grows with increases in /spl lambda/ and the Hurst exponent H controlling large-scale roughness. Numerical simulations using the method of moments demonstrate the dependence of /spl Delta/x on /spl lambda/ and the surface parameters.     

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

Improving the Gilbert-Varshamov bound for q-ary codes

Given positive integers q,n, and d, denote by A/sub q/(n,d) the maximum size of a q-ary code of length n and minimum distance d. The famous Gilbert-Varshamov bound asserts that A/sub q/(n,d+1)/spl ges/q/sup n//V/sub q/(n,d) where V/sub q/(n,d)=/spl Sigma//sub i=0//sup d/ (/sub i//sup n/)(q-1)/sup i/ is the volume of a q-ary sphere of radius d. Extending a recent work of Jiang and Vardy on binary codes, we show that for any positive constant /spl alpha/ less than (q-1)/q there is a positive constant c such that for d/spl les//spl alpha/n A/sub q/(n,d+1)/spl ges/cq/sup n//V/sub q/(n,d)n. This confirms a conjecture by Jiang and Vardy.     

Random properties of the highest level sequences of primitive sequences over Z(2/sup e/)

Using the estimates of the exponential sums over Galois rings, we discuss the random properties of the highest level sequences /spl alpha//sub e-1/ of primitive sequences generated by a primitive polynomial of degree n over Z(2/sup e/). First we obtain an estimate of 0, 1 distribution in one period of /spl alpha//sub e-1/. On the other hand, we give an estimate of the absolute value of the autocorrelation function |C/sub N/(h)| of /spl alpha//sub e-1/, which is less than 2/sup e-1/(2/sup e-1/-1)/spl radic/3(2/sup 2e/-1)2/sup n/2/+2/sup e-1/ for h/spl ne/0. Both results show that the larger n is, the more random /spl alpha//sub e-1/ will be.