By applying geometric techniques to real analytic singularly perturbed vector fields on the plane, we develop a way to give a bound on the Gevrey type of the Taylor development of canard manifolds at degenerate planar turning points. By blowing up the phase space at the turning point, we find asymptotic estimates even when such expansions w.r.t. traditional phase space variables do not exist. The asymptotic estimates are then used to give a sufficient and necessary condition on the existence of (local) canard solutions. 相似文献
Let P(G,λ) be the chromatic polynomial of a graph G with n vertices, independence number α and clique number ω. We show that for every λ≥n, ()α≤≤ ()n−ω. We characterize the graphs that yield the lower bound or the upper bound.?These results give new bounds on the mean colour
number μ(G) of G: n− (n−ω)()n−ω≤μ(G)≤n−α() α.
Received: December 12, 2000 / Accepted: October 18, 2001?Published online February 14, 2002 相似文献
A tree T is arbitrarily vertex decomposable if for any sequence τ of positive integers adding up to the order of T there is a sequence of vertex-disjoint subtrees of T whose orders are given by τ. An on-line version of the problem of characterizing arbitrarily vertex decomposable trees is completely solved here. 相似文献
The notion of balanced bipartitions of the vertices in a tree T was introduced and studied by Reid (Networks 34 (1999) 264). Reid proved that the set of balance vertices of a tree T consists of a single vertex or two adjacent vertices. In this note, we give a simple proof of that result. 相似文献
Cubic bridgeless graphs with chromatic index four are called uncolorable. We introduce parameters measuring the uncolorability of those graphs and relate them to each other. For k=2,3, let ck be the maximum size of a k-colorable subgraph of a cubic graph G=(V,E). We consider r3=|E|−c3 and
. We show that on one side r3 and r2 bound each other, but on the other side that the difference between them can be arbitrarily large. We also compare them to the oddness ω of G, the smallest possible number of odd circuits in a 2-factor of G. We construct cyclically 5-edge connected cubic graphs where r3 and ω are arbitrarily far apart, and show that for each 1c<2 there is a cubic graph such that ωcr3. For k=2,3, let ζk denote the largest fraction of edges that can be k-colored. We give best possible bounds for these parameters, and relate them to each other. 相似文献
This paper investigates the existence of positive solutions of a singular boundary value problem with negative exponent similar
to standard Emden-Fowler equation. A necessary and sufficient condition for the existence of C[0, 1] positive solutions as
well as C1[0, 1] positive solutions is given by means of the method of lower and upper solutions with the Schauder fixed point theorem. 相似文献
The eigenvalue and the stability of singular differential systems with delay are considered. Firstly we investigate some properties of the eigenvalue, then give the exact exponential estimation for the fundamental solution, and finally discuss the necessary and sufficient condition of uniform asymptotic stability. 相似文献
In this paper, some multiplicity results for positive solutions of some singular semi-positone three-point boundary value problem be obtained by using the fixed point index method. 相似文献
A model for parallel and distributed programs, the dynamic process graph (DPG), is investigated under graph-theoretic and complexity aspects. Such graphs embed constructors for parallel programs, synchronization mechanisms as well as conditional branches. They are capable of representing all possible executions of a parallel or distributed program in a very compact way. The size of this representation can be as small as logarithmic with respect to the size of any execution of the program.
In a preceding paper [A. Jakoby, et al., Scheduling dynamic graphs, in: Proc. 16th Symposium on Theoretical Aspects in Computer Science STACS'99, LNCS, vol. 1563, Springer, 1999, pp. 383–392] we have analysed the expressive power of the general model and various variants of it. We have considered the scheduling problem for DPGs given enough parallelism taking into account communication delays between processors when exchanging data. Given a DPG the question arises whether it can be executed (that means whether the corresponding parallel program has been specified correctly), and what is its minimum schedule length.
In this paper we study a subclass of dynamic process graphs called
-output DPGs, which are appropriate in many situations, and investigate their expressive power. In a previous paper we have shown that the problem to determine the minimum schedule length is still intractable for this subclass, namely this problem is
-complete as is the general case. Here we will investigate structural properties of the executions of such graphs. A natural graph-theoretic conjecture that executions must always split into components that are isomorphic to subgraphs turns out to be wrong. We are able to prove a weaker property. This implies a quadratic upper bound on the schedule length that may be necessary in the worst case, in contrast to the general case, where the optimal schedule length may be exponential with respect to the size of the representing DPG. Making this bound constructive, we obtain an approximation to a
-complete problem. Computing such a schedule and then executing the program can be done on a parallel machine in polynomial time in a highly distributive fashion. 相似文献