Perfect dodecagon quadrangle systems

A dodecagon quadrangle is the graph consisting of two cycles: a 12-cycle (x₁,x₂,…,x₁₂) and a 4-cycle (x₁,x₄,x₇,x₁₀). A dodecagon quadrangle system of order n and index ρ [ DQS] is a pair (X,H), where X is a finite set of n vertices and H is a collection of edge disjoint dodecagon quadrangles (called blocks) which partitions the edge set of ρK_n, with vertex set X. A dodecagon quadrangle system of order n is said to be perfect [PDQS] if the collection of 4-cycles contained in the dodecagon quadrangles form a 4-cycle system of order n and index μ. In this paper we determine completely the spectrum of DQSs of index one and of PDQSs with the inside 4-cycle system of index one.     

4-cycle properties for characterizing rectagraphs and hypercubes

A (0, 2)-graph is a connected graph, where each pair of vertices has either 0 or 2 common neighbours. These graphs constitute a subclass of (0, λ)-graphs introduced by Mulder in 1979. A rectagraph, well known in diagram geometry, is a triangle-free (0, 2)-graph. (0, 2)-graphs include hypercubes, folded cube graphs and some particular graphs such as icosahedral graph, Shrikhande graph, Klein graph, Gewirtz graph, etc. In this paper, we give some local properties of 4-cycles in (0, λ)-graphs and more specifically in (0, 2)-graphs, leading to new characterizations of rectagraphs and hypercubes.     

Extending AG(4, 2) to S(4, {5, 6}, 17)

A construction of S(4, {5, 6}, 17) is given using the geometry of AG(4, 2) and PG(3, 2). © 1999 John Wiley & Sons, Inc. J Combin Designs 7: 113–117, 1999     

Spherically symmetric internal layers for activator-inhibitor systems—I. Existence by a Lyapunov-Schmidt reduction

Reaction-diffusion systems of activator-inhibitor type are studied on an N-dimensional ball with the homogeneous Neumann boundary conditions. Under the condition that the activator diffuses slowly, reacts rapidly and the inhibitor diffuses rapidly, reacts moderately, we show that the system admits a family of spherically symmetric internal transition layer equilibria. The method of proof consists of rigorous asymptotic expansions and a Lyapunov-Schmidt reduction.     

Covering relations for multidimensional dynamical systems—II

We use a topological technique based on covering relations to prove the existence of chaotic orbits for certain Hamiltonian systems with several degrees of freedom. This paper relies on an earlier work of Zgliczyński and Gidea.     

Jacobi polynomials and design theory I

In this paper, we introduce the notion of Jacobi polynomials of a code with multiple reference vectors, and give the MacWilliams type identity for it. Moreover, we derive a formula to obtain the Jacobi polynomials using the Aronhold polarization operator. Finally, we describe some facts obtained from Type III and Type IV codes that interpret the relation between the Jacobi polynomials and designs.     

A necessary 4-cycle condition for dice representability of reciprocal relations

The comparison of independent random variables can be modeled by a set of dice and a reciprocal relation expressing the winning probability of one dice over another. It is well known that dice transitivity is a necessary 3-cycle condition for a reciprocal relation to be dice representable, i.e. to be the winning probability relation of a set of dice. Although this 3-cycle condition is sufficient for a rational-valued reciprocal relation on a set of three elements to be dice representable, it has been shown that this is no longer the case for sets consisting of four or more elements. In this contribution, we provide a necessary 4-cycle condition for dice representability of reciprocal relations. Moreover, we show that our condition is sufficient in the sense that a given rational-weighted 4-cycle and reciprocally weighted inverse cycle, both fulfilling the 4-cycle condition, can be extended to a winning probability graph representing a dice-representable reciprocal relation on four elements.     

Every 4‐Colorable Graph With Maximum Degree 4 Has an Equitable 4‐Coloring

Chen et al., conjectured that for r≥3, the only connected graphs with maximum degree at most r that are not equitably r‐colorable are K_{r, r} (for odd r) and K_{r + 1}. If true, this would be a joint strengthening of the Hajnal–Szemerédi theorem and Brooks' theorem. Chen et al., proved that their conjecture holds for r = 3. In this article we study properties of the hypothetical minimum counter‐examples to this conjecture and the structure of “optimal” colorings of such graphs. Using these properties and structure, we show that the Chen–Lih–Wu Conjecture holds for r≤4. © 2011 Wiley Periodicals, Inc. J Graph Theory 71:31–48, 2012     

Tags on subsets

A new definition of a tag on a subset of a finite set is given. Tags were recently defined in a joint paper of the author and J.S. Chahal. The new definition considerably simplifies the concepts further. Relationship with lexicographic ordering is much more visible. Applications to a general (t,k) existence problem which includes the existence conjecture for t-designs or characterizing degree sequences of a k-uniform hypergraphs as particular cases is discussed. Some new necessary inequalities, as well as some sufficient conditions for such existence questions are derived.     

Equitable list coloring of planar graphs without 4- and 6-cycles

A graph G is equitably k-choosable if for any k-uniform list assignment L, there exists an L-colorable of G such that each color appears on at most vertices. Kostochka, Pelsmajer and West introduced this notion and conjectured that G is equitably k-choosable for k>Δ(G). We prove this for planar graphs with Δ(G)≥6 and no 4- or 6-cycles.     

Generating random graphs in biased Maker‐Breaker games

We present a general approach connecting biased Maker‐Breaker games and problems about local resilience in random graphs. We utilize this approach to prove new results and also to derive some known results about biased Maker‐Breaker games. In particular, we show that for , Maker can build a pancyclic graph (that is, a graph that contains cycles of every possible length) while playing a game on . As another application, we show that for , playing a game on , Maker can build a graph which contains copies of all spanning trees having maximum degree with a bare path of linear length (a bare path in a tree T is a path with all interior vertices of degree exactly two in T). © 2015 Wiley Periodicals, Inc. Random Struct. Alg., 47, 615–634, 2015     

Hitting time results for Maker‐Breaker games

We study Maker‐Breaker games played on the edge set of a random graph. Specifically, we analyze the moment a typical random graph process first becomes a Maker's win in a game in which Maker's goal is to build a graph which admits some monotone increasing property \begin{align*}\mathcal{P}\end{align*}. We focus on three natural target properties for Maker's graph, namely being k ‐vertex‐connected, admitting a perfect matching, and being Hamiltonian. We prove the following optimal hitting time results: with high probability Maker wins the k ‐vertex connectivity game exactly at the time the random graph process first reaches minimum degree 2k; with high probability Maker wins the perfect matching game exactly at the time the random graph process first reaches minimum degree 2; with high probability Maker wins the Hamiltonicity game exactly at the time the random graph process first reaches minimum degree 4. The latter two statements settle conjectures of Stojakovi? and Szabó. We also prove generalizations of the latter two results; these generalizations partially strengthen some known results in the theory of random graphs. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

All graphs with maximum degree three whose complements have 4-cycle decompositions

Let G be the set that contains precisely the graphs on n vertices with maximum degree 3 for which there exists a 4-cycle system of their complement in K_n. In this paper G is completely characterized.     

On the classification of all self-dual additive codes over GF(4) of length up to 12

We consider additive codes over GF(4) that are self-dual with respect to the Hermitian trace inner product. Such codes have a well-known interpretation as quantum codes and correspond to isotropic systems. It has also been shown that these codes can be represented as graphs, and that two codes are equivalent if and only if the corresponding graphs are equivalent with respect to local complementation and graph isomorphism. We use these facts to classify all codes of length up to 12, where previously only all codes of length up to 9 were known. We also classify all extremal Type II codes of length 14. Finally, we find that the smallest Type I and Type II codes with trivial automorphism group have length 9 and 12, respectively.     

Full Graphs and Koszul Algebras I

The main result of this article is the establishment of a new connection between combinatorics and noncommutative algebra. This is done by linking a certain class of directed graphs, called full graphs, to quotients of path algebras that are Koszul algebras.     

Equitable edge‐colorings of simple graphs

An edge‐coloring of a graph G is equitable if, for each v∈V(G), the number of edges colored with any one color incident with v differs from the number of edges colored with any other color incident with v by at most one. A new sufficient condition for equitable edge‐colorings of simple graphs is obtained. This result covers the previous results, which are due to Hilton and de Werra, verifies a conjecture made by Hilton recently, and substantially extends it to a more general class of graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 66:175‐197, 2011     

Equitable partitions of Latin‐square graphs

We study equitable partitions of Latin‐square graphs and give a complete classification of those whose quotient matrix does not have an eigenvalue ?3.     

A useful transform of standard input data for a classical NP-complete problem

The archetypal symmetric travelling salesman problem can be seen in a new and interesting way, by using first a standard preparatory phase of input data, and then by applying a transform from the set D of ‘distances’ among ‘cities’ and the set B of ‘loss of optimality’.The specific form of D→B transform is introduced and discussed. In order to show in realistic terms the interest of the approach proposed, a class of ‘diffusive’ heuristic procedures operating from B is defined.An example of solution by an algorithm included in this class is completely worked out; an outline of computational tests done on the same algorithm is also given.