Maximally resonant polygonal systems

A benzenoid system G is k-resonant if any set F of no more than k disjoint hexagons is a resonant pattern, i.e, G−F has a perfect matching. In 1990’s M. Zheng constructed the 3-resonant benzenoid systems and showed that they are maximally resonant, that is, they are k-resonant for all k≥1. Recently, the equivalence of 3-resonance and maximal resonance has been shown to be valid also for coronoid systems, carbon nanotubes, polyhexes in tori and Klein bottles, and fullerene graphs. So our main problem is to investigate the extent of graphs possessing this interesting property. In this paper, by replacing the above hexagons with even faces, we define k-resonance of graphs in surfaces, possibly with boundary, in a unified way. Some exceptions exist. For plane polygonal systems tessellated with polygons of even size at least six such that all inner vertices have the same degree three and the others have degree two or three, we show that such 3-resonant polygonal systems are indeed maximally resonant. They can be constructed by gluing and lapping operations on three types of basic graphs.     

A sufficient condition for pancyclability of graphs

Let G be a graph of order n and S be a vertex set of q vertices. We call G,S-pancyclable, if for every integer i with 3≤i≤q there exists a cycle C in G such that |V(C)∩S|=i. For any two nonadjacent vertices u,v of S, we say that u,v are of distance two in S, denoted by d_S(u,v)=2, if there is a path P in G connecting u and v such that |V(P)∩S|≤3. In this paper, we will prove that if G is 2-connected and for all pairs of vertices u,v of S with d_S(u,v)=2, , then there is a cycle in G containing all the vertices of S. Furthermore, if for all pairs of vertices u,v of S with d_S(u,v)=2, , then G is S-pancyclable unless the subgraph induced by S is in a class of special graphs. This generalizes a result of Fan [G. Fan, New sufficient conditions for cycles in graphs, J. Combin. Theory B 37 (1984) 221-227] for the case when S=V(G).     

Constructions of optimal quaternary constant weight codes via group divisible designs

Generalized Steiner systems were first introduced by Etzion and used to construct optimal constant weight codes over an alphabet of size g+1 with minimum Hamming distance 2k−3, in which each codeword has length v and weight k. As to the existence of a , a lot of work has been done for k=3, while not so much is known for k=4. The notion k-^∗GDD was first introduced by Chen et al. and used to construct . The necessary condition for the existence of a is v≥14. In this paper, it is proved that there exists a for any prime power and v≥19. By using this result, the known results on the existence of optimal quaternary constant weight codes are then extended.     

Constructions of generalized Sidon sets

We give explicit constructions of sets S with the property that for each integer k, there are at most g solutions to k=s₁+s₂,s_i∈S; such sets are called Sidon sets if g=2 and generalized Sidon sets if g?3. We extend to generalized Sidon sets the Sidon-set constructions of Singer, Bose, and Ruzsa. We also further optimize Kolountzakis’ idea of interleaving several copies of a Sidon set, extending the improvements of Cilleruelo, Ruzsa and Trujillo, Jia, and Habsieger and Plagne. The resulting constructions yield the largest known generalized Sidon sets in virtually all cases.     

Graph designs for the eight-edge five-vertex graphs

The existence of graph designs for the two nonisomorphic graphs on five vertices and eight edges is determined in the case of index one, with three possible exceptions in total. It is established that for the unique graph with vertex sequence (3, 3, 3, 3, 4), a graph design of order n exists exactly when and n≠16, with the possible exception of n=48. For the unique graph with vertex sequence (2,3,3,4,4), a graph design of order n exists exactly when , with the possible exceptions of n∈{32,48}.     

Binary relations and reduced hypergroups

Different partial hypergroupoids are associated with binary relations defined on a set H. In this paper we find sufficient and necessary conditions for these hypergroupoids in order to be reduced hypergroups. Given two binary relations ρ and σ on H we investigate when the hypergroups associated with the relations ρ∩σ, ρ∪σ and ρσ are reduced. We also determine when the cartesian product of two hypergroupoids associated with a binary relation is a reduced hypergroup.     

Ramsey numbers for a disjoint union of good graphs

We give the Ramsey number for a disjoint union of some G-good graphs versus a graph G generalizing the results of Stahl (1975) [5] and Baskoro et al. (2006) [1] and the previous result of the author Bielak (2009) [2]. Moreover, a family of G-good graphs with s(G)>1 is presented.     

Degree conditions for group connectivity

Let G be a 2-edge-connected simple graph on n≥13 vertices and A an (additive) abelian group with |A|≥4. In this paper, we prove that if for every uv∉E(G), max{d(u),d(v)}≥n/4, then either G is A-connected or G can be reduced to one of K_2,3,C₄ and C₅ by repeatedly contracting proper A-connected subgraphs, where C_k is a cycle of length k. We also show that the bound n≥13 is the best possible.     

Linear-time certifying algorithms for near-graphical sequences

A sequence 〈d₁,d₂,…,d_n〉 of non-negative integers is graphical if it is the degree sequence of some graph, that is, there exists a graph G on n vertices whose ith vertex has degree d_i, for 1≤i≤n. The notion of a graphical sequence has a natural reformulation and generalization in terms of factors of complete graphs.If H=(V,E) is a graph and g and f are integer-valued functions on the vertex set V, then a (g,f)-factor of H is a subgraph G=(V,F) of H whose degree at each vertex v∈V lies in the interval [g(v),f(v)]. Thus, a (0,1)-factor is just a matching of H and a (1, 1)-factor is a perfect matching of H. If H is complete then a (g,f)-factor realizes a degree sequence that is consistent with the sequence of intervals 〈[g(v₁),f(v₁)],[g(v₂),f(v₂)],…,[g(v_n),f(v_n)]〉.Graphical sequences have been extensively studied and admit several elegant characterizations. We are interested in extending these characterizations to non-graphical sequences by introducing a natural measure of “near-graphical”. We do this in the context of minimally deficient (g,f)-factors of complete graphs. Our main result is a simple linear-time greedy algorithm for constructing minimally deficient (g,f)-factors in complete graphs that generalizes the method of Hakimi and Havel (for constructing (f,f)-factors in complete graphs, when possible). It has the added advantage of producing a certificate of minimum deficiency (through a generalization of the Erdös-Gallai characterization of (f,f)-factors in complete graphs) at no additional cost.     

Sloane's box stacking problem

Recently, Sloane suggested the following problem: We are given n boxes, labeled 1,2,…,n. For i=1,…,n, box i weighs (m-1)i grams (where m?2 is a fixed integer) and box i can support a total weight of i grams. What is the number of different ways to build a single stack of boxes in which no box will be squashed by the weight of the boxes above it? Prior to this generalized problem, Sloane and Sellers solved the case m=2. More recently, Andrews and Sellers solved the case m?3. In this note we give new and simple proofs of the results of Sloane and Sellers and of Andrews and Sellers, using a known connection with m-ary partitions.     

Periodic solutions for a class of superquadratic Hamiltonian systems

We prove the existence of nontrivial critical points for a class of superquadratic nonautonomous second-order Hamiltonian systems by applying condition ^∗(C) to critical point theory, and some new solvability conditions of nontrivial periodic solutions are obtained.     

Covering graphs with matchings of fixed size

Let m be a positive integer and let G be a graph. We consider the question: can the edge set E(G) of G be expressed as the union of a set M of matchings of G each of which has size exactly m? If this happens, we say that G is [m]-coverable and we call M an [m]-covering of G. It is interesting to consider minimum[m]-coverings, i.e. [m]-coverings containing as few matchings as possible. Such [m]-coverings will be called excessive[m]-factorizations. The number of matchings in an excessive [m]-factorization is a graph parameter which will be called the excessive[m]-index and denoted by . In this paper we begin the study of this new parameter as well as of a number of other related graph parameters.     

Asymptotic stability for anisotropic Kirchhoff systems

We study the question of asymptotic stability, as time tends to infinity, of solutions of dissipative anisotropic Kirchhoff systems, involving the p(x)-Laplacian operator, governed by time-dependent nonlinear damping forces and strongly nonlinear power-like variable potential energies. This problem had been considered earlier for potential energies which arise from restoring forces, whereas here we allow also the effect of amplifying forces. Global asymptotic stability can then no longer be expected, and should be replaced by local stability. The results are further extended to the more delicate problem involving higher order damping terms.     

A group-based search for solutions of the n-queens problem

The n-queens problem is a well-known problem in mathematics, yet a full search for n-queens solutions has been tackled until now using only simple algorithms (with the exception of the Rivin-Zabih algorithm). In this article, we discuss optimizations that mainly rely on group actions on the set of n-queens solutions. Most of our arguments deal with the case of toroidal queens; at the end, the application to the regular n-queens problem is discussed, and also the Rivin-Zabih algorithm.     

Bartholdi zeta functions of some graphs

We give a decomposition formula for the Bartholdi zeta function of a graph G which is partitioned into some irregular coverings. As a corollary, we obtain a decomposition formula for the Bartholdi zeta function of G which is partitioned into some regular coverings.     

A degree sum condition for graphs to be prism hamiltonian

Win, in 1975, and Jackson and Wormald, in 1990, found the best sufficient conditions on the degree sum of a graph to guarantee the properties of “having a k-tree” and “having a k-walk”, respectively. The property of “being prism hamiltonian” is an intermediate property between “having a 2-tree” and “having a 2-walk”. Thus, it is natural to ask what is the best degree sum condition for graphs to be prism hamiltonian. As an answer to this problem, in this paper, we show that a connected graph G of order n with σ₃(G)≥n is prism hamiltonian. The degree sum condition “σ₃(G)≥n” is best possible.     

Optimal reconstruction systems for erasures and for the q-potential

In this paper we introduce the q-potential as an extension of the Benedetto-Fickus frame potential, defined on general reconstruction systems and show that protocols are the minimizers of this potential under certain restrictions. We extend recent results of B.G. Bodmann on the structure of optimal protocols with respect to 1 and 2 lost packets where the worst (normalized) reconstruction error is computed with respect to a compatible unitarily invariant norm. We finally describe necessary and sufficient (spectral) conditions, that we call q-fundamental inequalities, for the existence of protocols with prescribed properties by relating this problem to Klyachko’s and Fulton’s theory on sums of hermitian operators.     

Moore bound for mixed networks

Mixed graphs contain both undirected as well as directed links between vertices and therefore are an interesting model for interconnection communication networks. In this paper, we establish the Moore bound for mixed graphs, which generalizes both the directed and the undirected Moore bound.     

The Godbillon-Vey cyclic cocycle for PL-foliations

We define a cyclic cocycle which corresponds to the piecewise linear Godbillon-Vey class of Ghys and Sergiescu [E. Ghys, V. Sergiescu, Sur un groupe remarquable de difféomorphismes du cercle, Comment. Math. Helv. 62 (1987) 185-239]. Using Connes's pairing [A. Connes, Non-commutative differential geometry. Part II: De Rham homology and noncommutative algebra, Publ. Math. Inst. Hautes Études Sci. 62 (1985) 257-360; A. Connes, Cyclic cohomology and the transverse fundamental class of a foliation, in: H. Araki, G. Effros (Eds.), Geometric Methods in Operator Algebras, Pitman Res. Notes Math. Ser., vol. 123, Longman, Harlow, 1986, pp. 52-144] between cyclic cohomology and K-theory, we then evaluate this cocycle on a suitable K-theory class and obtain a nontrivial result, for foliations of the 3-torus by slope components.