Topological formulation of termination properties of iterates of functions

We consider a number of decision problems, that appear in the dynamical systems and database literature, concerning the termination of iterates of real functions. These decision problems take a function as input and ask, for example, whether this function is mortal, nilpotent, terminating, or reaches a fixed point on a given point in . We associate topologies to functions and study some basic properties of these topologies. The contribution of this paper is a translation of the above mentioned decision problems into decision problems concerning well-known properties of topologies, e.g., connectivity. We also show that connectivity of topologies on is undecidable for n>1.     

The greedy algorithm for domination in graphs of maximum degree 3

We show that for a connected graph with n nodes and e edges and maximum degree at most 3, the size of the dominating set found by the greedy algorithm is at most if , if , and if .     

Fast computation of the Gauss hypergeometric function with all its parameters complex with application to the Pöschl-Teller-Ginocchio potential wave functions

The fast computation of the Gauss hypergeometric function with all its parameters complex is a difficult task. Although the function verifies numerous analytical properties involving power series expansions whose implementation is apparently immediate, their use is thwarted by instabilities induced by cancellations between very large terms. Furthermore, small areas of the complex plane, in the vicinity of , are inaccessible using power series linear transformations. In order to solve these problems, a generalization of R.C. Forrey's transformation theory has been developed. The latter has been successful in treating the function with real parameters. As in real case transformation theory, the large canceling terms occurring in analytical formulas are rigorously dealt with, but by way of a new method, directly applicable to the complex plane. Taylor series expansions are employed to enter complex areas outside the domain of validity of power series analytical formulas. The proposed algorithm, however, becomes unstable in general when |a|, |b|, |c| are moderate or large. As a physical application, the calculation of the wave functions of the analytical Pöschl-Teller-Ginocchio potential involving evaluations is considered.

Program summary

Program title: hyp_2F1, PTG_wfCatalogue identifier: AEAE_v1_0Program summary URL:http://cpc.cs.qub.ac.uk/summaries/AEAE_v1_0.htmlProgram obtainable from: CPC Program Library, Queen's University, Belfast, N. IrelandLicensing provisions: Standard CPC licence, http://cpc.cs.qub.ac.uk/licence/licence.htmlNo. of lines in distributed program, including test data, etc.: 6839No. of bytes in distributed program, including test data, etc.: 63 334Distribution format: tar.gzProgramming language: C++, Fortran 90Computer: Intel i686Operating system: Linux, WindowsWord size: 64 bitsClassification: 4.7Nature of problem: The Gauss hypergeometric function , with all its parameters complex, is uniquely calculated in the frame of transformation theory with power series summations, thus providing a very fast algorithm. The evaluation of the wave functions of the analytical Pöschl-Teller-Ginocchio potential is treated as a physical application.Solution method: The Gauss hypergeometric function verifies linear transformation formulas allowing consideration of arguments of a small modulus which then can be handled by a power series. They, however, give rise to indeterminate or numerically unstable cases, when b−a and c−a−b are equal or close to integers. They are properly dealt with through analytical manipulations of the Lanczos expression providing the Gamma function. The remaining zones of the complex plane uncovered by transformation formulas are dealt with Taylor expansions of the function around complex points where linear transformations can be employed. The Pöschl-Teller-Ginocchio potential wave functions are calculated directly with evaluations.Restrictions: The algorithm provides full numerical precision in almost all cases for |a|, |b|, and |c| of the order of one or smaller, but starts to be less precise or unstable when they increase, especially through a, b, and c imaginary parts. While it is possible to run the code for moderate or large |a|, |b|, and |c| and obtain satisfactory results for some specified values, the code is very likely to be unstable in this regime.Unusual features: Two different codes, one for the hypergeometric function and one for the Pöschl-Teller-Ginocchio potential wave functions, are provided in C++ and Fortran 90 versions.Running time: 20,000 function evaluations take an average of one second.     

On domination number of Cartesian product of directed cycles

Let γ(G) denote the domination number of a digraph G and let Cm□Cn denote the Cartesian product of Cm and Cn, the directed cycles of length m,n?2. In this paper, we determine the exact values: γ(C₂□Cn)=n; γ(C₃□Cn)=n if , otherwise, γ(C₃□Cn)=n+1; if , otherwise, .     

List edge and list total colorings of planar graphs without short cycles

Let G be a planar graph with maximum degree Δ(G). We use and to denote the list edge chromatic number and list total chromatic number of G, respectively. In this paper, it is proved that and if Δ(G)?6 and G has neither C₄ nor C₆, or Δ(G)?7 and G has neither C₅ nor C₆, where Ck is a cycle of length k.     

The 2-dipath chromatic number of Halin graphs

A 2-dipath k-coloring f of an oriented graph is a mapping from to the color set {1,2,…,k} such that f(x)≠f(y) whenever two vertices x and y are linked by a directed path of length 1 or 2. The 2-dipath chromatic number of is the smallest k such that has a 2-dipath k-coloring. In this paper we prove that if is an oriented Halin graph, then . There exist infinitely many oriented Halin graphs such that .