For a graphG, itsk-th graph powerGkis constructed by placing an edge between two vertices if they are within distancek. We consider the problem of deriving upper bounds on the Shannon capacity of graph powers by using spectral graph theory and linear optimization methods. First, we use the so-called ratio-type bound to provide an alternative and spectral proof of a result by Lovász [IEEE Trans. Inform. Theory1979], which states that, for a regular graph, the Hoffman ratio bound on the independence number is also an upper bound on the Lovász theta number and, hence, also on the Shannon capacity. In fact, we show that Lovász’ result holds in the more general context of graph powers. Secondly, we derive another bound on the Shannon capacity of graph powers, the so-called rank-type bound, which depends on a new family of polynomials that can be computed by running a simple algorithm. Lastly, we provide several computational experiments that demonstrate the sharpness of the two proposed algebraic bounds. As a by-product, when these two new algebraic bounds are tight, they can be used to easily derive the exact values of the Lovász theta number (which relies on solving an SDP) and the Shannon capacity (which is not known to be computable) of the corresponding graph power.

Given a graph G = ( V , E ) on n vertices and an integer k between 1 and n − 1 , the k -token graph F k ( G ) has vertices representing the k -subsets of V , and two vertices are adjacent if their symmetric difference is the two end-vertices of an edge in E . Using the theory of Markov chains of random walks and the interchange process, it was proved that the algebraic connectivities (second smallest Laplacian eigenvalues) of G and F k ( G ) coincide, but a combinatorial/algebraic proof has been shown elusive. In this paper, we use the latter approach and prove that such equality holds for different new classes of graphs under perturbations, such as extended cycles, extended complete bipartite graphs, kite graphs, and graphs with a cut clique. Kite graphs are formed by a graph (head) with several paths (tail) rooted at the same vertex and with exciting properties. For instance, we show that the different eigenvalues of a kite graph are also eigenvalues of its perturbed graph obtained by adding edges. Moreover, as a particular case of one of our theorems, we generalize a recent result of Barik and Verma (2024) about graphs with a cut vertex of degree n − 1 . Along the way, we give conditions under which the perturbed graph G + u v , with u v ∈ E , has the same algebraic connectivity as G .

An (r,z,k)-mixed graph G has every vertex with undirected degree r, directed in- and out-degree z, and diameter k. In this paper, we study the case r = z = 1, proposing some new constructions of (1,1,k)-mixed graphs with a large number of vertices N. Our study is based on computer techniques for small values of k and the use of graphs on alphabets for general k. In the former case, the constructions are either Cayley or lift graphs. In the latter case, some infinite families of (1,1,k)-mixed graphs are proposed with diameter of the order of 2log2 N.

For k≥1, the k-independence number αk of a graph is the maximum number of vertices that are mutually at distance greater than k. The well-known inertia and ratio bounds for the (1-)independence number α(=α1) of a graph, due to Cvetković and Hoffman, respectively, were generalized recently for every value of k. We show that, for graphs with enough regularity, the polynomials involved in such generalizations are closely related and give exact values for αk, showing a new relationship between the inertia and ratio type bounds. Additionally, we investigate the existence and properties of the extremal case of sets of vertices that are mutually at maximum distance for walk-regular graphs. Finally, we obtain new sharp inertia and ratio type bounds for partially walk-regular graphs by using the predistance polynomials.

Knowledge of the Laplacian eigenvalues of a network provides important insights into its structural features and dynamical behaviours. Node or link removal caused by possible outage events, such as mechanical and electrical failures or malicious attacks, significantly impacts the Laplacian spectra. This can also happen due to intentional node removal against which, increasing the algebraic connectivity is desired. In this article, an analytical metric is proposed to measure the effect of node removal on the Laplacian eigenvalues of the network. The metric is formulated based on the local multiplicity of each eigenvalue at each node, so that the effect of node removal on any particular eigenvalues can be approximated using only one single eigen-decomposition of the Laplacian matrix. The metric is applicable to undirected networks as well as strongly-connected directed ones. It also provides a reliable approximation for the “Laplacian energy” of a network. The performance of the metric is evaluated for several synthetic networks and also the American Western States power grid. Results show that this metric has a nearly perfect precision in correctly predicting the most central nodes, and significantly outperforms other comparable heuristic methods.

The Mondrian problem consists of dissecting a square of side length n∈N into non-congruent rectangles with natural length sides such that the difference d(n) between the largest and the smallest areas of the rectangles partitioning the square is minimum. In this paper, we compute some bounds on d(n) in terms of the number of rectangles of the square partition. These bounds provide us optimal partitions for some values of n∈N. We provide a sequence of square partitions such that d(n)∕n2 tends to zero for n large enough. For the case of ‘perfect’ partitions, that is, with d(n)=0, we show that, for any fixed powers s1,…,sm, a square with side length n=p1s1⋯pmsm, can have a perfect Mondrian partition only if p1 satisfies a given lower bound. Moreover, if n(x) is the number of side lengths x (with n≤x) of squares not having a perfect partition, we prove that its ‘density’ n(x)x is asymptotic to (log(log(x)))22logx, which improves previous results.

Loss-free schemes are defined to ensure successful packet/burst transmissions in optical packet/burst switching networks. To this end, they rely on a collision-free routing and wavelength assignment (CF-RWA) scheme combined with simple contention resolution mechanisms that guarantee the absence of losses in intermediate links. Here, the CF-RWA problem is studied. In particular, by using graph theory, the problem of finding CF-RWA schemes that minimise the number of wavelengths to serve a given traffic matrix is set. The problem is simplified when it is formulated by using pre-defined sets of non-colliding paths. Within this framework, the problem is shown to be equivalent to finding a given vertex-set colouring of the so-called restriction digraph. Here, two heuristic algorithms are proposed to obtain such vertex-set colourings. One of them provides a suitable CF-RWA without having to solve the minimisation problem. By way of example, the proposed method is applied to the NSFNet and the EON network providing quasi-optimal results.

We formally define the n-dimensional Manhattan street network $M_n$—a special case of an n-regular digraph—and we study some of its structural properties. In particular, we show that $M_n$ is a Cayley digraph, which can be seen as a subgroup of the n-dimensional version of the wallpaper group $pgg$. These results induce a useful new representation of $M_n$, which can be applied to design a local (shortest-path) routing algorithm and to study some other metric properties, such as the diameter. We also show that the n-dimensional Manhattan street networks are Hamiltonian and, in the standard case (that is, in dimension two), we give sufficient conditions for a 2-dimensional Manhattan street network to be decomposable into two arc-disjoint Hamiltonian cycles.

Contention resolution is a major issue in OBS networks. Several proposals that ensure burst transmissions without losses inside the network have been studied in the literature. Two of these proposals are based on combining a collision-free routing and wavelength assignment scheme with simple contention avoidance/resolution mechanisms. The static approach defines variable offsets and ensures contention avoidance by means of a suitable pre-assignment of offset windows to each communication. The dynamic approach guarantees the successful resolution of all contentions by using a single FDL at each intermediate node. Both proposals are based on giving priority to transmissions coming from the upstream. Hence, when an upstream node misbehaves or changes its transmission traffic pattern, it might delay new burst allocations on downstream nodes, leading to burst losses in the worst case. In this paper we deal with the fairness issue of these proposals. Thus, we introduce simple mechanisms that guarantee the transmission of the committed load for each communication, allowing, at the same time, the dynamic sharing of the spare bandwidth on each wavelength. The proposed mechanisms are analyzed by means of simulation.

This work introduces a new approach to get loss-free burst/packet transmission in optical burst and packet switched networks. To this end, our proposal defines (1) a routing and wavelength assignment (RWA) scheme based on the concept of wavelength tree, and (2) a simple contention resolution mechanism that solves contention using a limited number of fiber delay lines. We show that using the proposed scheme, for a 2-link-connected network with n nodes, there exists communication between any pair of nodes with [n/2] wavelengths. We apply this approach to address the problem of finding (conflict-free) transmission schemes in iterated line digraphs. Such digraphs have proved to be very useful models for dense, easily mutable, and fault tolerant communication networks. Examples of such networks are the well-known De Bruijn and Kautz digraphs and the wrapped butterfly networks. Our study leads us to define a useful tool for obtaining wavelength trees. By way of example, we illustrate the scheme operation for the 2-regular Kautz digraph. Simulation results show a good behavior in terms of transmission delay and resources utilization.

This paper proposes a simple procedure to ensure burst transmission without losses in Optical Burst Switching ring networks. The contention problem is solved by providing a scheme that pre-assigns, to each communication, a given wavelength and an offset window. This approach does not need any additional control information and, since burst contention is avoided, the network capacity and the wavelength utilization are maximized under dynamic traffic assumptions. The study is done by using techniques from graph theory. In particular, the so-called (acyclic) restriction digraphs provide a sharp lower bound for the number of required wavelengths, and support a greedy algorithm for assigning a suitable offset window to each communication. An alternative formulation of the obtained schemes, in terms of matrices, is also discussed. Simulation results of different feasible solutions are provided, showing low transmission delays and quite balanced wavelength utilization.

Abstract The knowledge of the spectrum of a (di)graph is relevant for estimating some of its structural properties, which provide information on the topological and communication properties of the corresponding networks. Among these properties, we have, for instance, edge‐expansion and node‐expansion, bisection width, diameter, maximum cut, connectivity, and partitions. In this paper, we determine the complete spectra (eigenvalues and multiplicities) of wrapped butterfly digraphs. © 2003 Wiley Periodicals, Inc.

Given a vertex subset C of a distance-regular graph $\Gamma$ on n vertices, it is shown that C is a completely regular code if and only if the number of vertices at maximum distance from C satisfies an expression in terms of the spectrum of $\Gamma$ and some mean numbers computed from the distances among the vertices of C (the so-called "inner distribution" of C). For such codes, this result can be seen as an improvement of Delsarte's linear programming method, since it gives stronger necessary conditions for their existence. As an application, a purely spectral characterization of those distance-regular graphs which are "edge-distance-regular" (that is, with every edge being a completely regular code with the same parameters) is derived.

Recently, it was proved that if the diameter D of a graph G is small enough in comparison with its girth, then G is maximally connected and that a similar result also holds for digraphs. More precisely, if the diameter D of a digraph G satisfies D ≤ 21 − 1, then G has maximum connectivity (κ = δ), and if D ≤ 21, then it attains maximum edge-connectivity (λ = δ), where I is a parameter which can be thought of as a generalization of the girth of a graph. In this paper, we study some similar conditions for a digraph to attain high connectivities, which are given in terms of what we call the conditional diameter or P-diameter of G. This parameter measures how far apart can be a pair of subdigraphs satisfying a given property P, and, hence, it generalizes the standard concept of diameter. As a corollary, some new sufficient conditions to attain maximum connectivity or edge-connectivity are derived. It is also shown that these conditions can be slightly relaxed when the digraphs are bipartite. The case of (undirected) graphs is managed as a corollary of the above results for digraphs. In particular, since I ≥ 1, some known results of Plesnik and Znám are either reobtained or improved. For instance, it is shown that any graph whose line graph has diameter D = 2 (respectively, D ≤ 3) has maximum connectivity (respectively, edge-connectivity). Moreover, for graphs with even girth and minimum degree large enough, we obtain a lower bound on their connectivities. © 1996 John Wiley & Sons, Inc.

The aim of this note is to present some counterexamples to the results in the paper by Du, Lyuu, and Hsu (see ibid., vol.42, no.5, p.612-16, May 1993).

The following problem arises in the design of some interconnection networks for distributed systems. Namely, to construct digraphs with given maximum out-degree, reduced diameter, easy routing, good connectivity, and good expandability. To this end, a method based on the concept of partial line digraph is presented. This proposal, which turns out to be a generalization of the so-called line digraph technique, allows digraphs that satisfy all the above-mentioned requirements to be obtained. In particular, it is shown that the partial line digraphs of Kautz digraphs solve the (d, N) digraph problem, i.e. to minimize the diameter D in a digraph of maximum out-degree d and number of vertices N, for any N in the range d/sup D-1/+d/sup D-2/+. . .+1>

This paper presents the solution of the following optimization problem that appears in the design of double-loop structures for local networks and also in data memory, allocation and data alignment in SIMD processors.

This paper studies the behavior of the diameter and the average distance between vertices of the line digraph of a given digraph. The results obtained are then applied to the so-called (d, k) digraph problem, that is, to maximize the number of vertices in a digraph of maximum out-degree d and diameter k. By line digraph iterations it is possible to construct digraphs with a number of vertices larger than (d2- l)/d2times the (nonattainable) Moore bound. In particular, this solves the (d, k) digraph problem for k = 2. Also, the line digraph technique provides us with a simple local routing algorithm for the corresponding networks.

We consider in this paper the (d,k) problem for directed graphs: to maximize the number of vertices in a digraph of degree d and diameter k. For any values of d and k, we construct a graph with a number of vertices larger than (d 2-1)/d2 times the (non-attainable) Moore bound. In particular, this solves the (d,k) digraph problem for k=2. We also show that these graphs can be obtained as line digraph iterations and that this technique provides us with a simple local routing algorithm for the corresponding networks.

The multibus interconnection network is an attractive solution for connecting processors and memory modules in a multiprocessor with shared memory. It provides a throughput which is intermediate between the single bus and the crossbar, with a corresponding intermediate cost.