Fully polynomial-time approximation schemes for time–cost tradeoff problems in series–parallel project networks

We consider the deadline problem and budget problem of the nonlinear time–cost tradeoff project scheduling model in a series–parallel activity network. We develop fully polynomial-time approximation schemes for both problems using K-approximation sets and functions, together with series and parallel reductions.     

Enumeration and limit laws of dissections on a cylinder

We compute the generating function for triangulations on a cylinder, with the restriction that all vertices belong to its boundary and that the intersection of a pair of different faces is either empty, a vertex or an edge. We generalize these results to maps with either constant ({k}-dissections) or unrestricted (unrestricted dissections) face degree. We apply singularity analysis to the resulting generating functions to obtain asymptotic estimates for their coefficients, as well as limit distributions for natural parameters.     

Asymptotic enumeration and limit laws for graphs of fixed genus

It is shown that the number of labelled graphs with n vertices that can be embedded in the orientable surface Sg of genus g grows asymptotically like

c(g)n5(g−1)/2−1γnn!     

Enumeration problems for classes of self-similar graphs

We describe a general construction principle for a class of self-similar graphs. For various enumeration problems, we show that this construction leads to polynomial systems of recurrences and provide methods to solve these recurrences asymptotically. This is shown for different examples involving classical self-similar graphs such as the Sierpiński graphs. The enumeration problems we investigate include counting independent subsets, matchings and connected subsets.     

Limit laws for UGROW random graphs

Representations are found for a limit law L(Z(k,p))$L\left(Z(k,p)\right)$ obtained from an expanding sequence of random forests containing n$n$ nodes with p∈(0,1]$p\in (0,1]$ a probability controlling bond formation. One implies that Z(k,p)$Z(k,p)$ is stochastically decreasing as k$k$ increases and that norming gives an exponential limit law. Limit theorems are given for the order of component trees. The proofs exploit properties of the gamma function.     

Conservation laws for Lotka–Volterra models

We derive necessary and sufficient conditions on a Lotka–Volterra model to admit a conservation law of Volterra's type. The result and the proof for the corresponding linear algebra problem are given in graph‐theoretical terms; they refer to the directed graph which is defined by the coefficients of the differential equation system. Copyright © 2003 John Wiley & Sons, Ltd.     

Homomorphism–homogeneous graphs

We answer two open questions posed by Cameron and Nesetril concerning homomorphism–homogeneous graphs. In particular we show, by giving a characterization of these graphs, that extendability to monomorphism or to homomorphism leads to the same class of graphs when defining homomorphism–homogeneity. Further, we show that there are homomorphism–homogeneous graphs that do not contain the Rado graph as a spanning subgraph answering the second open question. We also treat the case of homomorphism–homogeneous graphs with loops allowed, showing that the corresponding decision problem is co–NP complete. Finally, we extend the list of considered morphism–types and show that the graphs for which monomorphisms can be extended to epimor‐phisms are complements of homomorphism–homogeneous graphs. © 2010 Wiley Periodicals, Inc. J Graph Theory 65: 253–261, 2010     

Enumeration of cyclic graphs and cyclic designs

The close relationship of cyclic graphs and cyclic designs is pointed out and used in the enumeration of cyclic graphs. An explicit formula is given for graphs with a prime number of vertices and a general constructive method of enumeration is developed. The problem is shown to be the same as that of enumerating cyclic paired-comparison designs which was previously considered by the author. The earlier results are extended and modified.     

p-Fractals and power series–I. Some 2 variable results

u₁,…,u_r are in kx₁,…,x_s with k and deg(u₁,…,u_r) finite. Intending applications to Hilbert–Kunz theory, we code the numbers into a function φ_u, which empirically satisfies many functional equations related to “magnification by p,” where p=chark. p-fractals, introduced here, formalize these ideas.In the first interesting case (r=3, s=2), the φ_u are p-fractals. Our proof uses functions φ_I attached to ideals I and square-free elements h of A=kx,y. The finiteness of the set of ideal classes in and the existence of “magnification maps” on this set show the φ_I to be p-fractals.We describe further functional equations coming from a theory of reflection maps on ideal classes, and the paper concludes with examples and open questions.     

Enumeration of labelled chain graphs and labelled essential directed acyclic graphs

A chain graph is a digraph whose strong components are undirected graphs and a directed acyclic graph (ADG or DAG) G is essential if the Markov equivalence class of G consists of only one element. We provide recurrence relations for counting labelled chain graphs by the number of chain components and vertices; labelled essential DAGs by the number of vertices. The second one is a lower bound for the number of labelled essential graphs. The formula for labelled chain graphs can be extended in such a way, that allows us to count digraphs with two additional properties, which essential graphs have.     

Conservation laws for the Black–Scholes equation

In the search for solutions to the important partial differential equation due to Black, Scholes and Merton potential symmetries are very useful as new solutions of the equation can be obtained as a result. These potential symmetries require that the equation be written in conserved form, ie. we need to determine conservation laws for the equation. We calculate the conservation laws utilizing the point symmetries of the equation following the method of Kara and Mahomed [A.H. Kara, F.M. Mahomed, The relationship between symmetries and conservation laws, Int. J. Theor. Phys. 39 (2000) 23–40].     

Enumeration of labeled bicyclic and tricyclic Eulerian graphs

Explicit formulas for the number of labeled bicyclic and tricyclic Eulerian graphs and for the number of labeled tricyclic Eulerian blocks are obtained. Many-vertex asymptotics for these numbers are found.     

Enumeration of labeled outerplanar bicyclic and tricyclic graphs

The class of outerplanar graphs is used for testing the average complexity of algorithms on graphs. A random labeled outerplanar graph can be generated by a polynomial algorithm based on the results of an enumeration of such graphs. By a bicyclic (tricyclic) graph we mean a connected graph with cyclomatic number 2 (respectively, 3). We find explicit formulas for the number of labeled connected outerplanar bicyclic and tricyclic graphs with n vertices and also obtain asymptotics for the number of these graphs for large n. Moreover, we obtain explicit formulas for the number of labeled outerplanar bicyclic and tricyclic n-vertex blocks and deduce the corresponding asymptotics for large n.     

Enumeration of graphs with signed points and lines

Our object is to enumerate graphs in which the points or lines or both are assigned positive or negative signs. We also treat several associated problems for which these configurations are self-dual with respect to sign change. We find that the solutions to all of these counting problems can be expressed as special cases of one general formula involving the concatenation of the cycle index of the symmetric group with that of its pair group. This counting technique is based on Pólya's Enumeration Theorem and the Power Group Enumeration Theorem. Using a suitable computer program, we list the number of graphs of each type considered up to twelve points. Sharp asymptotic estimates are also obtained.     

Central limit theorem and stable laws for intermittent maps

In the setting of abstract Markov maps, we prove results concerning the convergence of renormalized Birkhoff sums to normal laws or stable laws. They apply to one-dimensional maps with a neutral fixed point at 0 of the form x+x¹⁺, for (0, 1). In particular, for >1/2, we show that the Birkhoff sums of a Hölder observable f converge to a normal law or a stable law, depending on whether f(0)=0 or f(0)0. The proof uses spectral techniques introduced by Sarig, and Wieners Lemma in non-commutative Banach algebras.Mathematics Subject Classification (2000):37A30, 37A50, 37C30, 37E05, 47A56, 60F05     

Functional limit theorems for random regular graphs

Consider $d$ uniformly random permutation matrices on $n$ labels. Consider the sum of these matrices along with their transposes. The total can be interpreted as the adjacency matrix of a random regular graph of degree $2d$ on $n$ vertices. We consider limit theorems for various combinatorial and analytical properties of this graph (or the matrix) as $n$ grows to infinity, either when $d$ is kept fixed or grows slowly with $n$ . In a suitable weak convergence framework, we prove that the (finite but growing in length) sequences of the number of short cycles and of cyclically non-backtracking walks converge to distributional limits. We estimate the total variation distance from the limit using Stein’s method. As an application of these results we derive limits of linear functionals of the eigenvalues of the adjacency matrix. A key step in this latter derivation is an extension of the Kahn–Szemerédi argument for estimating the second largest eigenvalue for all values of $d$ and $n$ .     

Conservation laws for Camassa–Holm equation, Dullin–Gottwald–Holm equation and generalized Dullin–Gottwald–Holm equation

In this paper we construct the conservation laws for the Camassa–Holm equation, the Dullin–Gottwald–Holm equation (DGH) and the generalized Dullin–Gottwald–Holm equation (generalized DGH). The variational derivative approach is used to derive the conservation laws. Only first order multipliers are considered. Two multipliers are obtained for the Camassa–Holm equation. For the DGH and generalized DGH equations the variational derivative approach yields two multipliers; thus two conserved vectors are obtained.     

On greedy algorithms for series parallel graphs

This note describes some sufficient conditions for the maximum or minimum of a weighted flow (the weights are on paths, and are derived from weights on the edges of the path), of given volume in a series parallel graph to be found by a greedy algorithm.