Indivisible plexes in latin squares

In this paper, we present two constructions of divisible difference sets based on skew Hadamard difference sets. A special class of Hadamard difference sets, which can be derived from a skew Hadamard difference set and a Paley type regular partial difference set respectively in two groups of orders v ₁ and v ₂ with |v ₁ − v ₂| = 2, is contained in these constructions. Some result on inequivalence of skew Hadamard difference sets is also given in the paper. As a consequence of Delsarte’s theorem, the dual set of skew Hadamard difference set is also a skew Hadamard difference set in an abelian group. We show that there are seven pairwisely inequivalent skew Hadamard difference sets in the elementary abelian group of order 3⁵ or 3⁷, and also at least four pairwisely inequivalent skew Hadamard difference sets in the elementary abelian group of order 3⁹. Furthermore, the skew Hadamard difference sets deduced by Ree-Tits slice symplectic spreads are the dual sets of each other when q ≤ 3¹¹.      

Paley type partial difference sets in non <Emphasis Type="Italic">p</Emphasis>-groups

By modifying a construction for Hadamard (Menon) difference sets we construct two infinite families of negative Latin square type partial difference sets in groups of the form where p is any odd prime. One of these families has the well-known Paley parameters, which had previously only been constructed in p-groups. This provides new constructions of Hadamard matrices and implies the existence of many new strongly regular graphs including some that are conference graphs. As a corollary, we are able to construct Paley–Hadamard difference sets of the Stanton-Sprott family in groups of the form when is a prime power. These are new parameters for such difference sets.      

Cyclic Relative Difference Sets and their p-Ranks

By modifying the constructions in Helleseth et al. [10] and No [15], we construct a family of cyclic ((q ^3k –1)/(q–1), q–1, q ^3k–1, q ^3k–2) relative difference sets, where q=3 ^e . These relative difference sets are liftings of the difference sets constructed in Helleseth et al. [10] and No [15]. In order to demonstrate that these relative difference sets are in general new, we compute p-ranks of the classical relative difference sets and 3-ranks of the newly constructed relative difference sets when q=3. By rank comparison, we show that the newly constructed relative difference sets are never equivalent to the classical relative difference sets, and are in general inequivalent to the affine GMW difference sets.     

On the p-Ranks of the Adjacency Matrices of Distance-Regular Graphs

Let be a distance-regular graph with adjacency matrix A. Let I be the identity matrix and J the all-1 matrix. Let p be a prime. We study the p-rank of the matrices A + bJ – cI for integral b, c and the p-rank of corresponding matrices of graphs cospectral with .Using the minimal polynomial of A and the theory of Smith normal forms we first determine which p-ranks of A follow directly from the spectrum and which, in general, do not. For the p-ranks that are not determined by the spectrum (the so-called relevant p-ranks) of A the actual structure of the graph can play a rôle, which means that these p-ranks can be used to distinguish between cospectral graphs.We study the relevant p-ranks for some classes of distance-regular graphs and try to characterize distance-regular graphs by their spectrum and some relevant p-rank.     

Paley type group schemes and planar Dembowski–Ostrom polynomials

In this paper we give some necessary and sufficient conditions for Dembowski–Ostrom polynomials to be planar. These conditions give a simple explanation of the Coulter–Matthews and Ding–Yin commutative semifields and enable us to obtain permutation polynomials from some of the Zha–Kyureghyan–Wang commutative semifields. We then give a generalization of Feng’s construction of Paley type group schemes in extra-special p-groups of exponent p and construct a family of Paley type group schemes in what we call the flag groups of finite fields. We also determine the strong multiplier groups of these group schemes. In the last section of this paper, we give a straightforward generalization of the twin prime power construction of difference sets to a construction of Hadamard designs from twin Paley type association schemes.     

Relative -difference sets in p-subgroups of

In this note, we study relative (p^a,p^b,p^a,p^a−b)-relative difference sets in certain p-subgroups of SL(n,K), K=F_q, where q is a prime power.     

A New Construction of Central Relative (p a , p a , p a , 1)-Difference Sets

Semiregular relative difference sets (RDS) in a finite group E which avoid a central subgroup C are equivalent to orthogonal cocycles. For example, every abelian semiregular RDS must arise from a symmetric orthogonal cocycle, and vice versa. Here, we introduce a new construction for central (p ^a , p ^a , p ^a , 1)-RDS which derives from a novel type of orthogonal cocycle, an LP cocycle, defined in terms of a linearised permutation (LP) polynomial and multiplication in a finite presemifield. The construction yields many new non-abelian (p ^a , p ^a , p ^a , 1)-RDS. We show that the subset of the LP cocycles defined by the identity LP polynomial and multiplication in a commutative semifield determines the known abelian (p ^a , p ^a , p ^a , 1)-RDS, and give a second new construction using presemifields.We use this cohomological approach to identify equivalence classes of central (p ^a , p ^a , p ^a , 1)-RDS with elementary abelian C and E/C. We show that for p = 2, a 3 and p = 3, a 2, every central (p ^a , p ^a , p ^a , 1)-RDS is equivalent to one arising from an LP cocycle, and list them all by equivalence class. For p = 2, a = 4, we list the 32 distinct equivalence classes which arise from field multiplication. We prove that, for any p, there are at least a equivalence classes of central (p ^a , p ^a , p ^a , 1)-RDS, of which one is abelian and a – 1 are non-abelian.     

Frame starters and adders in dicyclic groups

We construct frame starters in dicyclic groups Q_2n, in particular we construct frame starters with adders in Q_2q, where q = pⁿ and p ≡ 3 mod 4 is a prime. We also deduce the existence of strong frame starters in Z_2n for odd integers n whose prime factors are congruent with 1 modulo 4. The obtained results imply the constructions of classes of Room frames of types 4^p and 2ⁿ. © 1998 John Wiley & Sons, Inc. J Combin Designs 6: 347–353, 1998     

Strongly Regular Semi-Cayley Graphs

We consider strongly regular graphs = (V, E) on an even number, say 2n, of vertices which admit an automorphism group G of order n which has two orbits on V. Such graphs will be called strongly regular semi-Cayley graphs. For instance, the Petersen graph, the Hoffman–Singleton graph, and the triangular graphs T(q) with q 5 mod 8 provide examples which cannot be obtained as Cayley graphs. We give a representation of strongly regular semi-Cayley graphs in terms of suitable triples of elements in the group ring Z G. By applying characters of G, this approach allows us to obtain interesting nonexistence results if G is Abelian, in particular, if G is cyclic. For instance, if G is cyclic and n is odd, then all examples must have parameters of the form 2n = 4s ² + 4s + 2, k = 2s ² + s, = s ² – 1, and = s ²; examples are known only for s = 1, 2, and 4 (together with a noncyclic example for s = 3). We also apply our results to obtain new conditions for the existence of strongly regular Cayley graphs on an even number of vertices when the underlying group H has an Abelian normal subgroup of index 2. In particular, we show the nonexistence of nontrivial strongly regular Cayley graphs over dihedral and generalized quaternion groups, as well as over two series of non-Abelian 2-groups. Up to now these have been the only general nonexistence results for strongly regular Cayley graphs over non-Abelian groups; only the first of these cases was previously known.     

On the p-Ranks and Characteristic Polynomials of Cyclic Difference Sets

In this paper, the p-ranks and characteristic polynomials of cyclic difference sets are derived by expanding the trace expressions of their characteristic sequences. Using this method, it is shown that the 3-ranks and characteristic polynomials of the Helleseth–Kumar–Martinsen (HKM) difference set and the Lin difference set can be easily obtained. Also, the p-rank of a Singer difference set is reviewed and the characteristic polynomial is calculated using our approach.     

Commutative rings whose zero-divisor graph is a proper refinement of a star graph

A graph is called a proper refinement of a star graph if it is a refinement of a star graph, but it is neither a star graph nor a complete graph. For a refinement of a star graph G with center c, let G _c ^* be the subgraph of G induced on the vertex set V (G)\ {c or end vertices adjacent to c}. In this paper, we study the isomorphic classification of some finite commutative local rings R by investigating their zero-divisor graphs G = Γ(R), which is a proper refinement of a star graph with exactly one center c. We determine all finite commutative local rings R such that G _c ^* has at least two connected components. We prove that the diameter of the induced graph G _c ^* is two if Z(R)² ≠ {0}, Z(R)³ = {0} and G _c ^* is connected. We determine the structure of R which has two distinct nonadjacent vertices α, β ∈ Z(R)* \ {c} such that the ideal [N(α) ∩ N(β)]∪ {0} is generated by only one element of Z(R)*\{c}. We also completely determine the correspondence between commutative rings and finite complete graphs K _n with some end vertices adjacent to a single vertex of K _n .     

Flocks and Partial Flocks of Hyperbolic Quadrics via Root Systems

We construct three infinite families of partial flocks of sizes 12, 24 and 60 of the hyperbolic quadric of PG(3, q), for q congruent to -1 modulo 12, 24, 60 respectively, from the root systems of type D ₄, F ₄, H ₄, respectively. The smallest member of each of these families is an exceptional flock. We then characterise these partial flocks in terms of the rectangle condition of Benz and by not being subflocks of linear flocks or of Thas flocks. We also give an alternative characterisation in terms of admitting a regular group fixing all the lines of one of the reguli of the hyperbolic quadric.     

On geodesic structures of weakly median graphs I. Decomposition and octahedral graphs

We prove that the non-trivial (finite or infinite) weakly median graphs which are undecomposable with respect to gated amalgamation and Cartesian multiplication are the 5-wheels, the subhyperoctahedra different from K₁, the path K_1,2 and the 4-cycle K_2,2, and the two-connected K₄- and K_1,1,3-free bridged graphs. These prime graphs are exactly the weakly median graphs which do not have any proper gated subgraphs other than singletons. For finite graphs, these results were already proved in [H.-J. Bandelt, V.C. Chepoi, The algebra of metric betweenness I: subdirect representation, retracts, and axiomatics of weakly median graphs, preprint, 2002]. A graph G is said to have the half-space copoint property (HSCP) if every non-trivial half-space of the geodesic convexity of G is a copoint at each of its neighbors. It turns out that any median graph has the HSCP. We characterize the weakly median graphs having the HSCP. We prove that the class of these graphs is closed under gated amalgamation and Cartesian multiplication, and we describe the prime and the finite regular elements of this class.     

Cubic vertex‐transitive graphs of order 2pq

A graph is vertex?transitive or symmetric if its automorphism group acts transitively on vertices or ordered adjacent pairs of vertices of the graph, respectively. Let G be a finite group and S a subset of G such that 1?S and S={s^?1 | s∈S}. The Cayleygraph Cay(G, S) on G with respect to S is defined as the graph with vertex set G and edge set {{g, sg} | g∈G, s∈S}. Feng and Kwak [J Combin Theory B 97 (2007), 627–646; J Austral Math Soc 81 (2006), 153–164] classified all cubic symmetric graphs of order 4p or 2p² and in this article we classify all cubic symmetric graphs of order 2pq, where p and q are distinct odd primes. Furthermore, a classification of all cubic vertex‐transitive non‐Cayley graphs of order 2pq, which were investigated extensively in the literature, is given. As a result, among others, a classification of cubic vertex‐transitive graphs of order 2pq can be deduced. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 285–302, 2010     

On cubic non‐Cayley vertex‐transitive graphs

In 1983, the second author [D. Maru?i?, Ars Combinatoria 16B (1983), 297–302] asked for which positive integers n there exists a non‐Cayley vertex‐transitive graph on n vertices. (The term non‐Cayley numbers has later been given to such integers.) Motivated by this problem, Feng [Discrete Math 248 (2002), 265–269] asked to determine the smallest valency ?(n) among valencies of non‐Cayley vertex‐transitive graphs of order n. As cycles are clearly Cayley graphs, ?(n)?3 for any non‐Cayley number n. In this paper a goal is set to determine those non‐Cayley numbers n for which ?(n) = 3, and among the latter to determine those for which the generalized Petersen graphs are the only non‐Cayley vertex‐transitive graphs of order n. It is known that for a prime p every vertex‐transitive graph of order p, p² or p³ is a Cayley graph, and that, with the exception of the Coxeter graph, every cubic non‐Cayley vertex‐transitive graph of order 2p, 4p or 2p² is a generalized Petersen graph. In this paper the next natural step is taken by proving that every cubic non‐Cayley vertex‐transitive graph of order 4p², p>7 a prime, is a generalized Petersen graph. In addition, cubic non‐Cayley vertex‐transitive graphs of order 2p^k, where p>7 is a prime and k?p, are characterized. © 2011 Wiley Periodicals, Inc. J Graph Theory 69: 77–95, 2012     

An infinite family of octahedral crossing numbers

This paper calculates some crossing numbers for certain octahedral graphs. Precisely, if the number p is a prime power congruent to 1 modulo 4, then the crossing number of the p-dimensional octahedral graph in the orientable surface of genus (p–1)(p-4)/4 is (p²–p)/2. The key step is the construction of a self-dual imbedding of the complete graph on p vertices such that no face boundary contains a repeated vertex.     

Commutative presemifields and semifields

Strong conditions are derived for when two commutative presemifields are isotopic. It is then shown that any commutative presemifield of odd order can be described by a planar Dembowski-Ostrom polynomial and conversely, any planar Dembowski-Ostrom polynomial describes a commutative presemifield of odd order. These results allow a classification of all planar functions which describe presemifields isotopic to a finite field and of all planar functions which describe presemifields isotopic to Albert's commutative twisted fields. A classification of all planar Dembowski-Ostrom polynomials over any finite field of order p³, p an odd prime, is therefore obtained. The general theory developed in the article is then used to show the class of planar polynomials X¹⁰+aX⁶−a²X² with a≠0 describes precisely two new commutative presemifields of order e³ for each odd e?5.     

Classes of interval graphs under expanding length restrictions

Let C(α) denote the finite interval graphs representable as intersection graphs of closed real intervals with lengths in [1, α]. The points of increase for C are the rational α ≥ 1. The set D(α) = [∩_β>αC(β)]\C(α) of graphs that appear as soon as we go past α is characterized up to isomorphism on the basis of finite sets E(α) of irreducible graphs for each rational α. With α = p/q and p and q relatively prime, ∣E(α)∣ is computed for all (p,q) with q ? 2 and p = q + 1. When q = 1, E(p) contains only the bipartite star K¹, p_+2. A lowr bound on ∣E(α)∣ is given for all rational α.     

Distance-transitive dihedrants

The main result of this article is a classification of distance-transitive Cayley graphs on dihedral groups. We show that a Cayley graph X on a dihedral group is distance-transitive if and only if X is isomorphic to one of the following graphs: the complete graph K _2n ; a complete multipartite graph K _t×m with t anticliques of size m, where t m is even; the complete bipartite graph without 1-factor K _n,n − nK ₂; the cycle C _2n ; the incidence or the non-incidence graph of the projective geometry PG _d-1(d,q), d ≥ 2; the incidence or the non-incidence graph of a symmetric design on 11 vertices.