Maximal Sidon sets and matroids

A subset X of an abelian group Γ, written additively, is a Sidon set of orderh if whenever {(a_i,m_i):i∈I} and {(b_j,n_j):j∈J} are multisets of size h with elements in X and ∑_i∈Im_ia_i=∑_j∈Jn_jb_j, then {(a_i,m_i):i∈I}={(b_j,n_j):j∈J}. The set X is a generalized Sidon set of order(h,k) if whenever two such multisets have the same sum, then their multiset intersection has size at least k. It is proved that if X is a generalized Sidon set of order (2h−1,h−1), then the maximal Sidon sets of order h contained in X have the same cardinality. Moreover, X is a matroid where the independent subsets of X are the Sidon sets of order h.     

Existence of good large sets of Steiner triple systems

The concept of good large set of Steiner triple systems (or GLS in short) was introduced by Lu in his paper “on large sets of disjoint Steiner triple systems”, [J. Lu, On large sets of disjoint Steiner triple systems, I-III, J. Combin. Theory (A) 34 (1983) 140-182]. In this paper a doubling construction for GLSs is displayed and some existence results are obtained.     

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.     

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.     

Identifying codes and locating-dominating sets on paths and cycles

Let G=(V,E) be a graph and let r≥1 be an integer. For a set D⊆V, define N_r[x]={y∈V:d(x,y)≤r} and D_r(x)=N_r[x]∩D, where d(x,y) denotes the number of edges in any shortest path between x and y. D is known as an r-identifying code (r-locating-dominating set, respectively), if for all vertices x∈V (x∈V?D, respectively), D_r(x) are all nonempty and different. Roberts and Roberts [D.L. Roberts, F.S. Roberts, Locating sensors in paths and cycles: the case of 2-identifying codes, European Journal of Combinatorics 29 (2008) 72-82] provided complete results for the paths and cycles when r=2. In this paper, we provide results for a remaining open case in cycles and complete results in paths for r-identifying codes; we also give complete results for 2-locating-dominating sets in cycles, which completes the results of Bertrand et al. [N. Bertrand, I. Charon, O. Hudry, A. Lobstein, Identifying and locating-dominating codes on chains and cycles, European Journal of Combinatorics 25 (2004) 969-987].     

Relative difference sets fixed by inversion (III)—Cocycle theoretical approach

In this paper, we give a characterization of a group G which contains a semiregular relative difference set R relative to a central subgroup N containing the commutator subgroup [G,G] of G such that 1∈R and rRr=R for all r∈R. In particular, these relative difference sets are fixed by inversion and inner automorphisms of the group are multipliers. We also present a construction of such relative difference sets.     

Frame cellular automata: Configurations, generating sets and related matroids

We introduce a frame cellular automaton as a broad generalization of an earlier study on quasigroup-defined cellular automata. It consists of a triple (F,R,E_F) where, for a given finite set X of cells, the frame F is a family of subsets of X (called elementary frames, denoted S_i, i=1,…,n), which is a cover of X. A matching configuration is a map which attributes to each cell a state in a finite set G under restriction of a set of local rules R={R_i∣i=1,…n}, where R_i holds in the elementary frame S_i and is determined by an (|S_i|-1)-ary quasigroup over G. The frame associated map E_F models how a matching configuration can be grown iteratively from a certain initial cell-set. General properties of frames and related matroids are investigated. A generating set S⊂X is a set of cells such that there is a bijection between the collection of matching configurations and G^S. It is shown that for certain frames, the algebraically defined generating sets are bases of a related geometric-combinatorially defined matroid.     

On symmetric graphs of valency five

A graph X, with a subgroup G of the automorphism group of X, is said to be (G,s)-transitive, for some s≥1, if G is transitive on s-arcs but not on (s+1)-arcs, and s-transitive if it is -transitive. Let X be a connected (G,s)-transitive graph, and G_v the stabilizer of a vertex v∈V(X) in G. If X has valency 5 and G_v is solvable, Weiss [R.M. Weiss, An application of p-factorization methods to symmetric graphs, Math. Proc. Camb. Phil. Soc. 85 (1979) 43-48] proved that s≤3, and in this paper we prove that G_v is isomorphic to the cyclic group Z₅, the dihedral group D₁₀ or the dihedral group D₂₀ for s=1, the Frobenius group F₂₀ or F₂₀×Z₂ for s=2, or F₂₀×Z₄ for s=3. Furthermore, it is shown that for a connected 1-transitive Cayley graph of valency 5 on a non-abelian simple group G, the automorphism group of is the semidirect product , where R(G) is the right regular representation of G and .     

Super-vertex-antimagic total labelings of disconnected graphs

Let G=(V,E) be a finite, simple and non-empty (p,q)-graph of order p and size q. An (a,d)-vertex-antimagic total labeling is a bijection f from V(G)∪E(G) onto the set of consecutive integers 1,2,…,p+q, such that the vertex-weights form an arithmetic progression with the initial term a and the common difference d, where the vertex-weight of x is the sum of values f(xy) assigned to all edges xy incident to vertex x together with the value assigned to x itself, i.e. f(x). Such a labeling is called super if the smallest possible labels appear on the vertices.In this paper, we will study the properties of such labelings and examine their existence for disconnected 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).     

Fixed point theorems for better admissible multimaps on almost convex sets

We obtain new fixed point theorems on multimaps in the class Bp defined on almost convex subsets of topological vector spaces. Our main results are applied to deduce various fixed point theorems, coincidence theorems, almost fixed point theorems, intersection theorems, and minimax theorems. Consequently, our new results generalize well-known works of Kakutani, Fan, Browder, Himmelberg, Lassonde, and others.     

Characterizations of linear Volterra integral equations with nonnegative kernels

We first introduce the notion of positive linear Volterra integral equations. Then, we offer a criterion for positive equations in terms of the resolvent. In particular, equations with nonnegative kernels are positive. Next, we obtain a variant of the Paley-Wiener theorem for equations of this class and its extension to perturbed equations. Furthermore, we get a Perron-Frobenius type theorem for linear Volterra integral equations with nonnegative kernels. Finally, we give a criterion for positivity of the initial function semigroup of linear Volterra integral equations and provide a necessary and sufficient condition for exponential stability of the semigroups.     

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.     

Differentiability of the volume of a region enclosed by level sets

The level of a function f on Rn encloses a region. The volume of a region between two such levels depends on both levels. Fixing one of them the volume becomes a function of the remaining level. We show that if the function f is smooth, the volume function is again smooth for regular values of f. For critical values of f the volume function is only finitely differentiable. The initial motivation for this study comes from Radiotherapy, where such volume functions are used in an optimization process. Thus their differentiability properties become important.     

Bounds on isoperimetric values of trees

Let G=(V,E) be a finite, simple and undirected graph. For S⊆V, let δ(S,G)={(u,v)∈E:u∈S and v∈V−S} be the edge boundary of S. Given an integer i, 1≤i≤|V|, let the edge isoperimetric value of G at i be defined as b_e(i,G)=min_S⊆V;|S|=i|δ(S,G)|. The edge isoperimetric peak of G is defined as b_e(G)=max_1≤j≤|V|b_e(j,G). Let b_v(G) denote the vertex isoperimetric peak defined in a corresponding way. The problem of determining a lower bound for the vertex isoperimetric peak in complete t-ary trees was recently considered in [Y. Otachi, K. Yamazaki, A lower bound for the vertex boundary-width of complete k-ary trees, Discrete Mathematics, in press (doi:10.1016/j.disc.2007.05.014)]. In this paper we provide bounds which improve those in the above cited paper. Our results can be generalized to arbitrary (rooted) trees.The depth d of a tree is the number of nodes on the longest path starting from the root and ending at a leaf. In this paper we show that for a complete binary tree of depth d (denoted as ), and where c₁, c₂ are constants. For a complete t-ary tree of depth d (denoted as ) and d≥clogt where c is a constant, we show that and where c₁, c₂ are constants. At the heart of our proof we have the following theorem which works for an arbitrary rooted tree and not just for a complete t-ary tree. Let T=(V,E,r) be a finite, connected and rooted tree — the root being the vertex r. Define a weight function w:V→N where the weight w(u) of a vertex u is the number of its successors (including itself) and let the weight index η(T) be defined as the number of distinct weights in the tree, i.e η(T)=|{w(u):u∈V}|. For a positive integer k, let ?(k)=|{i∈N:1≤i≤|V|,b_e(i,G)≤k}|. We show that .     

Bounding the size of square-free subgraphs of the hypercube

We investigate the maximum size of a subset of the edges of the n-cube that does not contain a square, or 4-cycle. The size of such a subset is trivially at most 3/4 of the total number of edges, but the proportion was conjectured by Erd?s to be asymptotically 1/2. Following a computer investigation of the 4-cube and the 5-cube, we improve the known upper bound from 0.62284… to 0.62256… in the limit.     

Pair lengths of product graphs

The pair length of a graph G is the maximum positive integer k, such that the vertex set of G can be partitioned into disjoint pairs {x,x^′}, such that d(x,x^′)?k for every x∈V(G) and x^′y^′ is an edge of G whenever xy is an edge. Chen asked whether the pair length of the cartesian product of two graphs is equal to the sum of their pair lengths. Our aim in this short note is to prove this result.     

Asplund sets, differentiability and subdifferentiability of functions in Banach spaces

We show that Asplund sets are effective tools to study differentiability of Lipschitz functions, and ε-subdifferentiability of lower semicontinuous functions on general Banach spaces. If a locally Lipschitz function defined on an Asplund generated space has a minimal Clarke subdifferential mapping, then it is TBY-uniformly strictly differentiable on a dense Gδ subset of X. Examples are given of locally Lipschitz functions that are TBY-uniformly strictly differentiable everywhere, but nowhere Fréchet differentiable.     

Edge-connectivity and edge-disjoint spanning trees

Given a graph G, for an integer c∈{2,…,|V(G)|}, define λ_c(G)=min{|X|:X⊆E(G),ω(G−X)≥c}. For a graph G and for an integer c=1,2,…,|V(G)|−1, define,

     

On Tutte polynomial uniqueness of twisted wheels

A graph G is called T-unique if any other graph having the same Tutte polynomial as G is isomorphic to G. Recently, there has been much interest in determining T-unique graphs and matroids. For example, de Mier and Noy [A. de Mier, M. Noy, On graphs determined by their Tutte polynomials, Graphs Combin. 20 (2004) 105-119; A. de Mier, M. Noy, Tutte uniqueness of line graphs, Discrete Math. 301 (2005) 57-65] showed that wheels, ladders, Möbius ladders, square of cycles, hypercubes, and certain class of line graphs are all T-unique. In this paper, we prove that the twisted wheels are also T-unique.