On hypohamiltonian graphs

Herz, Duby and Vigué [9] conjectured that every hypohamiltonian graph has girth 5. In the present note hypohamiltonian graphs of girth 3 and 4 are described. Also two conjectures on hypohamiltonian graphs made by Bondy and Chvátal, respectively, are disproved.     

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.     

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.     

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}}$

.     

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.     

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.     

Automorphism groups of designs with λ=1

If $G$ is a finite group and $k=q>2$ or $k=q+1$ for a prime power $q$ then, for infinitely many integers $v$, there is a 2-$(v,k,1)$-design $\mathbf{D}$ for which $\mathrm{Aut}\mathbf{D}?G$.     

The maximum multiplicity of the largest k-th eigenvalue in a matrix whose graph is acyclic or unicyclic

Given a graph $G$ we are interested in studying the symmetric matrices associated to $G$ with a fixed number of negative eigenvalues. For this class of matrices we focus on the maximum possible nullity. For trees this parameter has already been studied and plenty of applications are known. In this work we derive a formula for the maximum nullity and completely describe its behavior as a function of the number of negative eigenvalues. In addition, we also carefully describe the matrices associated with trees that attain this maximum nullity. The analysis is then extended to the more general class of unicyclic graphs. Further our work is applied to re-describing all possible partial inertias associated with trees, and is employed to study an instance of the inverse eigenvalue problem for certain trees.     

The n‐ordered graphs: A new graph class

For a positive integer n, we introduce the new graph class of n‐ordered graphs, which generalize partial n‐trees. Several characterizations are given for the finite n‐ordered graphs, including one via a combinatorial game. We introduce new countably infinite graphs R⁽ⁿ⁾, which we name the infinite random n‐ordered graphs. The graphs R⁽ⁿ⁾ play a crucial role in the theory of n‐ordered graphs, and are inspired by recent research on the web graph and the infinite random graph. We characterize R⁽ⁿ⁾ as a limit of a random process, and via an adjacency property and a certain folding operation. We prove that the induced subgraphs of R⁽ⁿ⁾ are exactly the countable n‐ordered graphs. We show that all countable groups embed in the automorphism group of R⁽ⁿ⁾. © 2008 Wiley Periodicals, Inc. J Graph Theory 60: 204–218, 2009     

Minimum degree condition for a graph to be knitted

For a positive integer $k$, a graph is $k$-knitted if for each subset $S$ of $k$ vertices, and every partition of $S$ into (disjoint) parts $S_1,\dots ,S_t$ for some $t\ge 1$, one can find disjoint connected subgraphs $C_1,\dots ,C_t$ such that $C_i$ contains $S_i$ for each $i\in \left[t\right]?\{1,2,\dots ,t\}$. In this article, we show that if the minimum degree of an $n$-vertex graph $G$ is at least $n∕2+k∕2?1$ when $n\ge 2k+3$, then $G$ is $k$-knitted. The minimum degree is sharp. As a corollary, we obtain that $k$-contraction-critical graphs are $?\frac{k}{8}?$-connected.     

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.     

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.