Search for: All records

A k-dispersed labelling of a graph G on n vertices is a labelling of the vertices of G by the integers 1,...,n such that d(i,i+1) ≥ k for 1 ≤ i ≤ n − 1. Here DL(G) denotes the maximum value of k such that G has a k-dispersed labelling. In this paper, we study upper and lower bounds on DL(G). Computing DL(G) is NP-hard. However, we determine the exact value of DL(G) for cycles, paths, grids, hypercubes and complete binary trees. We also give a product construction and we prove a degree-based bound. 

Using a key result of Mancinska and Roberson characterizing quantum isomorphism in terms of planar homomorphism counts and using the theory of scaffolds, the authors construct large families of graphs that are pairwise non-isomorphic yet quantum isomorphic. All examples so far arise from Hadamard matrices. 

This paper introduces a generalization of perfect state transfer in continuous time quantum walks on graph and explores basic properties and example of this phenomenon. 

We consider ordered pairs (X,B) where X is a finite set of size v and B is some collection of k-element subsets of X such that every t-element subset of X is contained in exactly λ "blocks'' b ∈B for some fixed λ. We represent each block b by a zero-one vector c_b of length v and explore the ideal I(B) of polynomials in v variables with complex coefficients which vanish on the set { c_b ∣ b ∈ B}. After setting up the basic theory, we investigate two parameters related to this ideal: γ1(B) is the smallest degree of a non-trivial polynomial in the ideal I(B) and γ2(B) is the smallest integer s such that I(B) is generated by a set of polynomials of degree at most s. We first prove the general bounds t/2 < γ1(B) ≤ γ2(B) ≤ k. Examining important families of examples, we find that, for symmetric 2-designs and Steiner systems, we have γ2(B) ≤ t. But we expect γ2(B) to be closer to k for less structured designs and we indicate this by constructing infinitely many triple systems satisfying γ2(B) = k.