Testing Cayley graph densities

We present a computer-assisted analysis of combinatorial properties of the Cayley graphs of certain finitely generated groups: Given a group with a finite set of generators, we study the density of the corresponding Cayley graph, that is, the least upper bound for the average vertex degree (= number of adjacent edges) of any finite subgraph. It is known that an m-generated group is amenable if and only if the density of the corresponding Cayley graph equals to 2m. We test amenable and non-amenable groups, and also groups for which amenability is unknown. In the latter class we focus on Richard Thompson’s group F.

Star factorizations of graph products

A k-star is the graph K-1,K-k. We prove a general theorem about k-star factorizations of Cayley graphs. This is used to give necessary and sufficient conditions for the existence of k-star factorizations of any power (K-q)(S) of a complete graph with prime power order q, products C-r1 x C-r2 x ... x C-rk of k cycles of arbitrary lengths, and any power (C-r)(S) of a cycle of arbitrary length. (C) 2001 John Wiley & Sons, Inc.

Hamilton decompositions of 6-regular abelian Cayley graphs

In 1969, Lovasz asked whether every connected, vertex-transitive graph has a Hamilton path. This question has generated a considerable amount of interest, yet remains vastly open. To date, there exist no known connected, vertex-transitive graph that does not possess a Hamilton path. For the Cayley graphs, a subclass of vertex-transitive graphs, the following conjecture was made: Weak Lovász Conjecture: Every nontrivial, finite, connected Cayley graph is hamiltonian. The Chen-Quimpo Theorem proves that Cayley graphs on abelian groups flourish with Hamilton cycles, thus prompting Alspach to make the following conjecture: Alspach Conjecture: Every 2k-regular, connected Cayley graph on a finite abelian group has a Hamilton decomposition. Alspach’s conjecture is true for k = 1 and 2, but even the case k = 3 is still open. It is this case that this thesis addresses. Chapters 1–3 give introductory material and past work on the conjecture. Chapter 3 investigates the relationship between 6-regular Cayley graphs and associated quotient graphs. A proof of Alspach’s conjecture is given for the odd order case when k = 3. Chapter 4 provides a proof of the conjecture for even order graphs with 3-element connection sets that have an element generating a subgroup of index 2, and having a linear dependency among the other generators. Chapter 5 shows that if Γ = Cay(A, {s1, s2, s3}) is a connected, 6-regular, abelian Cayley graph of even order, and for some1 ≤ i ≤ 3, Δi = Cay(A/(si), {sj1 , sj2}) is 4-regular, and Δi ≄ Cay(ℤ3, {1, 1}), then Γ has a Hamilton decomposition. Alternatively stated, if Γ = Cay(A, S) is a connected, 6-regular, abelian Cayley graph of even order, then Γ has a Hamilton decomposition if S has no involutions, and for some s ∈ S, Cay(A/(s), S) is 4-regular, and of order at least 4. Finally, the Appendices give computational data resulting from C and MAGMA programs used to generate Hamilton decompositions of certain non-isomorphic Cayley graphs on low order abelian groups.

Restricted walks in regular trees

Let T be the Cayley graph of a finitely generated free group F. Given two vertices in T consider all the walks of a given length between these vertices that at a certain time must follow a number of predetermined steps. We give formulas for the number of such walks by expressing the problem in terms of equations in F and solving the corresponding equations.

Computing the diameter of Coxeter groups

This thesis addresses the problem of computing the minimal and maximal diameter of the Cayley graph of Coxeter groups. We first present and assert relevant parts of polytope theory and related Coxeter theory. After this, a method of contracting the orthogonal projections of a polytope from Rd onto R2 and R3, d ¸ 3 is presented. This method is the Equality Set Projection algorithm that requires a constant number of linearprogramming problems per facet of the projection in the absence of degeneracy. The ESP algorithm allows us to compute also projected geometric diameters of high-dimensional polytopes. A representation set of projected polytopes is presented to illustrate the methods adopted in this thesis.

Galerkin finite element method for incompressible thermofluid flows framed within the bond graph theory

In this paper a bond graph methodology is used to model incompressible fluid flows with viscous and thermal effects. The distinctive characteristic of these flows is the role of pressure, which does not behave as a state variable but as a function that must act in such a way that the resulting velocity field has divergence zero. Velocity and entropy per unit volume are used as independent variables for a single-phase, single-component flow. Time-dependent nodal values and interpolation functions are introduced to represent the flow field, from which nodal vectors of velocity and entropy are defined as state variables. The system for momentum and continuity equations is coincident with the one obtained by using the Galerkin method for the weak formulation of the problem in finite elements. The integral incompressibility constraint is derived based on the integral conservation of mechanical energy. The weak formulation for thermal energy equation is modeled with true bond graph elements in terms of nodal vectors of temperature and entropy rates, resulting a Petrov-Galerkin method. The resulting bond graph shows the coupling between mechanical and thermal energy domains through the viscous dissipation term. All kind of boundary conditions are handled consistently and can be represented as generalized effort or flow sources. A procedure for causality assignment is derived for the resulting graph, satisfying the Second principle of Thermodynamics. (C) 2007 Elsevier B.V. All rights reserved.

Optimization and Complexity Reduction of Switch-Reconfigured Antennas Using Graph Models

This letter addresses the optimization and complexity reduction of switch-reconfigured antennas. A new optimization technique based on graph models is investigated. This technique is used to minimize the redundancy in a reconfigurable antenna structure and reduce its complexity. A graph modeling rule for switch-reconfigured antennas is proposed, and examples are presented.

Characterization of rat behavior in the elevated plus-maze using a directed graph

The elevated plus-maze is a device widely used to assess rodent anxiety under the effect of several treatments, including pharmacological agents. The animal is placed at the center of the apparatus, which consists of two open arms and two arms enclosed by walls, and the number of entries and duration of stay in each arm are measured for a 5-min exposure period. The effect of an anxiolytic drug is to increase the percentage of time spent and number of entries into the open arms. In this work, we propose a new measure of anxiety levels in the rat submitted to the elevated plus-maze. We represented the spatial structure of the elevated plus-maze in terms of a directed graph and studied the statistics of the rat`s transitions between the nodes of the graph. By counting the number of times each transition is made and ordering them in descending frequency we represented the rat`s behavior in a rank-frequency plot. Our results suggest that the curves obtained under different pharmacological conditions can be well fitted by a power law with an exponent sensitive to both the drug type and the dose used. (C) 2009 Elsevier B.V. All rights reserved.

R-matrices and the tensor product graph method

A systematic method for constructing trigonometric R-matrices corresponding to the (multiplicity-free) tensor product of any two affinizable representations of a quantum algebra or superalgebra has been developed by the Brisbane group and its collaborators. This method has been referred to as the Tensor Product Graph Method. Here we describe applications of this method to untwisted and twisted quantum affine superalgebras.