On the Euler sequence spaces which include the spaces ?p and ?∞ I

In the present paper, we introduce the Euler sequence space consisting of all sequences whose Euler transforms of order r are in the space ?_p of non-absolute type which is the BK-space including the space ?_p and prove that the spaces and ?_p are linearly isomorphic for 1 ? p ? ∞. Furthermore, we give some inclusion relations concerning the space . Finally, we determine the α-, β- and γ-duals of the space for 1 ? p ? ∞ and construct the basis for the space , where 1 ? p < ∞.     

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 .     

About acyclic edge colourings of planar graphs

Let G=(V,E) be any finite simple graph. A mapping is called an acyclic edge k-colouring of G, if any two adjacent edges have different colours and there are no bichromatic cycles in G. In other words, for every pair of distinct colours i and j, the subgraph induced by all the edges which have either colour i or j is acyclic. The smallest number k of colours, such that G has an acyclic edge k-colouring is called the acyclic chromatic index of G and is denoted by .In 1991, Alon et al. [N. Alon, C.J.H. McDiarmid, B.A. Reed, Acyclic coloring of graphs, Random Structures and Algorithms 2 (1991) 277-288] proved that for any graph G of maximum degree Δ(G). This bound was later improved to 16Δ(G) by Molloy and Reed in [M. Molloy, B. Reed, Further algorithmic aspects of the local lemma, in: Proceedings of the 30th Annual ACM Symposium on Theory of Computing, 1998, pp. 524-529].In this paper we prove that for a planar graph G without cycles of length three and that the same holds if G has an edge-partition into two forests. We also show that if G is planar.     

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 .     

On the complexity of digraph packings

Let be a fixed collection of digraphs. Given a digraph H, a -packing of H is a collection of vertex disjoint subgraphs of H, each isomorphic to a member of . For undirected graphs, Loebl and Poljak have completely characterized the complexity of deciding the existence of a perfect -packing, in the case that consists of two graphs one of which is a single edge on two vertices. We characterize -packing where consists of two digraphs one of which is a single arc on two vertices.     

Enhanced algorithms for Local Search

Let G=(V,E) be a finite graph, and be any function. The Local Search problem consists in finding a local minimum of the function f on G, that is a vertex v such that f(v) is not larger than the value of f on the neighbors of v in G. In this note, we first prove a separation theorem slightly stronger than the one of Gilbert, Hutchinson and Tarjan for graphs of constant genus. This result allows us to enhance a previously known deterministic algorithm for Local Search with query complexity , so that we obtain a deterministic query complexity of , where n is the size of G, d is its maximum degree, and g is its genus. We also give a quantum version of our algorithm, whose query complexity is of . Our deterministic and quantum algorithms have query complexities respectively smaller than the algorithm Randomized Steepest Descent of Aldous and Quantum Steepest Descent of Aaronson for large classes of graphs, including graphs of bounded genus and planar graphs.