Trivalent 2-Arc Transitive Graphs of Type {G^1_2} are Near Polygonal

A connected graph Σ of girth at least four is called a near n-gonal graph with respect to E, where n ≥  4 is an integer, if E is a set of n-cycles of Σ such that every path of length two is contained in a unique member of E. It is well known that connected trivalent symmetric graphs can be classified into seven types. In this note we prove that every connected trivalent G-symmetric graph S 1 K₄{\Sigma \neq K_4} of type G¹₂{G^1_2} is a near polygonal graph with respect to two G-orbits on cycles of Σ. Moreover, we give an algorithm for constructing the unique cycle in each of these G-orbits containing a given path of length two.     

1-vertex-fault-tolerant cycles embedding on folded hypercubes

In this paper, we focus on a hypercube-like structure, the folded hypercube, which is basically a standard hypercube with some extra links between its nodes. Let f be a faulty vertex in an n-dimensional folded hypercube FQ_n. We show that FQ_n−{f} contains a fault-free cycle of every even length from 4 to 2ⁿ−2 if n≥3 and, furthermore, every odd length from n+1 to 2ⁿ−1 if n≥2 and n is even.     

Edge-fault-tolerant edge-bipancyclicity of bubble-sort graphs

The bubble-sort graph Bn is a bipartite graph. Kikuchi and Araki [Edge-bipancyclicity and edge-fault-tolerant bipancyclicity of bubble-sort graphs. Information Processing Letters, 100, 52- 59 (2006)] have proved that Bn is edge-bipancyclic for n ≥ 5 and Bn-F is bipancyclic when n ≥ 4 and |F | ≤ n-3. In this paper, we improve this result by showing that for any edge set F of Bn with |F | ≤ n-3, every edge of Bn F lies on a cycle of every even length from 6 to n! for n ≥ 5 and every edge of Bn F lies on a cycle of every even length from 8 to n! for n = 4.     

On quadrilaterals in layers of the cube and extremal problems for directed and oriented graphs

Erdős has conjectured that every subgraph of the n‐cube Q_n having more than (1/2 + o(1))e(Q_n) edges will contain a 4‐cycle. In this note we consider ‘layer’ graphs, namely, subgraphs of the cube spanned by the subsets of sizes k − 1, k and k + 1, where we are thinking of the vertices of Q_n as being the power set of {1,…, n}. Observe that every 4‐cycle in Q_n lies in some layer graph. We investigate the maximum density of 4‐cycle free subgraphs of layer graphs, principally the case k = 2. The questions that arise in this case are equivalent to natural questions in the extremal theory of directed and undirected graphs. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 66–82, 2000     

Long Monochromatic Berge Cycles in Colored 4-Uniform Hypergraphs

Here we prove that for n ≥ 140, in every 3-coloring of the edges of K_n⁽⁴⁾{K_n^{(4)}} there is a monochromatic Berge cycle of length at least n − 10. This result sharpens an asymptotic result obtained earlier. Another result is that for n ≥ 15, in every 2-coloring of the edges of K_n⁽⁴⁾{K_n^{(4)}} there is a 3-tight Berge cycle of length at least n − 10.     

Fault-tolerant panconnectivity of augmented cubes

The augmented cube AQ _n is a variation of the hypercube Q _n . This paper considers the panconnectivity of AQ _n (n ⩾ 3) with at most 2n−5 faulty vertices and/or edges and shows that, for any two fault-free vertices u and v with distance d in AQ _n , there exist fault-free uv-paths of every length from d + 2 to 2 ⁿ − f − 1, where f is the number of faulty vertices in AQ _n . The proof is based on an inductive construction.     

Sets of disjoint snakes based on a Reed-Muller code and covering the hypercube

A snake-in-the-box code (or snake) of word length n is a simple circuit in an n-dimensional cube Q _n , with the additional property that any two non-neighboring words in the circuit differ in at least two positions. To construct such snakes a straightforward, non-recursive method is developed based on special linear codes with minimum distance 4. An extension of this method is used for the construction of covers of Q _n consisting of 2 ^m-1 vertex-disjoint snakes, for 2 ^m-1 < n ≤ 2 ^m . These covers turn out to have a symmetry group of order 2 ^m .      

Edge-bipancyclicity of a hypercube with faulty vertices and edges

A bipartite graph G=(V,E) is said to be bipancyclic if it contains a cycle of every even length from 4 to |V|. Furthermore, a bipancyclic G is said to be edge-bipancyclic if every edge of G lies on a cycle of every even length. Let F_v (respectively, F_e) be the set of faulty vertices (respectively, faulty edges) in an n-dimensional hypercube Q_n. In this paper, we show that every edge of Q_n-F_v-F_e lies on a cycle of every even length from 4 to 2ⁿ-2|F_v| even if |F_v|+|F_e|?n-2, where n?3. Since Q_n is bipartite of equal-size partite sets and is regular of vertex-degree n, both the number of faults tolerated and the length of a longest fault-free cycle obtained are worst-case optimal.     

On a Conjecture of Kemnitz

A classic theorem of Erdis, Ginzburg and Ziv states that in a sequence of 2n-1 integers there is a subsequence of length n whose sum is divisble by n. This result has led to several extensions and generalizations. A multi-dimensional problem from this line of research is the following. Let Z_nZ_n stand for the additive group of integers modulo n. Let s(n, d) denote the smallest integer s such that in any sequence of s elements from Z_n^dZ_n^d (the direct sum of d copies of Z_nZ_n) there is a subsequence of length n whose sum is 0 in Z_n^dZ_n^d. Kemnitz conjectured that s(n, 2) = 4n - 3. In this note we prove that s(p,2) ￡ 4p - 2s(p,2) \le 4p - 2 holds for every prime p. This implies that the value of s(p, 2) is either 4p-3 or 4p-2. For an arbitrary positive integer n it follows that s(n, 2) ￡ (41/10)ns(n, 2) \le (41/10)n. The proof uses an algebraic approach.     

The braid group B4 is linear

We study a linear representation ρ:B _n ? GL _m (Z[q ^±1,t ^±1]) with m=n(n-1)/2. We will show that for n=4, this representation is faithful. We prove a relation with the new Charney length function. We formulate a conjecture implying that ρ is faithful for all n. Oblatum 15-VI-1999 & 24-II-2000?Published online: 18 September 2000     

Construction of hamiltonian cycles with a given spectrum of edge directions in an <Emphasis Type="Italic">n</Emphasis>-dimensional Boolean cube

The spectrum of a Hamiltonian cycle (of a Gray code) in an n-dimensional Boolean cube is the series a = (a ₁, ..., a _n ), where a _i is the number of edges of the ith direction in the cycle. The necessary conditions for the existence of a Gray code with the spectrum a are available: the numbers a _i are even and, for k = 1, ..., n, the sum of k arbitrary components of a is at least 2 ^k . We prove that there is some dimension N such that if the necessary condition on the spectrum is also sufficient for the existence of a Hamiltonian cycle with the spectrum in an N-dimensional Boolean cube then the conditions are sufficient for all dimensions n.     

Partitioning a graph into two square-cycles

A square-cycle is the graph obtained from a cycle by joining every pair of vertices of distance two in the cycle. The length of a square-cycle is the number of vertices in it. Let G be a graph on n vertices with minimum degree at least 2/3n and let c be the maximum length of a square-cycle in G. Pósa and Seymour conjectured that c = n. In this paper, it is proved that either c = n or 1/2n ≤ c ≤ 2/3n. As an application of this result, it is shown that G has two vertex-disjoint square-cycles C₁, and C₂ such that V(G) = V(C₁) ∪ V(C₂). © 1996 John Wiley & Sons, Inc.     

On some extremal problems in graph theory

The author proves that ifC is a sufficiently large constant then every graph ofn vertices and [Cn ^3/2] edges contains a hexagonX ₁,X ₂,X ₃,X ₄,X ₅,X ₆ and a seventh vertexY joined toX ₁,X ₃ andX ₅. The problem is left open whether our graph contains the edges of a cube, (i.e. an eight vertexZ joined toX ₂,X ₄ andX ₆).     

The Banach-Mazur distance to the cube and the Dvoretzky-Rogers factorization

We show the existence of a sequence (λ _n ) of scalars withλ _n =o(n) such that, for any symmetric compact convex bodyB ⊂R ⁿ , there is an affine transformationT satisfyingQ ⊂T(B) ⊂λ _n Q, whereQ is then-dimensional cube. This complements results of the second-named author regarding the lower bound on suchλ _n . We also show that ifX is ann-dimensional Banach space andm=[n/2], then there are operatorsα:l ₂ ^m →X andβ:X→l _∞ ^m with ‖α‖·‖β‖≦C, whereC is a universal constant; this may be called “the proportional Dvoretzky-Rogers factorization”. These facts and their corollaries reveal new features of the structure of the Banach-Mazur compactum. Research performed while this author was visiting IHES. Supported in part by the NSF Grant DMS-8702058 and the Sloan Research Fellowship.     

VERTEX-FAULT-TOLERANT CYCLES EMBEDDING ON ENHANCED HYPERCUBE NETWORKS

In this paper, we study the enhanced hypercube, an attractive variant of the hypercube and obtained by adding some complementary edges from a hypercube, and focus on cycles embedding on the enhanced hypercube with faulty vertices. Let Fu be the set of faulty vertices in the n-dimensional enhanced hypercube Qn,k （n ≥ 3, 1 ≤ k 〈≤n - 1）. When IFvl = 2, we showed that Qn,k - Fv contains a fault-free cycle of every even length from 4 to 2n - 4 where n （n ≥ 3） and k have the same parity; and contains a fault-free cycle of every even length from 4 to 2n - 4, simultaneously, contains a cycle of every odd length from n-k ＋ 2 to 2^n-3 where n （≥ 3） and k have the different parity. Furthermore, when ｜Fv｜ = fv ≤ n - 2, we prove that there exists the longest fault-free cycle, which is of even length 2^n - 2fv whether n （n ≥ 3） and k have the same parity or not; and there exists the longest fault-free cycle, which is of odd length 2^n - 2fv ＋ 1 in Qn,k - Fv where n （≥ 3） and k have the different parity.     

A Ramsey‐type result for the hypercube

We prove that for every fixed k and ? ≥ 5 and for sufficiently large n, every edge coloring of the hypercube Q_n with k colors contains a monochromatic cycle of length 2 ?. This answers an open question of Chung. Our techniques provide also a characterization of all subgraphs H of the hypercube which are Ramsey, that is, have the property that for every k, any k‐edge coloring of a sufficiently large Q_n contains a monochromatic copy of H. © 2006 Wiley Periodicals, Inc. J Graph Theory 53: 196–208, 2006     

Factorizations of complete multipartite graphs into generalized cubes

For a positive integer d, the usual d‐dimensional cube Q_d is defined to be the graph (K₂)^d, the Cartesian product of d copies of K₂. We define the generalized cube Q(K_k, d) to be the graph (K_k)^d for positive integers d and k. We investigate the decomposition of the complete multipartite graph K into factors that are vertex‐disjoint unions of generalized cubes Q(K_k, d_i), where k is a power of a prime, n and j are positive integers with j ≤ n, and the d_i may be different in different factors. We also use these results to partially settle a problem of Kotzig on Q_d‐factorizations of K_n. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 144–150, 2000     

All cycle‐complete graph Ramsey numbers r(Cm,K6)

The cycle‐complete graph Ramsey number r(C_m, K_n) is the smallest integer N such that every graph G of order N contains a cycle C_m on m vertices or has independence number α(G) ≥ n. It has been conjectured by Erd?s, Faudree, Rousseau and Schelp that r(C_m, K_n) = (m ? 1) (n ? 1) + 1 for all m ≥ n ≥ 3 (except r(C₃, K₃) = 6). This conjecture holds for 3 ≤ n ≤ 5. In this paper we will present a proof for n = 6 and for all n ≥ 7 with m ≥ n² ? 2n. © 2003 Wiley Periodicals, Inc. J Graph Theory 44: 251–260, 2003     

Games of Chains and Cutsets in the Boolean Lattice II

Let 2 ^[n] denote the poset of all subsets of [n]={1,2,...,n} ordered by inclusion. Following Gutterman and Shahriari (Order 14, 1998, 321–325) we consider a game G _n (a,b,c). This is a game for two players. First, Player I constructs a independent maximal chains in 2 ^[n]. Player II will extend the collection to a+b independent maximal chains by finding another b independent maximal chains in 2 ^[n]. Finally, Player I will attempt to extend the collection further to a+b+c such chains. The last Player who is able to complete her move wins. In this paper, we complete the analysis of G _n (a,b,c) by considering its most difficult instance: when c=2 and a+b+2=n. We prove, the rather surprising result, that, for n7, Player I wins G _n (a,n–a–2,2) if and only if a3. As a consequence we get results about extending collections of independent maximal chains, and about cutsets (collections of subsets that intersect every maximal chain) of minimum possible width (the size of largest anti-chain).