For a fixed positive integer t, we consider the graph colouring problem in which edges at distance at most t are given distinct colours. We obtain sharp lower bounds for the distance-t chromatic index, the least number of colours necessary for such a colouring. Our bounds are of algebraic nature; they depend on the eigenvalues of the line graph and on a polynomial which can be found using integer linear programming methods. We provide several graph classes that attain equality for our bounds, and also present some computational results which illustrate the bound’s performance. Lastly, we investigate the implications the spectral approach has for the Erdős–Nešetřil conjecture, and derive some conditions which a graph must satisfy if we could use it to obtain a counter example through the proposed spectral methods.

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.

We use a graph-theoretic approach which yields improvements on the known Gilbert-Varshamov (GV) bound for sum-rank-metric codes for certain parameters. In particular, we show that asymptotically Fn×mqcan be partitioned into sum-rank-metric codes whose average size is bigger than the GV bound by a logarithmic factor for these parameters. Finally, we discuss the connection of such codes to set-coloring Ramsey numbers.

The exact distance t -power of a graph G , G [ ♯ t ] , is a graph which has the same vertex set as G , with two vertices adjacent in G [ ♯ t ] if and only if they are at distance exactly t in the original graph G . We study the clique number of this graph, also known as the t -equidistant number. We show that it is NP-hard to determine the t -equidistant number of a graph, and that in fact, it is NP-hard to approximate it within a constant factor. We also investigate how the t -equidistant number relates to another distance-based graph parameter; the t -independence number. In particular, we show how large the gap between both parameters can be. The hardness results motivate deriving eigenvalue bounds, which compare well against a known general bound. In addition, the tightness of the proposed eigenvalue bounds is studied.

We derive a linear programming bound on the maximum cardinality of error-correcting codes in the sum-rank metric. Based on computational experiments on relatively small instances, we observe that the obtained bounds outperform all previously known bounds.

We determine the diameter of generalized Grassmann graphs and the zero forcing number of some generalized Johnson graphs, generalized Grassmann graphs and the Hamming graphs. Our work extends several previously known results.

We consider the problem of deriving upper bounds on the parameters of sum-rank-metric codes, with focus on their dimension and block length. The sum-rank metric is a combination of the Hamming and the rank metric, and most of the available techniques to investigate it seem to be unable to fully capture its hybrid nature. In this paper, we introduce a new approach based on sum-rank-metric graphs, in which the vertices are tuples of matrices over a finite field, and where two such tuples are connected when their sum-rank distance is equal to one. We establish various structural properties of sum-rank-metric graphs and combine them with eigenvalue techniques to obtain bounds on the cardinality of sum-rank-metric codes. The bounds we derive improve on the best known bounds for several choices of the parameters. While our bounds are explicit only for small values of the minimum distance, they clearly indicate that spectral theory is able to capture the nature of the sum-rank-metric better than the currently available methods. They also allow us to establish new non-existence results for (possibly nonlinear) MSRD codes.

Let G be a graph on n vertices with adjacency matrix A, and let 1 be the all-ones vector. We call G controllable if the set of vectors 1, A1,..., An-11 spans the whole space Rn. We characterize the isomorphism problem of controllable graphs in terms of other combinatorial, geometric and logical problems. We also describe a polynomial time algorithm for graph isomorphism that works for almost all graphs.

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.

We show several sharp upper and lower bounds for the sum of the largest eigenvalues of the signless Laplacian matrix. These bounds improve and extend previously known bounds.

Abstract A Neumaier graph is a non-complete edge-regular graph containing a regular clique. In this paper we give some sufficient and necessary conditions for a Neumaier graph to be strongly regular. Further we show that there does not exist Neumaier graphs with exactly four distinct eigenvalues. We also determine the Neumaier graphs with smallest eigenvalue $$-2$$ - 2 .

The status of a vertex v in a connected graph is the sum of the distances from v to all other vertices. The status sequence of a connected graph is the list of the statuses of all the vertices of the graph. In this paper we investigate the status sequences of trees. Particularly, we show that it is NP-complete to decide whether there exists a tree that has a given sequence of integers as its status sequence. We also present some new results about trees whose status sequences are comprised of a few distinct numbers or many distinct numbers. In this direction, we show that any status injective tree is unique among trees. Finally, we investigate how orbit partitions and equitable partitions relate to the status sequence.

We apply Godsil–McKay switching to the symplectic graphs over $$\mathbb {F}_2$$ with at least 63 vertices and prove that the 2-rank of (the adjacency matrix of) the graph increases after switching. This shows that the switched graph is a new strongly regular graph with parameters $$(2^{2\nu }-1, 2^{2\nu -1}, 2^{2\nu -2},2^{2\nu -2})$$ and 2-rank $$2\nu +2$$ when $$\nu \ge 3$$ . For the symplectic graph on 63 vertices we investigate repeated switching by computer and find many new strongly regular graphs with the above parameters for $$\nu =3$$ with various 2-ranks. Using these results and a recursive construction method for the symplectic graph from Hadamard matrices, we obtain several graphs with the above parameters, but different 2-ranks for every $$\nu \ge 3$$ .