On Rosa-type labelings and cyclic graph decompositions

A labeling (or valuation) of a graph G is an assignment of integers to the vertices of G subject to certain conditions. A hierarchy of graph labelings was introduced by Rosa in the late 1960s. Rosa showed that certain basic labelings of a graph G with n edges yielded cyclic G-decompositions of K _2n+1 while other stricter labelings yielded cyclic G-decompositions of K _2nx+1 for all natural numbers x. Rosa-type labelings are labelings with applications to cyclic graph decompositions. We survey various Rosa-type labelings and summarize some of the related results. (Communicated by Peter Horák)     

Even subgraphs of bridgeless graphs and 2-factors of line graphs

By Petersen's theorem, a bridgeless cubic multigraph has a 2-factor. Fleischner generalised this result to bridgeless multigraphs of minimum degree at least three by showing that every such multigraph has a spanning even subgraph. Our main result is that every bridgeless simple graph with minimum degree at least three has a spanning even subgraph in which every component has at least four vertices. We deduce that if G is a simple bridgeless graph with n vertices and minimum degree at least three, then its line graph has a 2-factor with at most max{1,(3n-4)/10} components. This upper bound is best possible.     

两类图的(d,1)-全标号

主要讨论了W_n与C_m的笛卡尔积和均衡完全r-部图K_r(n)的(d,1)-全标号,并得出了(d,1)-全数λ_d~T(W_n□C_m)和λ_d~T(K_(r(n)))的确切值.     

The conjugacy problem for Dehn twist automorphisms of free groups

A Dehn twist automorphism of a group G is an automorphism which can be given (as specified below) in terms of a graph-of-groups decomposition of G with infinite cyclic edge groups. The classic example is that of an automorphism of the fundamental group of a surface which is induced by a Dehn twist homeomorphism of the surface. For , a non-abelian free group of finite rank n, a normal form for Dehn twist is developed, and it is shown that this can be used to solve the conjugacy problem for Dehn twist automorphisms of . Received: February 12, 1996.     

P4‐decompositions of regular graphs

In this article, we show that every simple r‐regular graph G admits a balanced P₄‐decomposition if r ≡ 0(mod 3) and G has no cut‐edge when r is odd. We also show that a connected 4‐regular graph G admits a P₄‐decomposition if and only if |E(G)| ≡ 0(mod 3) by characterizing graphs of maximum degree 4 that admit a triangle‐free Eulerian tour. © 1999 John Wiley & Sons, Inc. J Graph Theory 31: 135–143, 1999     

Resistance characterizations of equiarboreal graphs

A weighted (unweighted) graph $G$ is called equiarboreal if the sum of weights (the number) of spanning trees containing a given edge in $G$ is independent of the choice of edge. In this paper, we give some resistance characterizations of equiarboreal weighted and unweighted graphs, and obtain the necessary and sufficient conditions for $k$-subdivision graphs, iterated double graphs, line graphs of regular graphs and duals of planar graphs to be equiarboreal. Applying these results, we obtain new infinite families of equiarboreal graphs, including iterated double graphs of 1-walk-regular graphs, line graphs of triangle-free 2-walk-regular graphs, and duals of equiarboreal planar graphs.     

Integrated scheduling of crane handling and truck transportation in a maritime container terminal

This paper studies the interactions between crane handling and truck transportation in a maritime container terminal by addressing them simultaneously. Yard trucks are shared among different ships, which helps to reduce empty truck trips in the terminal area. The problem is formulated as a constraint programming model and a three-stage algorithm is developed. At the first stage, crane schedules are generated by a heuristic method. At the second stage, the multiple-truck routing problem is solved based on the precedence relations of the transportation tasks derived from the first stage. At the last stage a complete solution is constructed by using a disjunctive graph. The three procedures are linked by an iterative structure, which facilitates the search for a good solution. The computational results indicate that the three-stage algorithm is effective for finding high-quality solutions and can efficiently solve large problems.     

A presentation for reduced extended affine weyl groups

In 1985 K. Saito [Sal] introduced the concept of an extended affine Weyl group (EAWG), the Weyl group of an extended affine root system (EARS). In [A2, Section 5J, we gave a presentation called “a presentation by conjugation” for the class of EAWGs of index zero, a subclass of EAWGs. In this paper we will give a presentation wh.ich we call a “generalized present.ation by conjugation” for the class of reduced EAWGs. If the extended affine Weyl group is of index zero this presentation reduces to “a presentation by conjugation”. Our main result states that when the nullity of the EARS is 2, these two presentations coincide that is, EAWGs of nullity 2 have “a presentation by conjugation”. In [ST] another presentation for EAWGs of nullity 2 is given.