Another class of balanced graph designs: balanced circuit designs

A block considered as a set of elements together with its adjacency matrix A is called a C-block if A is the adjacency matrix of a circuit. A balanced circuit design with parameters v, b, r, k, λ (briefly, BCD(v, k, λ)) is an arrangement of v elements into bC-blocks such that each C-block contains k elements, each element occurs in exactly rC-blocks and any two distinct elements are linked in exactly λ C-blocks.We investigate conditions for the existence of BCD and show, in particular, that if the block-size k ? 6 and the trivial necessary conditions are satisfied, then the corresponding BCD exists.     

Generalised Ramsey numbers for small graphs

The generalised Ramsey number R(G₁, G₂,..., G_k) is defined as the smallest integer n such that, if the edges of K_n, the complete graph on n vertices, are coloured using k colours C₁, C₂,..., C_k, then for some i(1≤i≤k) there is a subgraph G_i of K_n with all of its edges colour C_i. When G₁=G₂=...,G_k=G, we use the more compact notation R_k(G).The generalised Ramsey numbers R_k(G) are investigated for all graphs G having at most four vertices (and no isolates). This extends the work of Chvátal and Harary, who made this investigation in the case k=2.     

Minimal graphs with cyclic color group

We determine the minimum number of vertices an edge-colored graph must have, if its group of color preserving automorphisms is the cyclic group of order n.     

On the stabilizer subgroup of a fair of matrices

Let (F,G) be a pair of matrices defined over an arbitrary field, Fn × n, Gn × m. Consider the natural action of GL_n x GL_m on this pair given by (F,G) ? (gFg^-1,gGh^-1), where (g,h) ∈ GL_n × GL_m. This action is of interest in system theory as well as the representation theory of quivers. In this paper we study the stabilizer subgroup of this action stab(F,G), i.e.

$\text{{(g,h) ∈ GL}{}_{\mathrm{n}}\text{x GL}{}_{\mathrm{m}}\text{|gFg}{}^{-1}\text{= F,gGh}{}^{-1}\text{= G}}$

.     

r-tuple colorings of uniquely colorable graphs

An r-tuple coloring of a graph is one in which r colors are assigned to each point of the graph so that the sets of colors assigned to adjacent points are always disjoint. We investigate the question of whether a uniquely n-colorable graph can receive an r-tuple coloring with fewer than nr colors. We show that this cannot happen for n=3 and r=2 and that for a given n and r to establish the conjecture that no uniquely n-colorable graph can receive an r-tuple coloring from fewer than nr colors it suffices to prove it for on a finite set of uniquely n-colorable graphs.     

Classifying patterns by automorphism group: An operator theoretic approach

This paper considers the problem of enumerating the elements of a set under a group action with a given automorphism group. The problem is approached from a linear algebraic point of view, with a class of identities obtained by applications of appropriate linear operators and functionals. A variety of new counting and enumerating results are obtained in this manner, and the connections to the recent work of de Bruijn, Foulkes, Sheehan, Stockmeyer and White are defined. Included among the new results are general formulas for enumerating patterns with a given automorphism group when a group acts on the range and domain of a finite function space. In this case, the multilinear computing techniques developed by Williamson are exploited.     

Relations between the half turns of the hyperbolic plane

Let R_a denote the half turn about the point a of the hyperbolic plane H. If the points a, b, c, d lie on the same line and the pair (c, d) is obtained from the pair (a, b) by a translation, then we have R_aR_b = R_cR_d. We study the group G whose generating set is {R_a:a∈H} and whose defining relations are the ones mentioned above together with the relations R²_a = 1. We show that G can be made into a Lie group, G has two connected components, and its identity component G₀ is the universal covering group of PSL₂(R). In particular, it follows that all relations between the half turns in PSL₂(R) follow from the abovementioned relations and a single additional relation of length five.     

A consistency analysis for the numerical solution of boundary integral equations

A method is presented for assessing the nature of the error incurred in the boundary integral equation (BIE) solution of both harmonic and biharmonic boundary value problems (BVPs). It is shown to what order of accuracy the governing partial differential equation is actually represented by the approximating numerical scheme, and how raising the order of the boundary ‘shape functions’ affects this representation. The effect of varying both the magnitude and the aspect ratio of the solution domain is investigated; it is found that the present technique may suggest an optimum nondimensional scaling for the BIE solution of a particular harmonic or biharmonic BVP.     

Numerical solution of a nonlinear wave equation in polar coordinates

We study a finite element scheme and a difference scheme for the radial solutions of a nonlinear Klein-Gordon equation.     

DP-3-coloring of some planar graphs

In this article, we use a unified approach to prove several classes of planar graphs are DP-3-colorable, which extend the corresponding results on 3-choosability.     

Bounds on the number of Hamiltonian circuits in the n-cube

New upper and lower bounds are found for the number of Hamiltonian circuits in the graph of the n-cube.     

The lattice of quasivarieties of undirected graphs

In this note, it is shown that the quasivariety of undirected graphs is Q-universal. Received March 3, 2000; accepted in final form January 31, 2001.     

Note on 3-choosability of planar graphs with maximum degree 4

Deciding whether a planar graph (even of maximum degree 4) is 3-colorable is NP-complete. Determining subclasses of planar graphs being 3-colorable has a long history, but since Grötzsch’s result that triangle-free planar graphs are such, most of the effort was focused to solving Havel’s and Steinberg’s conjectures. In this paper, we prove that every planar graph obtained as a subgraph of the medial graph of any bipartite plane graph is 3-choosable. These graphs are allowed to have close triangles (even incident), and have no short cycles forbidden, hence representing an entirely different class than the graphs inferred by the above mentioned conjectures.