Even Orientations of Graphs: Part I

A graph G is 1-extendable if every edge belongs to at least one 1-factor. Let G be a graph with a 1-factor F. Then an even F-orientation of G is an orientation in which each F-alternating cycle has exactly an even number of edges directed in the same fixed direction around the cycle. In this paper, we examine the structure of 1-extendible graphs G which have no even F-orientation where F is a fixed 1-factor of G. In the case of cubic graphs we give a characterization. In a companion paper [M. Abreu, D. Labbate and J. Sheehan. Even orientations of graphs: Part II], we complete this characterization in the case of regular graphs, graphs of connectivity at least four and k--regular graphs for $kge3$. Moreover, we will point out a relationship between our results on even orientations and Pfaffian graphs developed in [M. Abreu, D. Labbate and J. Sheehan. Even orientations and Pfaffian graphs].

On the Ubiquity and Utility of Cyclic Schemes

Let $k,l,m,n$, and $mu$ be positive integers. A $mathbb{Z}_mu$--{it scheme of valency} $(k,l)$ and {it order} $(m,n)$ is a $m times n$ array $(S_{ij})$ of subsets $S_{ij} subseteq mathbb{Z}_mu$ such that for each row and column one has $sum_{j=1}^n |S_{ij}| = k $ and $sum_{i=1}^m |S_{ij}| = l$, respectively. Any such scheme is an algebraic equivalent of a $(k,l)$-semi-regular bipartite voltage graph with $n$ and $m$ vertices in the bipartition sets and voltages coming from the cyclic group $mathbb{Z}_mu$. We are interested in the subclass of $mathbb{Z}_mu$--schemes that are characterized by the property $a - b + c - d; ot equiv ;0$ (mod $mu$) for all $a in S_{ij}$, $b in S_{ih}$, $c in S_{gh}$, and $d in S_{gj}$ where $i,g in {1,...,m}$ and $j,h in {1,...,n}$ need not be distinct. These $mathbb{Z}_mu$--schemes can be used to represent adjacency matrices of regular graphs of girth $ge 5$ and semi-regular bipartite graphs of girth $ge 6$. For suitable $rho, sigma in mathbb{N}$ with $rho k = sigma l$, they also represent incidence matrices for polycyclic $(rho mu_k, sigma mu_l)$ configurations and, in particular, for all known Desarguesian elliptic semiplanes. Partial projective closures yield {it mixed $mathbb{Z}_mu$-schemes}, which allow new constructions for Krv{c}adinacs sporadic configuration of type $(34_6)$ and Balbuenas bipartite $(q-1)$-regular graphs of girth 6 on as few as $2(q^2-q-2)$ vertices, with $q$ ranging over prime powers. Besides some new results, this survey essentially furnishes new proofs in terms of (mixed) $mathbb{Z}_mu$--schemes for ad-hoc constructions used thus far.

Adjacency Matrices of Configuration Graphs

In 1960, Hoffman and Singleton cite{HS60} solved a celebrated equation for square matrices of order $n$, which can be written as $$ (kappa - 1) I_n + J_n - A A^{rm T} = A$$ where $I_n$, $J_n$, and $A$ are the identity matrix, the all one matrix, and a $(0,1)$--matrix with all row and column sums equal to $kappa$, respectively. If $A$ is an incidence matrix of some configuration $cal C$ of type $n_kappa$, then the left-hand side $Theta(A):= (kappa - 1)I_n + J_n - A A^{rm T}$ is an adjacency matrix of the non--collinearity graph $Gamma$ of $cal C$. In certain situations, $Theta(A)$ is also an incidence matrix of some $n_kappa$ configuration, namely the neighbourhood geometry of $Gamma$ introduced by Lef`evre-Percsy, Percsy, and Leemans cite{LPPL}. The matrix operator $Theta$ can be reiterated and we pose the problem of solving the generalised Hoffman--Singleton equation $Theta^m(A)=A$. In particular, we classify all $(0,1)$--matrices $M$ with all row and column sums equal to $kappa$, for $kappa = 3,4$, which are solutions of this equation. As a by--product, we obtain characterisations for incidence matrices of the configuration $10_3F$ in Kantors list cite{Kantor} and the $17_4$ configuration $#1971$ in Betten and Bettens list cite{BB99}.