Balancing signed graphs

A signed graph based on F is an ordinary graph F with each edge marked as positive or negative. Such a graph is called balanced if each of its cycles includes an even number of negative edges. Psychologists are sometimes interested in the smallest number d=d(G) such that a signed graph G may be converted into a balanced graph by changing the signs of d edges. We investigate the number D(F) defined as the largest d(G) such that G is a signed graph based on F. We prove that $\text{1}\text{2}\text{m?}\text{nm}\text{≤D(F)≤}\text{1}\text{2}\text{m}$ for every graph F with n vertices and m edges. If F is the complete bipartite graph with t vertices in each part, then $\text{D(F)≤}\text{1}\text{2}\text{t}{}^2\text{?ct}{}^{\mathrm{<mtext>3</mtext><mtext>2</mtext>}}$ for some positive constant c.     

Diameter vulnerability of graphs by edge deletion

Let f(t,k) be the maximum diameter of graphs obtained by deleting t edges from a (t+1)-edge-connected graph with diameter k. This paper shows for t≥4, which corrects an improper result in [C. Peyrat, Diameter vulnerability of graphs, Discrete Appl. Math. 9 (3) (1984) 245-250] and also determines f(2,k)=3k−1 and f(3,k)=4k−2 for k≥3.     

A general approach to optimal control of a regression experiment

Let $\text{θ}\text{θ}\text{?}$ = ($\text{θ}\text{θ}\text{?}$₁, $\text{θ}\text{θ}\text{?}$₂, …, $\text{θ}\text{θ}\text{?}$_n)′ be the least-squares estimator of θ = (θ₁, θ₂, …, θ_n)′ by the realization of the process y(t) = Σ_{k = 1}ⁿθ_kf_k(t) + ξ(t) on the interval T = [a, b] with f = (f₁, f₂, …, f_n)′ belonging to a certain set X. The process satisfies E(ξ(t))≡0 and has known continuous covariance r(s, t) = E(ξ(s)ξ(t)) on T × T. In this paper, A-, D-, and D_s-optimality are used as criteria for choosing f in X. A-, D-, and D_s-optimal models can be constructed explicitly by means of r.     

On cycles in regular 3-partite tournaments

The vertex set of a digraph D is denoted by V(D). A c-partite tournament is an orientation of a complete c-partite graph. In 1991, Jian-zhong Wang conjectured that every arc of a regular 3-partite tournament D is contained in directed cycles of all lengths 3,6,9,…,|V(D)|. This conjecture is not valid, because for each integer t with 3?t?|V(D)|, there exists an infinite family of regular 3-partite tournaments D such that at least one arc of D is not contained in a directed cycle of length t.In this paper, we prove that every arc of a regular 3-partite tournament with at least nine vertices is contained in a directed cycle of length m, m+1, or m+2 for 3?m?5, and we conjecture that every arc of a regular 3-partite tournament is contained in a directed cycle of length m, (m+1), or (m+2) for each m∈{3,4,…,|V(D)|-2}.It is known that every regular 3-partite tournament D with at least six vertices contains directed cycles of lengths 3, |V(D)|-3, and |V(D)|. We show that every regular 3-partite tournament D with at least six vertices also has a directed cycle of length 6, and we conjecture that each such 3-partite tournament contains cycles of all lengths 3,6,9,…,|V(D)|.     

Comparability graphs and intersection graphs

A function diagram (f-diagram) D consists of the family of curves {$\text{1}\text{?}$ñ} obtained from n continuous functions $\text{f}{}_{\mathrm{i}}\text{:[0,1]→}\text{R}\text{(1?i?n)}$. We call the intersection graph of D a function graph (f-graph). It is shown that a graph G is an f-graph if and only if its complement ? is a comparability graph. An f-diagram generalizes the notion of a permulation diagram where the f_i are linear functions. It is also shown that G is the intersection graph of the concatenation of ?k permutation diagrams if and only if the partial order dimension of $\text{G}\text{?}\text{is ?k+1}$. Computational complexity results are obtained for recognizing such graphs.     

On the sum of the total domination numbers of a digraph and its converse

A vertex subset S of a digraph D is called a dominating set of D if every vertex not in S has an in-neighbor in S. A dominating set S of D is called a total dominating set of D if the subdigraph induced by S has no isolated vertices. The total domination number of D, denoted by γt(D), is the minimum cardinality of a total dominating set of D. We show that for any connected digraph D of order n≥3, γt(D)+γt(D^? )≤5n/3, where D? is the converse of D. Furthermore, we characterize the oriented trees for which the equality holds.     

On separating systems of graphs

Given a finite loopless graph G (resp. digraph D), let σ(G), ?(G) and ψ(D) denote the minimal cardinalities of a completely separating system of G, a separating system of G and a separating system of D, respectively. The main results of this paper are:

$\text{δ(G) =}\text{min}\text{m}{}^{\mathrm{m}}{}_{\mathrm{?m/2?}}\text{?γ(G)}\text{and}\text{?(G) = ?}\text{log}{}_2\text{γ(G)?}\text{where}\text{γ(G)}$

denotes the chromatic number of G. (ii) All the problems of determining σ(G), ?(G) and ψ(D) are NP-complete.     

On the ramsey numbers N(3,3,…3;2)

The main results of this paper are N(3,3,3,3;2) > 50 andf(k+1)≥3 f(k)+f(k?2), where $\text{f(k) = N}\text{3,3,…;2)}\text{k}\text{times}\text{?1 for k ≥ 3}$.     

On the number of conjugacy classes in SL(2,Z)

Let $\text{H}\text{(t)}$ be the number of conjugacy classes of elements in SL(2, $\text{L}$) with trace t, and let $\text{h}\text{(n)}$ be the number of equivalence classes of binary quadratic forms with discriminant n. Then for t≠±2, $\text{H}\text{(t)=}\text{h}\text{(t}{}^2\text{?4)}$. For all real θ > 0 there is a T(θ) such that whenever |t|>T(θ), $\text{H}\text{(t)>|t|}{}^{\mathrm{1?\theta }}$. There is a c>0 such that for those t such that t²?4 is squarefree, $\text{H}\text{(t)≤c|t|}$.     

Periodic forcing of solutions of a boundary value problem for a second-order differential equation in Hilbert space

We show that if u is a bounded solution on $\text{R}$⁺ of u″(t) ?Au(t) + f(t), where A is a maximal monotone operator on a real Hilbert space H and f∈L_loc²($\text{R}$⁺;H) is periodic, then there exists a periodic solution ω of the differential equation such that u(t) ? ω(t)   0 and u′(t) ? ω′(t) → 0 as t → ∞. We also show that the two-point boundary value problem for this equation has a unique solution for boundary values in $\text{D(A)}$ and that a smoothing effect takes place.     

Decreasing the diameter of bounded degree graphs

Let f_d (G) denote the minimum number of edges that have to be added to a graph G to transform it into a graph of diameter at most d. We prove that for any graph G with maximum degree D and n > n₀ (D) vertices, f₂(G) = n − D − 1 and f₃(G) ≥ n − O(D³). For d ≥ 4, f_d (G) depends strongly on the actual structure of G, not only on the maximum degree of G. We prove that the maximum of f_d (G) over all connected graphs on n vertices is n/⌊d/2 ⌋ − O(1). As a byproduct, we show that for the n‐cycle C_n, f_d (C_n) = n/(2⌊d/2 ⌋ − 1) − O(1) for every d and n, improving earlier estimates of Chung and Garey in certain ranges. © 2000 John Wiley & Sons, Inc. J Graph Theory 35: 161–172, 2000     

Degrees and cycles in digraphs

In this article, we give conditions on the total degrees of the vertices in a strong digraph implying the existence of a cycle of length at least $\text{?}\text{(n?1)}\text{h}\text{? + 1}$, where n is the number of vertices of the graph and h an integer, 1?h?n?1. The same conditions imply the existence of a path of length $\text{?}\text{(n?1)}\text{h}\text{? + ?}\text{(n?2)}\text{h}\text{?}$. In the case of strong oriented graphs (antisymmetric digraphs) we improve these conditions. In both cases, we show that the given conditions are the best possible.     

Boundary layer methods for certain nonlinear singularly perturbed optimal control problems

We shall examine the control problem consisting of the system $\text{dx}\text{dt}\text{= f}{}_1\text{(x, z, u, t, ?)}$$\text{?(}\text{dz}\text{dt}\text{) = f}{}_2\text{(x, z, u, t, ?)}$ on the interval 0 ? t ? 1 with the initial values x(0, ?) and z(0, ?) prescribed, where the cost functional J(?) = π(x(1, ?), z(1, ?), ?) + ∝₀¹V(x(t, ?), z(t, ?), u(t, ?), t, ?) dt is to be minimized. We shall restrict attention to the special problem where the f_i's are linear in z and u, V is quadratic in z and independent of z when ? = 0, π and V are positive semidefinite functions of x and z, and V is a positive definite function of u. Under appropriate conditions, we shall obtain an asymptotic solution of the problem valid as the small parameter ? tends to zero. The techniques of constructing such asymptotic expansions will be stressed.     

Potential theory associated with Uhlenbeck-Ornstein process

Some parallel results of Gross' paper (Potential theory on Hilbert space, J. Functional Analysis1 (1967), 123–181) are obtained for Uhlenbeck-Ornstein process U(t) in an abstract Wiener space (H, B, i). Generalized number operator $\text{N}$ is defined by $\text{N}$f(x) = ?lim_∈←0{E[f($\text{U}$(τ^∈_ξ))] ? f(x)}/E[τ^∈_ξ, where τ_x^? is the first exit time of U(t) starting at x from the ball of radius ? with center x. It is shown that $\text{N}$f(x) = ?trace D²f(x)+〈Df(x),x〉 for a large class of functions f. Let r_t(x, dy) be the transition probabilities of U(t). The λ-potential G_λf, λ > 0, and normalized potential Rf of f are defined by G_λf(X) = ∫₀^∞e^?λtr_tf(x) dt and Rf(x) = ∫₀^∞ [r_tf(x) ? r_tf(0)] dt. It is shown that if f is a bounded Lip-1 function then trace D²G_λf(x) ? 〈DG_λf(x), x〉 = ?f(x) + λG_λf(x) and trace D²Rf(x) ? 〈DRf(x), x〉 = ?f(x) + ∫_Bf(y)p₁(dy), where p₁ is the Wiener measure in B with parameter 1. Some approximation theorems are also proved.     

Decomposition de Km+Kn en cycles hamiltoniens

Let K_m be the complete graph of order m. We prove that the cartesian sum K_m+K_n can be decomposed into $\text{1}\text{2}$(m+n?2) hamiltonian cycles if m+n is even and into $\text{1}\text{2}$(m+n?3) hamiltonian cycles and a perfect matching if m+n is odd.     

Minimally k-connected graphs of low order and maximal size

Let G be a minimally k-connected graph of order n and size e(G).Mader [4] proved that (i) $\text{e(G)?kn?(}\text{k+1}\text{2}\text{)}$; (ii) e(G)?k(n?k) if n?3k?2, and the complete bipartite graph K_k,n?k is the only minimally k-connected graph of order; n and size k(n?k) when k?2 and n?3k?1.The purpose of the present paper is to determine all minimally k-connected graphs of low order and maximal size. For each n such that k+1?n?3k?2 we prove $\text{e(G)??}\text{(n+k)}{}^2\text{8}\text{?}$ and characterize all minimally k-connected graphs of order n and size $\text{?(}\text{(n+k)}{}^2\text{8}\text{?}$.     

Antipodal graphs of diameter three

Distance-regular graphs of diameter three are of three (almost distinct) kinds: primitive, bipartite, and antipodal. An antipodal graph of diameter three is just an r-fold covering of a complete graph K_k+1 for some r?k. Its intersection array and spectrum are determined by the parameters r, k together with the number c of 2-arcs joining any two vertices at distance two. Most such graphs have girth three. In this note we consider antipodal distance-regular graphs of diameter three and girth ? 4. If r=2, then the only graphs are “K_{k+1, k+1} minus a 1-factor.” We therefore assume r?3. The graphs with c=1 necessarily have r=k and were classified in lsqb3rsqb. We prove the inequality $\text{r?2>c}{}^{\mathrm{<mtext>1</mtext><mtext>2</mtext>}}$ (Theorem 2), list the feasible parameter sets when c=2 or 3 (Corollary 1), and conclude that every 3-fold or 4-fold antipodal covering of a complete graph has girth three (Corollary 2).     

On forced nonlinear oscillations

The existence of a 1-periodic solution of the generalized Liénard equation x″ + g(x)x′ + f(t, x) = e(t), where g(x) is continuous, e(t) is continuous, periodic of period 1 and with mean value 0 and f is continuous, periodic of period 1 in t, is proved under one of the following conditions: (i) there exists M ? 0 such that $\text{f(t, x)x ? 0}\text{for}\text{¦x¦? M}$ and

$\text{lim sup}\text{|x|?+∞}\text{|f(t,x)|}\text{| x |}\text{<}\text{4π}{}^2\text{2π + 1}$

(ii) there exists M ? 0 such that $\text{f(t, x)x ? 0}\text{for}\text{¦x¦? M}$. Earlier results of A. C. Lazer, J. Mawhin and R. Reissig are obtained as particular cases.     

Un lemme de Mañé bilatéralA bilateral version of Mañé's lemma

We prove that, assuming some hyperbolicity on the dynamical system T:X→X and some regularity on $\text{f:X→}\text{R}$, there exists $\text{θ:X→}\text{R}$ in the same regularity class and such that α(f)?f?θ+θ°T?β(f), where α(f), β(f) are the infimum and the supremum of the averages of f along periodic orbits. To cite this article: T. Bousch, C. R. Acad. Sci. Paris, Ser. I 335 (2002) 533–536.     

Non-simply connected copes

Let (W⁴,?W⁴) be a 4-manifold. Let f₁,f₂,…,f_k:(D²,?D²)→ (W⁴,?W⁴) be transverse immersions that have spherical duals $\text{α}{}_1\text{,α}{}_2\text{,…,α}{}_{\mathrm{k}}\text{:S}{}^2\text{→}\text{W}\text{?}$. Then there are open disjoint subsets V₁, V₂,…,V_k of W, such that for each 1?i?k, (a) ?V_i=V₁∩?W and ?V_i is an open regular neighborhood of f_i(?D²) in ?W, and (b) (V_i,?V_i,f_i(?D²)) is proper homotopy equivalent to (M, ?M, d)—a standard object in which d bounds an embedded flat disk. If we could get a homeomorphism instead of a proper homotopy equivalence, then we would be able to prove a 5-dimensional s-cobordism theorem.