Minimum order of loop networks of given degree and girth

Behzad, Chartrand and Wall proposed the conjecture that any regular digraph of degreer and girthg has ordern r(g – 1) + 1. The conjecture was proved in [3] for vertex transitive graphs. For Loop Networks the conjecture is equivalent to a theorem of Shepherdson in additive number theory. We show that, except for graphs of a particular structure, Loop Networks, and in general Abelian Cayley graphs, verify the stronger inequalityn (r + 1)(g – 1) – 1. This bound is best possible.Supported by the Spanish Research Council (CICYT) under project TIC 90-0712 and Acción Integrada Hispanofrancesa, TIC 79B.     

Vosperian and superconnected Abelian Cayley digraphs

A digraphX is said to be Vosperian if any fragment has cardinality either 1 or|V(X)| – d ⁺ (X) – 1.A digraph is said to be superconnected if every minimum cutset is the set of vertices adjacent from or to some vertex.In this paper we characterize Vosperian and superconnected Abelian Cayley directed graphs. Our main tool is a difficult theorem of J.H. Kemperman from Additive Group Theory.In particular we characterize Vosperian and superconnected loops network (also called circulants).     

On Subsets with Small Product in Torsion-Free Groups

G be a nonabelian torsion-free group. Let C be a finite generating subset of G such that . We prove that, for all subsets B of G with , we have . In particular, a finite subset X with cardinality satisfies the inequality if and only if there are elements , such that the following two conditions hold: (i) . (ii) where . Received: October 13, 1997/Revised: Revised August 18, 1998     

On Vosperian and Superconnected Vertex-Transitive Digraphs

We investigate the structure of a digraph having a transitive automorphism group where every cutset of minimal cardinality consists of all successors or all predecessors of some vertex. We give a complete characterization of vosperian arc-transitive digraphs. It states that an arc-transitive strongly connected digraph is vosperian if and only if it is irreducible. In particular, this is the case if the degree is coprime with the order of the digraph. We give also a complete characterization of vosperian Cayley digraphs and a complete characterization of irreducible superconnected Cayley digraphs. These two last characterizations extend the corresponding ones in Abelian Cayley digraphs and the ones in the undirected case.     

Distinct length modular zero-sum subsequences: A proof of Graham's conjecture

Text

Let S be a sequence of n nonnegative integers not exceeding n−1 such that S takes at least three distinct values. We show that S has two nonempty zero-sum subsequences with distinct lengths. This proves a conjecture of R.L. Graham. The validity of this conjecture was verified by Erd?s and Szemerédi for all sufficiently large prime n.

Video

For a video summary of this paper, please click here or visit http://www.youtube.com/watch?v=LftJj-E6aQA.     

Covering a Finite Abelian Group by Subset Sums

Let G be an abelian group of order n. The critical number c(G) of G is the smallest s such that the subset sums set (S) covers all G for eachs ubset SG\{0} of cardinality |S|s. It has been recently proved that, if p is the smallest prime dividing n and n/p is composite, then c(G)=|G|/p+p–2, thus establishing a conjecture of Diderrich.We characterize the critical sets with |S|=|G|/p+p–3 and (S)=G, where p3 is the smallest prime dividing n, n/p is composite and n7p²+3p.We also extend a result of Diderrichan d Mann by proving that, for n67, |S|n/3+2 and S=G imply (S)=G. Sets of cardinality for which (S) =G are also characterized when n183, the smallest prime p dividing n is odd and n/p is composite. Finally we obtain a necessary and sufficient condition for the equality (G)=G to hold when |S|n/(p+2)+p, where p5, n/p is composite and n15p².* Work partially supported by the Spanish Research Council under grant TIC2000-1017 Work partially supported by the Catalan Research Council under grant 2000SGR00079     

On multiply critically h-connected graphs

A conjecture of Slater states that K_{h + 1} is the unique k-critically h-connected noncomplete graph for 2k > h. We prove here that there is no k-critically h-connected connected graph with order $\text{?h + k ? 2}\text{for}\text{2k > h + 1}$. We prove also that there is no k-critically h-connected line graph for 2k > h. The last result was conjectured by Maurer and Slater. We apply in our proofs a method introduced by Mader.     

Vertex‐transitive graphs that remain connected after failure of a vertex and its neighbors

A d‐regular graph is said to be superconnected if any disconnecting subset with cardinality at most d is formed by the neighbors of some vertex. A superconnected graph that remains connected after the failure of a vertex and its neighbors will be called vosperian. Let Γ be a vertex‐transitive graph of degree d with order at least d+4. We give necessary and sufficient conditions for the vosperianity of Γ. Moreover, assuming that distinct vertices have distinct neighbors, we show that Γ is vosperian if and only if it is superconnected. Let G be a group and let S?G\{1} with S=S^?1. We show that the Cayley graph, Cay(G, S), defined on G by S is vosperian if and only if G\(S∪{1}) is not a progression and for every non‐trivial subgroup H and every a∈G, If moreover S is aperiodic, then Cay(G, S) is vosperian if and only if it is superconnected. © 2011 Wiley Periodicals, Inc. J Graph Theory 67:124‐138, 2011