Lower bounds on covering codes via partition matrices

Let Kq(n,R) denote the minimal cardinality of a q-ary code of length n and covering radius R. Let σq(n,s;r) denote the minimal cardinality of a q-ary code of length n, which is s-surjective with radius r. In order to lower-bound Kq(n,n−2) and σq(n,s;s−2) we introduce partition matrices and their transversals. Our approach leads to a short new proof of a classical bound of Rodemich on Kq(n,n−2) and to the new bound Kq(n,n−2)?3q−2n+2, improving the first iff 5?n<q?2n−4. We determine Kq(q,q−2)=q−2+σ₂(q,2;0) if q?10. Moreover, we obtain the new powerful recursive bound Kq+1(n+1,R+1)?min{2(q+1),Kq(n,R)+1}.     

Some inverse results for Hill's equation

We consider Hill's equation y″+(λ−q)y=0 where q∈L¹[0,π]. We show that if l_n—the length of the n-th instability interval—is of order O(n^−(k+2)) then the real Fourier coefficients a_n^k,b_n^k of q^(k)—k-th derivative of q—are of order O(n⁻²), which implies that q^(k) is absolutely continuous almost everywhere for k=0,1,2,….     

Ordering connected graphs having small degree distances

The concept of degree distance of a connected graph G is a variation of the well-known Wiener index, in which the degrees of vertices are also involved. It is defined by D^′(G)=∑_x∈V(G)d(x)∑_y∈V(G)d(x,y), where d(x) and d(x,y) are the degree of x and the distance between x and y, respectively. In this paper it is proved that connected graphs of order n≥4 having the smallest degree distances are K_1,n−1,BS(n−3,1) and K_1,n−1+e (in this order), where BS(n−3,1) denotes the bistar consisting of vertex disjoint stars K_1,n−3 and K_1,1 with central vertices joined by an edge.     

The Independence Number for De Bruijn networks and Kautz networks

Let D be a directed graph; the (l,ω)-Independence Number of graph D, denoted by α_l,ω(D), is an important performance parameter for interconnection networks. De Bruijn networks and Kautz networks, denoted by B(d,n) and K(d,n) respectively, are versatile and efficient topological structures of interconnection networks. For l=1,2,…,n, this paper shows that α_l,d−1(B(d,n))=dⁿ,α_l,d−1(K(d,n))=α_l,d(K(d,n))=dⁿ+dⁿ⁻¹ if d≥3 and n≤d−2. In particular, the paper shows the exact value of the Independence Number for B(d,1) and B(d,2) for any d. For the generalized situation, the paper obtains a lower bound α_l,d−1(B(d,n))≥d² if n≥3 and d≥5.     

Homoclinic solutions for a class of the second order Hamiltonian systems

We study the existence of homoclinic orbits for the second order Hamiltonian system , where q∈Rⁿ and V∈C¹(R×Rⁿ,R), V(t,q)=-K(t,q)+W(t,q) is T-periodic in t. A map K satisfies the “pinching” condition b₁|q|²?K(t,q)?b₂|q|², W is superlinear at the infinity and f is sufficiently small in L²(R,Rⁿ). A homoclinic orbit is obtained as a limit of 2kT-periodic solutions of a certain sequence of the second order differential equations.     

Group action for enumerating maps on surfaces

A map is a connected topological graph Γ cellularly embedded in a surface. For any connected graph Γ, by introducing the conception of semi-arc automorphism groupAut1/2 Γ and classifying all embedding of Γ under the action of this group, the numbersr ^o (Γ) andr ^N (Γ) of rooted maps on orientable and non-orientable surfaces with underlying graph Γ are found. Many closed formulas without sum Σ for the number of rooted maps on surfaces (orientable or non-orientable) with given underlying graphs, such as, complete graphK _n , complete bipartite graphK _m,n, bouquetsB _n , dipoleDp _n and generalized dipoleDp _n ^k,l are refound in this paper.     

A note on acyclic edge coloring of complete bipartite graphs

An acyclic edge coloring of a graph is a proper edge coloring such that there are no bichromatic (2-colored) cycles. The acyclic chromatic index of a graph is the minimum number k such that there is an acyclic edge coloring using k colors and is denoted by a^′(G). Let Δ=Δ(G) denote the maximum degree of a vertex in a graph G. A complete bipartite graph with n vertices on each side is denoted by K_n,n. Alon, McDiarmid and Reed observed that a^′(K_p−1,p−1)=p for every prime p. In this paper we prove that a^′(K_p,p)≤p+2=Δ+2 when p is prime. Basavaraju, Chandran and Kummini proved that a^′(K_n,n)≥n+2=Δ+2 when n is odd, which combined with our result implies that a^′(K_p,p)=p+2=Δ+2 when p is an odd prime. Moreover we show that if we remove any edge from K_p,p, the resulting graph is acyclically Δ+1=p+1-edge-colorable.     

A note on the Path Kernel Conjecture

Let τ(G) denote the number of vertices in a longest path in a graph G=(V,E). A subset K of V is called a P_n-kernel of G if τ(G[K])≤n−1 and every vertex v∈V?K is adjacent to an end-vertex of a path of order n−1 in G[K]. It is known that every graph has a P_n-kernel for every positive integer n≤9. R. Aldred and C. Thomassen in [R.E.L. Aldred, C. Thomassen, Graphs with not all possible path-kernels, Discrete Math. 285 (2004) 297-300] proved that there exists a graph which contains no P₃₆₄-kernel. In this paper, we generalise this result. We construct a graph with no P₁₅₅-kernel and for each integer l≥0 we provide a construction of a graph G containing no P_τ(G)−l-kernel.     

On the restriction of cross characteristic representations of 2 F 4(q) to proper subgroups

We prove that the restriction of any nontrivial representation of the Ree groups ² F ₄(q), q = 2²ⁿ⁺¹ ≥ 8 in odd characteristic to any proper subgroup is reducible. We also determine all triples (K, V, H) such that ${K \in \{^2F_4(2), ^2F_4(2)'\} }We prove that the restriction of any nontrivial representation of the Ree groups ² F ₄(q), q = 2²ⁿ⁺¹ ≥ 8 in odd characteristic to any proper subgroup is reducible. We also determine all triples (K, V, H) such that K ? {²F₄(2), ²F₄(2)￠}{K \in \{^2F_4(2), ^2F_4(2)'\} } , H is a proper subgroup of K, and V is a representation of K in odd characteristic restricting absolutely irreducibly to H.     

Properties of connected graphs having minimum degree distance

The degree distance of a connected graph, introduced by Dobrynin, Kochetova and Gutman, has been studied in mathematical chemistry. In this paper some properties of graphs having minimum degree distance in the class of connected graphs of order n and size m≥n−1 are deduced. It is shown that any such graph G has no induced subgraph isomorphic to P₄, contains a vertex z of degree n−1 such that G−z has at most one connected component C such that |C|≥2 and C has properties similar to those of G.For any fixed k such that k=0,1 or k≥3, if m=n+k and n≥k+3 then the extremal graph is unique and it is isomorphic to K₁+(K_1,k+1∪(n−k−3)K₁).     

Arc-regular cubic graphs of order four times an odd integer

A graph is arc-regular if its automorphism group acts sharply-transitively on the set of its ordered edges. This paper answers an open question about the existence of arc-regular 3-valent graphs of order 4m where m is an odd integer. Using the Gorenstein?CWalter theorem, it is shown that any such graph must be a normal cover of a base graph, where the base graph has an arc-regular group of automorphisms that is isomorphic to a subgroup of Aut(PSL(2,q)) containing PSL(2,q) for some odd prime-power?q. Also a construction is given for infinitely many such graphs??namely a family of Cayley graphs for the groups PSL(2,p ³) where p is an odd prime; the smallest of these has order?9828.     

A new class of transitive graphs

Let n and k be integers with n≥k≥0. This paper presents a new class of graphs H(n,k), which contains hypercubes and some well-known graphs, such as Johnson graphs, Kneser graphs and Petersen graph, as its subgraphs. The authors present some results of algebraic and topological properties of H(n,k). For example, H(n,k) is a Cayley graph, the automorphism group of H(n,k) contains a subgroup of order 2ⁿn! and H(n,k) has a maximal connectivity and is hamiltonian if k is odd; it consists of two isomorphic connected components if k is even. Moreover, the diameter of H(n,k) is determined if k is odd.     

Uniformly optimal graphs in some classes of graphs with node failures

The uniformly optimal graph problem with node failures consists of finding the most reliable graph in the class Ω(n,m) of all graphs with n nodes and m edges in which nodes fail independently and edges never fail. The graph G is called uniformly optimal in Ω(n,m) if, for all node-failure probabilities q∈(0,1), the graph G is the most reliable graph in the class of graphs Ω(n,m). This paper proves that the multipartite graphs K(b,b+1,…,b+1,b+2) are uniformly optimal in their classes Ω((k+2)(b+1),(k²+3k+2)(b+1)²/2−1), where k is the number of partite sets of size (b+1), while for i>2, the multipartite graphs K(b,b+1,…,b+1,b+i) are not uniformly optimal in their classes Ω((k+2)b+k+i,(k+2)(k+1)b²/2+(k+1)(k+i)b+k(k+2i−1)/2).     

Degrees of the Elliptic Teichmüller Lift

The purpose of this paper is to find upper bounds for the degrees, or equivalently, for the order of the poles at O, of the coordinate functions of the elliptic Teichmüller lift of an ordinary elliptic curve over a perfect field of characteristic p. We prove the following bounds:ord₀(x_n)?−(n+2)pⁿ+npⁿ⁻¹, ord₀(y_n)?−(n+3)pⁿ+npⁿ⁻¹. Also, we prove that the bound for x_n is not the exact order if, and only if, p divides (n+1), and the bound for y_n is not the exact order if, and only if, p divides (n+1)(n+2)/2. Finally, we give an algorithm to compute the reduction modulo p³ of the canonical lift for p≠2,3.     

The Rotation Number Approach to the Periodic Fuc caron ik Spectrum

In this paper, we study the Fu?ik spectrum of the problem: (^*) ?+(λ₊+q₊(t))x₊+(λ₋+q₋(t))x₋=0 with the 2π-periodic boundary condition, where q_±(t) are 2π-periodic. After introducing a rotation number function ρ(λ₊, λ₋) for (^*), we prove using the Hamiltonian structure and the positive homogeneity of (^*) that for any positive integer n, the two boundary curves of the domain ρ⁻¹(n/2) in the (λ₊, λ₋)-plane are Fu?ik curves of (^*). The result obtained in this paper shows that such a spectrum problem is much like that of the higher dimensional Fu?ik spectrum with the Dirichlet condition. In particular, it remains open if the Fu?ik spectrum of (^*) is composed of only these curves.     

A non-existence result on cyclic cycle-decompositions of the cocktail party graph

We prove that in every cyclic cycle-decomposition of K_2n−I (the cocktail party graph of order 2n) the number of cycle-orbits of odd length must have the same parity of n(n−1)/2. This gives, as corollaries, some useful non-existence results one of which allows to determine when the two table Oberwolfach Problem OP(3,2?) admits a 1-rotational solution.     

Almost recognizability by spectrum of finite simple linear groups of prime dimension

The spectrum of a group is the set of its element orders. Let L = PSL _n (q), where n is a prime greater than 3. We show that every finite group whose spectrum is the same as the spectrum of L is isomorphic to an extension of L by a subgroup of the outer automorphism group of L.     

Cyclic Biembeddings of Twofold Triple Systems

We construct face two-colourable triangulations of the graph 2K _n in an orientable surface; equivalently biembeddings of two twofold triple systems of order n, for all n ≡ 4 (mod 12). The biembeddings have a cyclic automorphism and the construction employs index 1 current graphs.     

A new family of expansive graphs

An affine graph is a pair (G,σ) where G is a graph and σ is an automorphism assigning to each vertex of G one of its neighbors. On one hand, we obtain a structural decomposition of any affine graph (G,σ) in terms of the orbits of σ. On the other hand, we establish a relation between certain colorings of a graph G and the intersection graph of its cliques K(G). By using the results we construct new examples of expansive graphs. The expansive graphs were introduced by Neumann-Lara in 1981 as a stronger notion of the K-divergent graphs. A graph G is K-divergent if the sequence |V(Kⁿ(G))| tends to infinity with n, where Kⁿ⁺¹(G) is defined by Kⁿ⁺¹(G)=K(Kⁿ(G)) for n?1. In particular, our constructions show that for any k?2, the complement of the Cartesian product C^k, where C is the cycle of length 2k+1, is K-divergent.