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.

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.

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.