Domatic partitions of computable graphs

Given a graph G, we say that a subset D of the vertex set V is a dominating set if it is near all the vertices, in that every vertex outside of D is adjacent to a vertex in D. A domatic k-partition of G is a partition of V into k dominating sets. In this paper, we will consider issues of computability related to domatic partitions of computable graphs. Our investigation will center on answering two types of questions for the case when k = 3. First, if domatic 3-partitions exist in a computable graph, how complicated can they be? Second, a decision problem: given a graph, how difficult is it to decide whether it has a domatic 3-partition? We will completely classify this decision problem for highly computable graphs, locally finite computable graphs, and computable graphs in general. Specifically, we show the decision problems for these kinds of graphs to be ${\Pi^{0}_{1}}$ -, ${\Pi^{0}_{2}}$ -, and ${\Sigma^{1}_{1}}$ -complete, respectively.     

On determination of graph G whose bond lattice ℒ(G) is modular

We shall prove that a bond lattice ℒ(G) of a graph G is Boolean if and only if G is a forest, and that a bond lattice ℒ(G) is modular if and only if G has no cycle of length n>3.     

Spaces of orders and their Turing degree spectra

We investigate computability theoretic and topological properties of spaces of orders on computable orderable groups. A left order on a group G is a linear order of the domain of G, which is left-invariant under the group operation. Right orders and bi-orders are defined similarly. In particular, we study groups for which the spaces of left orders are homeomorphic to the Cantor set, and their Turing degree spectra contain certain upper cones of degrees. Our approach unifies and extends Sikora’s (2004) [28] investigation of orders on groups in topology and Solomon’s (2002) [31] investigation of these orders in computable algebra. Furthermore, we establish that a computable free group F_n of rank n>1 has a bi-order in every Turing degree.     

Complexities of Winning Strategies in Diophantine Games

This paper considers the computational complexity of computing winning strategies in diophantine games, where two players take turns choosing natural numbers x₁, x₂, x₃, . . . , x_n and the win condition is a polynomial equation in the variables x₁, x₂, . . . , x_n. A diophantine game G₄ of length 4 is constructed with the propertythat neither player has a polynomial time computable winning strategy. Also a diophantine game G₆ of length 6 is constructed with the property that one of the players has a polynomial time computable winning strategy in G₆ iff P = NP. Finally a diophantine game N_b of length 6 is constructed such that one of the players has a polynomial time computable winning strategy in it iff co-NP = NP.     

Sufficient conditions for the existence of 0’-limitwise monotonic functions for computable <Emphasis Type="Italic">η</Emphasis>-like linear orders

We find new sufficient conditions for the existence of a 0’-limitwise monotonic function defining the order for a computable η-like linear order L, i.e., of a function G such that L ∑ _q∈? G(q). Namely, we define the notions of left local maximal block and right local maximal block and prove that if the sizes of these blocks in a computable η-like linear order L are bounded then there is a 0’-limitwise monotonic function G with L = ∑ _q∈? G(q).     

On graphs whose square have strong hamiltonian properties

The squareG² of a graph G is the graph having the same vertex set as G and two vertices are adjacent if and only if they are at distance at most 2 from each other. It is known that if G has no cut-vertex, then G² is Hamilton-connected (see [G. Chartrand, A.M. Hobbs, H.A. Jung, S.F. Kapoor, C.St.J.A. Nash-Williams, The square of a block is hamiltonian connected, J. Combin. Theory Ser. B 16 (1974) 290-292; R.J. Faudree and R.H. Schelp, The square of a block is strongly path connected, J. Combin. Theory Ser. B 20 (1976) 47-61]). We prove that if G has only one cut-vertex, then G² is Hamilton-connected. In the case that G has only two cut-vertices, we prove that if the block that contains the two cut-vertices is hamiltonian, then G² is Hamilton-connected. Further, we characterize all graphs with at most one cycle having Hamilton-connected square.     

Group Rings with Solvable Unit Groups of Minimal Derived Length

Let F be a field of characteristic p > 2 and G a nonabelian nilpotent group containing elements of order p. Write F G for the group ring. The conditions under which the unit group ??(F G) is solvable are known, but only a few results have been proved concerning its derived length. It has been established that if G is torsion, the minimum derived length is ?log₂(p + 1)?, and this minimum occurs if and only if |G′| = p. In the present note, we show that the same holds if G has elements of infinite order.     

Metric properties on Lie groups of polynomial volume growth

It is well known that we have an algebraic characterization of connected Lie groups of polynomial volume growth: a Lie group G has polynomial volume growth if and only if it is of type R. In this paper, we shall give a geometric characterization of connected Lie groups of polynomial volume growth in terms of the distance distortion of the subgroups. More precisely, we prove that a connected Lie group G has polynomial volume growth if and only if every closed subgroup has a polynomial distortion in G.     

On the genus and thickness of graphs

The genus γ(G) of a simple graph G is the minimum genus of the orientable surface on which G is embeddable. The thickness θ(G) of G is the minimum number of planar subgraphs of G whose union is G. From the definitions, it is clear that θ(G) = 1 if and only if γ(G) = 0. In this paper, we will show that θ(G) ≦ γ(G) + 1, if G has no triangle or if G is toroidal.     

The similarity problem for Fourier algebras and corepresentations of group von Neumann algebras

Let G be a locally compact group, and let A(G) and VN(G) be its Fourier algebra and group von Neumann algebra, respectively. In this paper we consider the similarity problem for A(G): Is every bounded representation of A(G) on a Hilbert space H similar to a *-representation? We show that the similarity problem for A(G) has a negative answer if and only if there is a bounded representation of A(G) which is not completely bounded. For groups with small invariant neighborhoods (i.e. SIN groups) we show that a representation π:A(G)→B(H) is similar to a *-representation if and only if it is completely bounded. This, in particular, implies that corepresentations of VN(G) associated to non-degenerate completely bounded representations of A(G) are similar to unitary corepresentations. We also show that if G is a SIN, maximally almost periodic, or totally disconnected group, then a representation of A(G) is a *-representation if and only if it is a complete contraction. These results partially answer questions posed in Effros and Ruan (2003) [7] and Spronk (2002) [25].     

Computability of finite-dimensional linear subspaces and best approximation

We discuss computability properties of the set P_G(x) of elements of best approximation of some point x∈X by elements of G⊆X in computable Banach spaces X. It turns out that for a general closed set G, given by its distance function, we can only obtain negative information about P_G(x) as a closed set. In the case that G is finite-dimensional, one can compute negative information on P_G(x) as a compact set. This implies that one can compute the point in P_G(x) whenever it is uniquely determined. This is also possible for a wider class of subsets G, given that one imposes additionally convexity properties on the space. If the Banach space X is computably uniformly convex and G is convex, then one can compute the uniquely determined point in P_G(x). We also discuss representations of finite-dimensional subspaces of Banach spaces and we show that a basis representation contains the same information as the representation via distance functions enriched by the dimension. Finally, we study computability properties of the dimension and the codimension map and we show that for finite-dimensional spaces X the dimension is computable, given the distance function of the subspace.     

Graphs with 1-Hamiltonian-connected cubes

The cube G³ of a connected graph G is that graph having the same vertex set as G and in which two distinct vertices are adjacent if and only if their distance in G is at most three. A Hamiltonian-connected graph has the property that every two distinct vertices are joined by a Hamiltonian path. A graph G is 1-Hamiltonian-connected if, for every vertex w of G, the graphs G and G?w are Hamiltonian-connected. A characterization of graphs whose cubes are 1-Hamiltonian-connected is presented.     

A fixed point theorem for exponentially bounded groups

A fixed point property for linear actions of locally compact groups is presented. It is shown, in particular, that if G is either a finitely generated, discrete solvable group or a connected group then G has this fixed point property if, and only if, G is exponentially bounded.     

On 1-factors of point determining graphs

A graph G is said to be point determining if and only if distinct points of G have distinct neighborhoods. For such a graph G, the nucleus is defined to be the set G″ consisting of all points ν of G for which G-ν is a point determining graph.In [4], Summer exhibited several families of graphs H such that if G⁰ = H, for some point determining graph G, then G has a 1-factor. In this paper, we extend this class of graphs.     

Characterization of self-complementary graphs with 2-factors

Let G be a self-complementary graph (s.c.) and π its degree sequence. Then G has a 2-factor if and only if π - 2 is graphic. This is achieved by obtaining a structure theorem regarding s.c. graphs without a 2-factor. Another interesting corollary of the structure theorem is that if G is a s.c. graph of order p?8 with minimum degree at least $\text{p}\text{4}$, then G has a 2-factor and the result is the best possible.     

The book thickness of a graph

The book thickness bt(G) of a graph G is defined, its basic properties are delineated, and relations are given with other invariants such as thickness, genus, and chromatic number. A graph G has book thickness bt(G) ≤ 2 if and only if it is a subgraph of a hamiltonian planar graph, but we conjecture that there are planar graphs with arbitrarily high book thickness.     

A descent principle for the Dirac-dual-Dirac method

Let G be a torsion-free discrete group with a finite-dimensional classifying space BG. We show that G has a dual-Dirac morphism if and only if a certain coarse (co-)assembly map is an isomorphism. Hence the existence of a dual-Dirac morphism for such groups is a metric, that is, coarse, invariant. We get results for groups with torsion as well.     

The existence of even factors in iterated line graphs

An even factor of a graph is a spanning subgraph of G in which all degrees are even, positive integers. In this paper, we characterize the claw-free graphs having even factors and then prove that the n-iterated line graph Lⁿ(G) of G has an even factor if and only if every end branch of G has length at most n and every odd branch-bond of G has a branch of length at most n+1.     

Fixed point property for Banach algebras associated to locally compact groups

In this paper we investigate when various Banach algebras associated to a locally compact group G have the weak or weak^∗ fixed point property for left reversible semigroups. We proved, for example, that if G is a separable locally compact group with a compact neighborhood of the identity invariant under inner automorphisms, then the Fourier-Stieltjes algebra of G has the weak^∗ fixed point property for left reversible semigroups if and only if G is compact. This generalizes a classical result of T.C. Lim for the case when G is the circle group T.     

On coverings in the lattice of all group topologies of arbitrary Abelian groups

The remainder of the completion of a topological abelian group (G, τ₀) contains a nonzero element of prime order if and only if G admits a Hausdorff group topology τ₁ that precedes the given topology and is such that (G, τ₀) has no base of closed zero neighborhoods in (G, τ₁).