Existence of r-self-orthogonal Latin squares

Two Latin squares of order v are r-orthogonal if their superposition produces exactly r distinct ordered pairs. If the second square is the transpose of the first one, we say that the first square is r-self-orthogonal, denoted by r-SOLS(v). It has been proved that for any integer v?28, there exists an r-SOLS(v) if and only if v?r?v² and r∉{v+1,v²-1}. In this paper, we give an almost complete solution for the existence of r-self-orthogonal Latin squares.     

Maximum transversal in partial Latin squares and rainbow matchings

In a partial Latin square P a set of distinct entries, such that no two of which are in the same row or column is called a transversal. By the size of a transversal T, we mean the number of its entries. We define a duplex to be a partial Latin square of order n containing 2n entries such that exactly two entries lie in each row and column and each of n symbols occurs exactly twice. We show that determining the maximum size of a transversal in a given duplex is an NP-complete problem. This problem relates to independent sets in certain subfamilies of cubic graphs. Generalizing the concept of transversals in edge coloring of graphs we are led to introduce the concept of rainbow matching. We show that if each color appears at most twice then it is a polynomial time problem to know whether there exists a rainbow matching of size at least ⌊n/2⌋-t for each fixed t, where n is the order of the graph. As an application we show that for any fixed t, there is a polynomial time algorithm which decides whether α(G)?n-t, for any graph G on 2n vertices containing a perfect matching. At the end we mention some other applications of rainbow matching.     

On a generalization of the Evans Conjecture

The Evans Conjecture states that a partial Latin square of order n with at most n-1 entries can be completed. In this paper we generalize the Evans Conjecture by showing that a partial r-multi Latin square of order n with at most n-1 entries can be completed. Using this generalization, we confirm a case of a conjecture of Häggkvist.     

On a deterministic linear partial differential system

We develop an Lp theory for the Cauchy problem of linear partial differential systems of the form

     

On operator valued sequences of multipliers and R-boundedness

In recent papers (cf. [J.L. Arregui, O. Blasco, (p,q)-Summing sequences, J. Math. Anal. Appl. 274 (2002) 812-827; J.L. Arregui, O. Blasco, (p,q)-Summing sequences of operators, Quaest. Math. 26 (2003) 441-452; S. Aywa, J.H. Fourie, On summing multipliers and applications, J. Math. Anal. Appl. 253 (2001) 166-186; J.H. Fourie, I. Röntgen, Banach space sequences and projective tensor products, J. Math. Anal. Appl. 277 (2) (2003) 629-644]) the concept of (p,q)-summing multiplier was considered in both general and special context. It has been shown that some geometric properties of Banach spaces and some classical theorems can be described using spaces of (p,q)-summing multipliers. The present paper is a continuation of this study, whereby multiplier spaces for some classical Banach spaces are considered. The scope of this research is also broadened, by studying other classes of summing multipliers. Let E(X) and F(Y) be two Banach spaces whose elements are sequences of vectors in X and Y, respectively, and which contain the spaces c₀₀(X) and c₀₀(Y) of all X-valued and Y-valued sequences which are eventually zero, respectively. Generally spoken, a sequence of bounded linear operators (un)⊂L(X,Y) is called a multiplier sequence from E(X) to F(Y) if the linear operator from c₀₀(X) into c₀₀(Y) which maps (xi)∈c₀₀(X) onto (unxn)∈c₀₀(Y) is bounded with respect to the norms on E(X) and F(Y), respectively. Several cases where E(X) and F(Y) are different (classical) spaces of sequences, including, for instance, the spaces Rad(X) of almost unconditionally summable sequences in X, are considered. Several examples, properties and relations among spaces of summing multipliers are discussed. Important concepts like R-bounded, semi-R-bounded and weak-R-bounded from recent papers are also considered in this context.     

Large sets of resolvable idempotent Latin squares

An idempotent Latin square of order v is called resolvable and denoted by RILS(v) if the v(v−1) off-diagonal cells can be resolved into v−1 disjoint transversals. A large set of resolvable idempotent Latin squares of order v, briefly LRILS(v), is a collection of v−2 RILS(v)s pairwise agreeing on only the main diagonal. In this paper we display some recursive and direct constructions for LRILSs.     

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.     

On (d,1)-total numbers of graphs

A (d,1)-total labelling of a graph G assigns integers to the vertices and edges of G such that adjacent vertices receive distinct labels, adjacent edges receive distinct labels, and a vertex and its incident edges receive labels that differ in absolute value by at least d. The span of a (d,1)-total labelling is the maximum difference between two labels. The (d,1)-total number, denoted , is defined to be the least span among all (d,1)-total labellings of G. We prove new upper bounds for , compute some for complete bipartite graphs K_m,n, and completely determine all for d=1,2,3. We also propose a conjecture on an upper bound for in terms of the chromatic number and the chromatic index of G.     

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.     

6-regular Cayley graphs on abelian groups of odd order are hamiltonian decomposable

Alspach conjectured that any 2k-regular connected Cayley graph on a finite abelian group A has a hamiltonian decomposition. In this paper, the conjecture is shown true if k=3, and the order of A is odd.     

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.     

On the complexity of crossings in permutations

We investigate crossing minimization problems for a set of permutations, where a crossing expresses a disarrangement between elements. The goal is a common permutation π^∗ which minimizes the number of crossings. In voting and social science theory this is known as the Kemeny optimal aggregation problem minimizing the Kendall-τ distance. This rank aggregation problem can be phrased as a one-sided two-layer crossing minimization problem for a series of bipartite graphs or for an edge coloured bipartite graph, where crossings are counted only for monochromatic edges. We contribute the max version of the crossing minimization problem, which attempts to minimize the discrimination against any permutation. As our results, we correct the construction from [C. Dwork, R. Kumar, M. Noar, D. Sivakumar, Rank aggregation methods for the Web, Proc. WWW10 (2001) 613-622] and prove the NP-hardness of the common crossing minimization problem for k=4 permutations. Then we establish a 2−2/k-approximation, improving the previous factor of 2. The max version is shown NP-hard for every k≥4, and there is a 2-approximation. Both approximations are optimal, if the common permutation is selected from the given ones. For two permutations crossing minimization is solved by inspecting the drawings, whereas it remains open for three permutations.     

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 .     

On the complexity of the multicut problem in bounded tree-width graphs and digraphs

Given an edge- or vertex-weighted graph or digraph and a list of source-sink pairs, the minimum multicut problem consists in selecting a minimum weight set of edges or vertices whose removal leaves no path from each source to the corresponding sink. This is a classical NP-hard problem, and we show that the edge version becomes tractable in bounded tree-width graphs if the number of source-sink pairs is fixed, but remains NP-hard in directed acyclic graphs and APX-hard in bounded tree-width and bounded degree unweighted digraphs. The vertex version, although tractable in trees, is proved to be NP-hard in unweighted cacti of bounded degree and bounded path-width.     

On (s,t)-supereulerian graphs in locally highly connected graphs

Given two nonnegative integers s and t, a graph G is (s,t)-supereulerian if for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y|≤t, there is a spanning eulerian subgraph H of G that contains X and avoids Y. We prove that if G is connected and locally k-edge-connected, then G is (s,t)-supereulerian, for any pair of nonnegative integers s and t with s+t≤k−1. We further show that if s+t≤k and G is a connected, locally k-edge-connected graph, then for any disjoint sets X,Y⊂E(G) with |X|≤s and |Y≤t, there is a spanning eulerian subgraph H that contains X and avoids Y, if and only if G−Y is not contractible to K₂ or to K_2,l with l odd.     

Minimal rankings and the arank number of a path

Given a graph G, a function f:V(G)→{1,2,…,k} is a k-ranking of G if f(u)=f(v) implies every u-v path contains a vertex w such that f(w)>f(u). A k-ranking is minimal if the reduction of any label greater than 1 violates the described ranking property. The arank number of a graph, denoted ψ_r(G), is the largest k such that G has a minimal k-ranking. We present new results involving minimal k-rankings of paths. In particular, we determine ψ_r(P_n), a problem posed by Laskar and Pillone in 2000.     

Minimum monopoly in regular and tree graphs

In this paper we consider a graph optimization problem called minimum monopoly problem, in which it is required to find a minimum cardinality set S⊆V, such that, for each u∈V, |N[u]∩S|?|N[u]|/2 in a given graph G=(V,E). We show that this optimization problem does not have a polynomial-time approximation scheme for k-regular graphs (k?5), unless P=NP. We show this by establishing two L-reductions (an approximation preserving reduction) from minimum dominating set problem for k-regular graphs to minimum monopoly problem for 2k-regular graphs and to minimum monopoly problem for (2k-1)-regular graphs, where k?3. We also show that, for tree graphs, a minimum monopoly set can be computed in linear time.     

Path bundles on n-cubes

A path bundle is a set of 2^a paths in an n-cube, denoted Q_n, such that every path has the same length, the paths partition the vertices of Q_n, the endpoints of the paths induce two subcubes of Q_n, and the endpoints of each path are complements. This paper shows that a path bundle exists if and only if n>0 is odd and 0?a?n-⌈log₂(n+1)⌉.     

The poset structures admitting the extended binary Golay code to be a perfect code

Brualdi et al. [Codes with a poset metric, Discrete Math. 147 (1995) 57-72] introduced the concept of poset codes, and gave an example of poset structure which admits the extended binary Golay code to be a 4-error-correcting perfect P-code. In this paper we classify all of the poset structures which admit the extended binary Golay code to be a 4-error-correcting perfect P-code, and show that there are no posets which admit the extended binary Golay code to be a 5-error-correcting perfect P-code.     

On the minimum real roots of the adjoint polynomial of a graph

For a graph G, we denote by h(G,x) the adjoint polynomial of G. Let β(G) denote the minimum real root of h(G,x). In this paper, we characterize all the connected graphs G with .