Perfect state transfer in integral circulant graphs of non-square-free order

This paper provides further results on the perfect state transfer in integral circulant graphs (ICG graphs). The non-existence of PST is proved for several classes of ICG graphs containing an isolated divisor d₀, i.e. the divisor which is relatively prime to all other divisors from d∈D?{d₀}. The same result is obtained for classes of integral circulant graphs having the NSF property (i.e. each n/d is square-free, for every d∈D). A direct corollary of these results is the characterization of ICG graphs with two divisors, which have PST. A similar characterization is obtained for ICG graphs where each two divisors are relatively prime. Finally, it is shown that ICG graphs with the number of vertices n=2p² do not have PST.     

Amply regular graphs and block designs

We study the amply regular diameter d graphs Γ such that for some vertex a the set of vertices at distance d from a is the set of points of a 2-design whose set of blocks consists of the intersections of the neighborhoods of points with the set of vertices at distance d-1 from a. We prove that the subgraph induced by the set of points is a clique, a coclique, or a strongly regular diameter 2 graph. For diameter 3 graphs we establish that this construction is a 2-design for each vertex a if and only if the graph is distance-regular and for each vertex a the subgraph Γ₃(a) is a clique, a coclique, or a strongly regular graph. We obtain the list of admissible parameters for designs and diameter 3 graphs under the assumption that the subgraph induced by the set of points is a Seidel graph. We show that some of the parameters found cannot correspond to distance-regular graphs.     

Regular graphs of large girth and arbitrary degree

For every integer d≥10, we construct infinite families {G _n } _n∈? of d+1-regular graphs which have a large girth ≥log _d |G _n |, and for d large enough ≥1.33 · log _d |G _n |. These are Cayley graphs on PGL ₂(F _q ) for a special set of d+1 generators whose choice is related to the arithmetic of integral quaternions. These graphs are inspired by the Ramanujan graphs of Lubotzky-Philips-Sarnak and Margulis, with which they coincide when d is a prime. When d is not equal to the power of an odd prime, this improves the previous construction of Imrich in 1984 where he obtained infinite families {I _n } _n∈? of d + 1-regular graphs, realized as Cayley graphs on SL ₂(F _q ), and which are displaying a girth ≥0.48·log _d |I _n |. And when d is equal to a power of 2, this improves a construction by Morgenstern in 1994 where certain families {M _n } _n∈N of 2 ^k +1-regular graphs were shown to have girth ≥2/3·log₂ ^k |M _n |.     

On the theta number of powers of cycle graphs

We give a closed formula for Lovász’s theta number of the powers of cycle graphs C _k ^d?1 and of their complements, the circular complete graphs K _k/d . As a consequence, we establish that the circular chromatic number of a circular perfect graph is computable in polynomial time. We also derive an asymptotic estimate for the theta number of C _k ^d .     

Properties of Regular Uniform k—Stratified Graphs

A regular graph G = (V, E) is a k-stratified graph if V is partitioned into V₁, V₂, …, V_k subsets called strata. The stratification splits the degree d_v ∀v ϵ V into k-integers d_v1, d_v2, …, d_vk each one corresponding to a stratum. If d_v1 = d_v2 = … = d_vk ∀v ϵ V then G is called regular uniform k-stratified, RU^k_s(n, d) where n is the cardinality of the vertex set in each stratum and d is the degree of every vertex in each stratum. For every k, the class RU^k_s(n, d) has a unique graph generator class RU^l_s(n, d) derived by decomposition of graphs in RU^k_s(n, d). We investigate the minimization of the cardinality of V, the colorability, vertex coloring and the diameter of the graphs in the class. We also deal with complexity questions concerning RU^k_s(n, d). Some well-known computer network models such as barrel shifters and hypercubes are shown to belong in RU^k_s(n, d).     

The number of independent sets in unicyclic graphs with a given diameter

Let U_n,d denote the set of unicyclic graphs with a given diameter d. In this paper, the unique unicyclic graph in U_n,d with the maximum number of independent sets, is characterized.     

Majorants and minorants for the classes of graphs with fixed diameter and number of vertices

We study majorants (minorants) for the classes of n-vertex diameter d graphs, that is, the extremal graphs on which the sharp upper (lower) bounds are attained for the number of distinct radius i balls for every i ≥ 0. We explicitly describe the minorants for all values of n and d, determine when the class of n-vertex diameter d graphs contains majorants, and describe these extremal graphs.     

The Topological Tverberg Theorem and winding numbers

The Topological Tverberg Theorem claims that any continuous map of a (q-1)(d+1)-simplex to R^d identifies points from q disjoint faces. (This has been proved for affine maps, for d?1, and if q is a prime power, but not yet in general.)The Topological Tverberg Theorem can be restricted to maps of the d-skeleton of the simplex. We further show that it is equivalent to a “Winding Number Conjecture” that concerns only maps of the (d-1)-skeleton of a (q-1)(d+1)-simplex to R^d. “Many Tverberg partitions” arise if and only if there are “many q-winding partitions.”The d=2 case of the Winding Number Conjecture is a problem about drawings of the complete graphs K_3q-2 in the plane. We investigate graphs that are minimal with respect to the winding number condition.     

Hyper- and reverse-Wiener indices of F-sums of graphs

The Wiener index W(G)=∑_{u,v}⊂V(G)d(u,v), the hyper-Wiener index and the reverse-Wiener index , where d(u,v) is the distance of two vertices u,v in G, d²(u,v)=d(u,v)², n=|V(G)| and D is the diameter of G. In [M. Eliasi, B. Taeri, Four new sums of graphs and their Wiener indices, Discrete Appl. Math. 157 (2009) 794-803], Eliasi and Taeri introduced the F-sums of two connected graphs. In this paper, we determine the hyper- and reverse-Wiener indices of the F-sum graphs and, subject to some condition, we present some exact expressions of the reverse-Wiener indices of the F-sum graphs.     

Classification of subsets with minimal width and dual width in Grassmann, bilinear forms and dual polar graphs

Brouwer, Godsil, Koolen and Martin [Width and dual width of subsets in polynomial association schemes, J. Combin. Theory Ser. A 102 (2003) 255-271] introduced the width w and the dual width w^* of a subset in a distance-regular graph and in a cometric association scheme, respectively, and then derived lower bounds on these new parameters. For instance, subsets with the property w+w^*=d in a cometric distance-regular graph with diameter d attain these bounds. In this paper, we classify subsets with this property in Grassmann graphs, bilinear forms graphs and dual polar graphs. We use this information to establish the Erd?s-Ko-Rado theorem in full generality for the first two families of graphs.     

On tricyclic graphs of a given diameter with minimal energy

The energy of a graph is defined as the sum of the absolute values of all the eigenvalues of the graph. Let G(n,d) be the class of tricyclic graphs G on n vertices with diameter d and containing no vertex disjoint odd cycles C_p,C_q of lengths p and q with p+q≡2(mod4). In this paper, we characterize the graphs with minimal energy in G(n,d).     

On the hardness of sampling independent sets beyond the tree threshold

We consider local Markov chain Monte–Carlo algorithms for sampling from the weighted distribution of independent sets with activity λ, where the weight of an independent set I is λ^|I|. A recent result has established that Gibbs sampling is rapidly mixing in sampling the distribution for graphs of maximum degree d and λ < λ _c (d), where λ _c (d) is the critical activity for uniqueness of the Gibbs measure (i.e., for decay of correlations with distance in the weighted distribution over independent sets) on the d-regular infinite tree. We show that for d ≥ 3, λ just above λ _c (d) with high probability over d-regular bipartite graphs, any local Markov chain Monte–Carlo algorithm takes exponential time before getting close to the stationary distribution. Our results provide a rigorous justification for “replica” method heuristics. These heuristics were invented in theoretical physics and are used in order to derive predictions on Gibbs measures on random graphs in terms of Gibbs measures on trees. A major theoretical challenge in recent years is to provide rigorous proofs for the correctness of such predictions. Our results establish such rigorous proofs for the case of hard-core model on bipartite graphs. We conjecture that λ _c is in fact the exact threshold for this computational problem, i.e., that for λ > λ _c it is NP-hard to approximate the above weighted sum over independent sets to within a factor polynomial in the size of the graph.     

On the existence of graphs of diameter two and defect two

In the context of the degree/diameter problem, the ‘defect’ of a graph represents the difference between the corresponding Moore bound and its order. Thus, a graph with maximum degree d and diameter two has defect two if its order is n=d²−1. Only four extremal graphs of this type, referred to as (d,2,2)-graphs, are known at present: two of degree d=3 and one of degree d=4 and 5, respectively. In this paper we prove, by using algebraic and spectral techniques, that for all values of the degree d within a certain range, (d,2,2)-graphs do not exist.The enumeration of (d,2,2)-graphs is equivalent to the search of binary symmetric matrices A fulfilling that AJ_n=dJ_n and A²+A+(1−d)I_n=J_n+B, where J_n denotes the all-one matrix and B is the adjacency matrix of a union of graph cycles. In order to get the factorization of the characteristic polynomial of A in Q[x], we consider the polynomials F_i,d(x)=f_i(x²+x+1−d), where f_i(x) denotes the minimal polynomial of the Gauss period , being ζ_i a primitive ith root of unity. We formulate a conjecture on the irreducibility of F_i,d(x) in Q[x] and we show that its proof would imply the nonexistence of (d,2,2)-graphs for any degree d>5.     

Four correspondences between graphs and generalized young tableaux

Read's method of counting the number of undirected labeled graphs with a prescribed valency at each labeled node implies that the number of different graphs with a given degree sequence (d₁, d₂, d₃…d_n) is equal to the number of generalized Young tableaux of a certain shape filled with objects of specification (d₁, d₂, d₃…d_n). There are in fact four such results which are applicable to graphs with or without loops and with or without multiple edges. This paper contains four one-one correspondences between the four types of graph and generalized Young tableaux having four different shapes. The correspondences can be considered as combinatorial proofs of four identities of Littlewood.     

Graphs of order two less than the Moore bound

The problem of determining the largest order n_d,k of a graph of maximum degree at most d and diameter at most k is well known as the degree/diameter problem. It is known that n_d,k?M_d,k where M_d,k is the Moore bound. For d=4, the current best upper bound for n_4,k is M_4,k-1. In this paper we study properties of graphs of order M_d,k-2 and we give a new upper bound for n_4,k for k?3.     

The Endomorphism Type of Certain Bipartite Graphs and a Characterization of Projective Planes

Fan (in Southeast Asian Bull Math 25, 217–221, 2001) determines the endomorphism type of a finite projective plane. In this note we show that Fan’s result actually characterizes the class of projective planes among the finite bipartite graphs of diameter three. In fact, this will follow from a generalization of Fan’s theorem and its converse to all finite bipartite graphs with diameter d and girth g such that (1) d + 1<g≤2d, and (2) every pair of adjacent edges is contained in a circuit of length g.     

Minimizing the least eigenvalue of unicyclic graphs with fixed diameter

Let U(n,d) be the set of unicyclic graphs on n vertices with diameter d. In this article, we determine the unique graph with minimal least eigenvalue among all graphs in U(n,d). It is found that the extremal graph is different from that for the corresponding problem on maximal eigenvalue as done by Liu et al. [H.Q. Liu, M. Lu, F. Tian, On the spectral radius of unicyclic graphs with fixed diameter, Linear Algebra Appl. 420 (2007) 449-457].     

Non-hyperbolicity in random regular graphs and their traffic characteristics

In this paper we prove that random d-regular graphs with d ≥ 3 have traffic congestion of the order O(n log _d?1 ³ n) where n is the number of nodes and geodesic routing is used. We also show that these graphs are not asymptotically δ-hyperbolic for any non-negative δ almost surely as n → ∞.     

The Cayley graphs of ℤ<Superscript>d</Superscript> and the limits of vertex-primitive graphs of <Emphasis Type="Italic">HA</Emphasis>-type

We study the limits of the finite graphs that admit some vertex-primitive group of automorphisms with a regular abelian normal subgroup. It was shown in [1] that these limits are Cayley graphs of the groups ?^d. In this article we prove that for each d > 1 the set of Cayley graphs of ?^d presenting the limits of finite graphs with vertex-primitive and edge-transitive groups of automorphisms is countable (in fact, we explicitly give countable subsets of these limit graphs). In addition, for d < 4 we list all Cayley graphs of ?^d that are limits of minimal vertex-primitive graphs. The proofs rely on a connection of the automorphism groups of Cayley graphs of ?^d with crystallographic groups.     

Optimal tristance anticodes in certain graphs

For z₁,z₂,z₃∈Zⁿ, the tristance d₃(z₁,z₂,z₃) is a generalization of the L₁-distance on Zⁿ to a quantity that reflects the relative dispersion of three points rather than two. A tristance anticodeA_d of diameter d is a subset of Zⁿ with the property that d₃(z₁,z₂,z₃)?d for all z₁,z₂,z₃∈A_d. An anticode is optimal if it has the largest possible cardinality for its diameter d. We determine the cardinality and completely classify the optimal tristance anticodes in Z² for all diameters d?1. We then generalize this result to two related distance models: a different distance structure on Z² where d(z₁,z₂)=1 if z₁,z₂ are adjacent either horizontally, vertically, or diagonally, and the distance structure obtained when Z² is replaced by the hexagonal lattice A₂. We also investigate optimal tristance anticodes in Z³ and optimal quadristance anticodes in Z², and provide bounds on their cardinality. We conclude with a brief discussion of the applications of our results to multi-dimensional interleaving schemes and to connectivity loci in the game of Go.