On almost self-complementary graphs

A graph is called almost self-complementary if it is isomorphic to one of its almost complements X^c-I, where X^c denotes the complement of X and I a perfect matching (1-factor) in X^c. Almost self-complementary circulant graphs were first studied by Dobson and Šajna [Almost self-complementary circulant graphs, Discrete Math. 278 (2004) 23-44]. In this paper we investigate some of the properties and constructions of general almost self-complementary graphs. In particular, we give necessary and sufficient conditions on the order of an almost self-complementary regular graph, and construct infinite families of almost self-complementary regular graphs, almost self-complementary vertex-transitive graphs, and non-cyclically almost self-complementary circulant graphs.     

Halving Steiner 2-designs

A Steiner 2-design S(2,k,v) is said to be halvable if the block set can be partitioned into two isomorphic sets. This is equivalent to an edge-disjoint decomposition of a self-complementary graph G on v vertices into K_ks. The obvious necessary condition of those orders v for which there exists a halvable S(2,k,v) is that v admits the existence of an S(2,k,v) with an even number of blocks. In this paper, we give an asymptotic solution for various block sizes. We prove that for any k?5 or any Mersenne prime k, there is a constant number v₀ such that if v>v₀ and v satisfies the above necessary condition, then there exists a halvable S(2,k,v). We also show that a halvable S(2,2ⁿ,v) exists for over a half of possible orders. Some recursive constructions generating infinitely many new halvable Steiner 2-designs are also presented.     

Self-complementary magic squares of doubly even orders

A magic square $M$ in which the entries consist of consecutive integers from $1,2,\dots ,n^2$ is said to be self-complementary of order$n$ if the resulting square obtained from $M$ by replacing each entry $i$ by $n^2+1?i$ is equivalent to $M$ (under rotation or reflection). We present a new construction for self-complementary magic squares of order $n$ for each $n\ge 4$, where $n$ is a multiple of $4$.     

Vertex-transitive self-complementary uniform hypergraphs of prime order

For an integer n and a prime p, let . In this paper, we present a construction for vertex-transitive self-complementary k-uniform hypergraphs of order n for each integer n such that for every prime p, where ?=max{k₍₂₎,(k−1)₍₂₎}, and consequently we prove that the necessary conditions on the order of vertex-transitive self-complementary uniform hypergraphs of rank k=2^? or k=2^?+1 due to Potoňick and Šajna are sufficient. In addition, we use Burnside’s characterization of transitive groups of prime degree to characterize the structure of vertex-transitive self-complementary k-hypergraphs which have prime order p in the case where k=2^? or k=2^?+1 and , and we present an algorithm to generate all of these structures. We obtain a bound on the number of distinct vertex-transitive self-complementary graphs of prime order , up to isomorphism.     

Indecomposable laplacian integral graphs

A graph that can be constructed from isolated vertices by the operations of union and complement is decomposable. Every decomposable graph is Laplacian integral. i.e., its Laplacian spectrum consists entirely of integers. An indecomposable graph is not decomposable. The main purpose of this note is to demonstrate the existence of infinitely many indecomposable Laplacian integral graphs.     

New classes of self-complementary codes and quasi-symmetric designs

We present a new technique for constructing binary error correcting codes and give some examples of codes that can be constructed via this method. Among the examples is an infinite family of self-complementary codes with parameters (2u ²−u, 8u ², u ²−u) that can be constructed whenever there exists a u × u Hadamard Matrix. These codes meet the Grey–Rankin bound and imply the existence of quasi-symmetric designs on 2u ²−u points.     

The existence of regular self-complementary 3-uniform hypergraphs

A k-uniform hypergraph with vertex set V and edge set E is called t-subset-regular if every t-element subset of V lies in the same number of elements of E. In this paper we show that a 1-subset-regular self-complementary 3-uniform hypergraph with n vertices exists if and only if n≥5 and n is congruent to 1 or 2 modulo 4.     

The least prior deviation quasi-Newton update

We propose a new choice for the parameter in the Broyden class and derive and discuss properties of the resulting self-complementary quasi-Newton update. Our derivation uses a variational principle that minimizes the extent to which the quasi-Newton relation is violated on a prior step. We discuss the merits of the variational principle used here vis-a-vis the other principle in common use, which minimizes deviation from the current Hessian or Hessian inverse approximation in an appropriate Frobenius matrix norm. One notable advantage of our principle is an inherent symmetry that results in the same update being obtained regardless of whether the Hessian matrix or the inverse Hessian matrix is updated.We describe the relationship of our update to the BFGS, SR1 and DFP updates under particular assumptions on line search accuracy, type of function being minimized (quadratic or nonquadratic) and norm used in the variational principle.Some considerations concerning implementation are discussed and we also give a numerical illustration based on an experimental implementation using MATLAB.Corresponding author.     

Steiner almost self-complementary graphs and halving near-Steiner triple systems

We show that for every admissible order v≡0 or there exists a near-Steiner triple system of order v that can be halved. As a corollary we obtain that a Steiner almost self-complementary graph with n vertices exists if and only if n≡0 or .