Constructions of covering triangulations with folds

Let G be a graph with a known triangular embedding in a surface S, and consider G_(m), the composition of G with an independant set of order m. The purpose of this paper is to construct a triangular embedding of G_(m) into a surface by using a covering triangulation with folds. We make the construction for three cases. One of them is used for proving that G_(m) can be triangularly embedded into a surface if G is an Eulerian graph which can be triangularly embedded into a surface S with the same orientability characteristic as .     

The Forwarding Indices of Random Graphs

A routing R of a graph G is a set of n(n ? 1) elementary paths R(u, v) specified for all ordered pairs (u, v) of vertices of G. The vertex-forwarding index ξ(G) of G, is defined by Where ξ(G, R) is the maximum number of paths of the routing R passing through any vertex of G and the minimum is taken over all the routings of G. Let G_p denote the random graph on n vertices with edge probability p and let m = np. It is proved among other things that, under natural growth conditions on the function p = p(n), the ratio Tends to 1 in probability as n tends to infinity.     

A power law for connectedness of some random graphs at the critical point

We consider P(G is connected) when G is a graph with vertex set Z⁺ = {1,2, …}, and the edge between i and j is present with probability p(i, j) = min(λ h(i, j), 1) for certain functions h(i, j) homogeneous of degree -1. It is known that there is a critical value λ_c of λ such that . We show that the probability, at the critical point λ_c, that n₁, and n₂ are connected satisfies a power law, in the sense that for n₂ ≧ n_t ≧ 1 for any δ > 0 and certain constants c₁ and c₂.     

Hamilton cycles in claw-free graphs

Bondy conjectured that if G is a k-connected graph of order n such that for any (k + 1)-independent set / of G, then the subgraph outside any longest cycle contains no path of length k ? 1. In this paper, we are going to prove that, if G is a k-connected claw-free (K_1,3-free) graph of order n such that for any (k + 1)-independent set /, then G contains a Hamilton cycle. The theorem in this paper implies Bondy's conjecture in the case of claw-free graphs.     

Periodic solutions of quasilinear non-autonomous systems with impulses

The paper considers a system of differential equations with impulse perturbations at fixed moments in time of the form where x ? R ⁿ, ε is a small parameter, Sufficient conditions have been found for existence of the periodic solution of the given system in the critical and non-critical cases.     

Fractional colorings with large denominators

The m-chromatic number χ_m(G) of a graph G is the fewest colors needed so each node has m colors and no color appears on adjacent nodes. The fractional chromatic number is χ*(G)=lim_m→∞χ_m(G)/m. Let m(G) be the least m so that χ* (G) = χ_m(G)/m. For n node graphs, Chvátal, Garey and Johnson showed m(G) ≦ n^n/2 and gave example, where m(G) is asymptotically . This note gives examples where m(G) is asymptotically λⁿ, where λ ≈? 1.346193. © 1995 John Wiley & Sons, Inc.     

Maximum Bandwidth Under Edge Addition

We determine how much the bandwidth B(G) of a graph G can increase when a single edge is added. Let g(b,n) be the maximum possible value of B(G + e) when G has n vertices and bandwidth b. The problem of studying when B(G + e) ≦ B (G) + 1 was originally possed by Erdos. We determine © 1996 John Wiley & Sons, Inc.     

Bounds for the ramsey number of a disconnected graph versus any graph

Bounds are determined for the Ramsey number of the union of graphs versus a fixed graph H, based on the Ramsey number of the components versus H. For certain unions of graphs, the exact Ramsey number is determined. From these formulas, some new Ramsey numbers are indicated. In particular, if . Where k_i is the number of components of order i and t₁ (H) is the minimum order of a color class over all critical colorings of the vertices of H, then .     

Stability and Oscillations of Solutions of Integro-Differential Equations of Pendulum—like Systems

A system of nonlinear differential equations of the type on a domain of ?ⁿ is studied. Functional relations between the f_j's, j = 1, …, n, and other necessary conditions are deduced when at each point of the domain the system has a manifold of local solutions. A structure theorem, that makes possible to reduce the problems of the system, e.g. the global solvability of it, to the corresponding questions for a connection of the type ?_z?w = g(z, w) in a fibre bundle over a Riemann surface is proved, and through this reduction we obtain theorems of identity, extension, global factorization, and so on, for the solutions of the system. As an example, a system of nonlinear differential equations of the type is studied and its global solutions are constructed.     

On the distance matrix of a directed graph

In this note, we show how the determinant of the distance matrix D(G) of a weighted, directed graph G can be explicitly expressed in terms of the corresponding determinants for the (strong) blocks G_i of G. In particular, when cof D(G), the sum of the cofactors of D(G), does not vanish, we have the very attractive formula .     

A constructive approximation theorem for the oblique derivative problem in potential theory

The (exterior) oblique derivative problem of potential theory is considered where l is a C^(1,λ)-vector field on a regular boundary ?G_e in Euclidean space R ³ and the direction l at any point of ?G_e forms with the outside normal n an angle ? (l, n) satisfying cos ? (l, n) ≥ c > 0. An approximation of the uniquely determined solution is given by use of trial functions {Φ_n}_n=0,1,… harmonic in some region containing G _e and suitable for numerical purpose (for instance: solid spherical harmonics, certain sequences of fundamental solutions). The system {l▽Φ_n+hΦ_n}_n=0,1,… defined on ?G_e is shown to be closed and complete in the pre-Hilbert space C^(0,λ)(?G_e) of λ-Hölder continuous functions.     

The eigenvalues and eigenfunctions of a spherically symmetric anharmonic oscillator

We show that the operator H_s has a complete set of eigenfunctions and eigenvalues , which satisfy [2l(l + 1) - (3n² + 3n + 1)]s + o(s) and lim_s→0 = 0. The functions are given in spherical coordinates as a product of generalized Laguerre functions and spherical harmonics.     

On a neutral Lotka–Volterra system

Sufficient conditions are obtained for the linear stability of the positive equilibrium of the neutral system in terms of the parameters of the system. The case n=2 is considered in detail and the general case is discussed briefly.     

On the riemann problem for a prototype of a mixed type conservation law

We study the system of conservation laws given by With initial value The system is elliptic when u² + v² < ρ² and hyperbolic when u² + v² ≧ ρ². Following Liu's construction it is found that the system always has a weak solution which however is not necessarily unique.     

Half-Linear Eigenvalue Problems

We consider the eigenvalue problem for t ? [0, b], where aⁿ = |a|ⁿ sgna, a ? ?, λ ? ?, the constants μ, v are real such that 0 ≤ μ < n and derive asymptotic estimates for solutions of the differential equation in the definite case q(t)> 0 which corresponds to the well-known WKB-approximation in the linear case n = 1, μ = 0. In the second part we investigate the asymptotic distribution of the eigenvalues in the general case of two -point boundary conditions and refine these results for the so called separated boundary conditions.     

On 3-colorings of bipartite p-threshold graphs

In this paper some extremal properties of 3-colorings of bipartite complete graphs in the class of all bipartite p-threshold graphs that are uniquely 2-colorable are proved. As a consequence it is shown that the complete bipartite graphs K_{p, p + r} where p ? 2 and 0 ? r < are chromatically unique. A useful result concerning the maximization of a sum of powers of two under certain restrictions, which has an arithmetical interest, is also presented.     

Hamiltonian cycles in 2-connected claw-free-graphs

M. Matthews and D. Sumner have proved that of G is a 2-connected claw-free graph of order n such that δ ≧ (n ? 2)/3, then G is hamiltonian. We prove that the bound for the minimum degree δ can be reduced to n/4 under the additional condition that G is not in F, where F is the set of all graphs defined as follows: any graph H in F can be decomposed into three vertex disjoint subgraphs H₁, H₂, H₃ such that , where u_i, v_i ? V(H_i), u_j v_j ? V(H_j) 1 ? i ≦ j ≦ 3. Examples are given to show that the bound n/4 is sharp. © 1995 John Wiley & Sons, Inc.     

On the residue of a graph

The residue R of a simple graph G of degree sequence S: d₁ ? d₂ ? …? ? d_n is the number of zeros obtained by the iterative process consisting of deleting the first term d₁ of S, subtracting 1 from the d₁ following ones, and sorting down the new sequence. The depth is the number n - R of steps in this algorithm. We prove here some conjectures given by the computer program GRAFFITI, in particular, .     

Spectral Decomposition of Symmetric Operator Matrices

The authors study symmetric operator matrices in the product of Hilbert spaces H = H₁×H₂, where the entries are not necessarily bounded operators. Under suitable assumptions the closure L_o exists and is a selfadjoint operator in H. With L_o, the closure of the transfer function is considered. Under the assumption that there exists a real number β < inf p(A) such that M(β)<< 0, it follows that β ε p(L_o). Applying a factorization result of A.I. Virozub and V.I. Matsaev [VM] to the holomorphic operator function M(λ, the_spectral subspaces of L_o corresponding to the intervals ] — ∞, β] and [β, ∞[ and the restrictions of L_o to these subspaces are characterized. Similar results are proved for operator matrices which are symmetric in a Krein space.     

Existence for a characteristic boundary value problem for an equation of mixed type in three-dimensional space

The equation of mixed type With k(x₃) = sign x₃|x₃|^m, m > 0, d?C¹(?), x = (x₁, x₂, x₃), is considered in the threedimensional region G which is bounded by the surfaces: a piecewise smooth surface Γ₀ lying in the half-space x₃ > 0 which intersects the plane x₃ = 0 in the unit circle, and for x₃ < 0 by the characteristic surfaces We prove existence of a generalized solution for the characteristic boundary value problem: Lu = fin G, u_Γ0∪Γ1 = 0. The result is obtained by using a variant of the energy-integral method.