For a vertex v of a connected graph G (V, E) and a subset S of V, the distance between v and S is defined by d(v,S)=min{d(v,x):x∈S}. For an ordered k-

The minimum linear arrangement problem is a combinatorial optimization problem whose goal is to find a linear layout of a network in such way that a certain objective cost function is optimized. In this paper, we compute the minimum linear arrangement of incomplete hypercubes using graph embeddings.

Graph embedding problems have gained importance in the field of interconnection networks for parallel computer architectures. Interconnection networks provide an effective mechanism for exchanging data between processors in a parallel computing system. In this paper, we introduce a technique to obtain a lower bound for dilation of an embedding. Moreover, we give algorithms to compute exact dilation of embedding circulant network into a triangular grid, Tower of Hanoi graph and Sierpinski gasket graph, proving that the lower bound obtained is sharp.

Abstract In the pursuit of obtaining largest graphs of given maximum degree Δ and diameter D, many construction techniques have been developed. Compounding of graphs is one such technique. In this article, by means of the compounding of complete graphs into a bipartite Moore graph of diameter 6, we obtain a family of large graphs of the same diameter. For maximum degrees Δ = 5, 6, 9, 12, and 14, members of this family constitute the largest known graphs of diameter 6. © 2008 Wiley Periodicals, Inc. NETWORKS, 2009

Abstract A (k;g)‐cage is a k‐regular graph with girth g and with the least possible number of vertices. In this article we prove that (k;g)‐cages are edge‐superconnected if g is even. Earlier, Marcote and Balbuena proved that (k;g)‐cages are edge‐superconnected if g is odd [Networks 43 (2004), 54–59]. Combining our results, we conclude that all (k;g)‐cages are edge‐superconnected. © 2006 Wiley Periodicals, Inc. NETWORKS, Vol. 47(2), 102–110 2006

Let D={a 1 , . . ., a n } be a set of real numbers, and let $S\subset \{1,\ldots,n\}$. For an interval $I\subset \{1,\ldots,n\}$ we set SUM(I)=\sum_{i\in I}a_i$. In this paper we solve the following problem which has been asked in connection with security of statistical databases: Find a largest family B of subintervals of {1,. . .,n} so that knowing the value of SUM(I) for all $I\in {\bf B}$ does not enable one to calculate any element $a_i\in D$, where $i\in S$.

The usability of a statistical database is defined to be the ratio of the cardinality of the largest set of queries which can be answered without compromise to the total number of queries. In this paper, we present new results concerning the usability of secure statistical databases for general SUM, COUNT and MEAN queries, as well as for the corresponding range queries. We give the usability of these k-dimensional databases for all k/spl ges/1. The paper concludes with a discussion of the implications of our results.

In this paper we study some relationships between the number of vertices, degree and diameter of finite diregular graphs. The three problems considered are N(d,k), K(n,d) and D(n,k); that is, find the maximum possible number of vertices given degree d and diameter k, find the minimum possible diameter given the number of vertices n and degree d, and find the minimum possible degree given the number of vertices n and diameter k respectively. These three problems are related but as far as we know not equivalent. In this paper we restrict our attention to digraphs of degree 2. Using new techniques we improve upon the bounds for N(d,k) and K(n,d) in the case of d = 2. The current state of knowledge of N(2,k) and K(n,2) (n≤100) is given in Tables 1 and 2. The paper concludes with eight open problems in the area.