Remarks on restrained domination and total restrained domination in graphs

The restrained domination number ^r(G) and the total restrained domination number _t ^r (G) of a graph G were introduced recently by various authors as certain variants of the domination number (G) of (G). A well-known numerical invariant of a graph is the domatic number d(G) which is in a certain way related (and may be called dual) to (G). The paper tries to define analogous concepts also for the restrained domination and the total restrained domination and discusses the sense of such new definitions.This research was supported by Grant MSM 245100303 of the Ministry of Education, Youth and Sports of the Czech Republic.     

On Domination Number of 4-Regular Graphs

Let G be a simple graph. A subset S V is a dominating set of G, if for any vertex v V – S there exists a vertex u S such that uv E(G). The domination number, denoted by (G), is the minimum cardinality of a dominating set. In this paper we prove that if G is a 4-regular graph with order n, then (G) ⁴/₁₁ n     

On the isotopy of Legendrian knots

Let ₀ and ₁ be Legendrian knots which are isotopic as usual knots, and which have the same obvious invariants rot and link. It seems to be an open question whether ₀ and ₁ are isotopic as Legendrian knots. In the paper we give a positive answer to this question for the (rather restricted) class of Legendrian knots with nonintersecting fronts.     

A note on the independent domination number of subset graph

The independent domination number i(G) (independent number (G)) is the minimum (maximum) cardinality among all maximal independent sets of G. Haviland (1995) conjectured that any connected regular graph G of order n and degree 1/2n satisfies i(G) 2n/3 1/2. For 1 k l m, the subset graph S _m (k, l) is the bipartite graph whose vertices are the k- and l-subsets of an m element ground set where two vertices are adjacent if and only if one subset is contained in the other. In this paper, we give a sharp upper bound for i(S _m (k, l)) and prove that if k + l = m then Havilands conjecture holds for the subset graph S _m (k, l). Furthermore, we give the exact value of (S _m (k, l)).This work was supported by National Natural Sciences Foundation of China (19871036).     

The Domination Parameters of Cubic Graphs

Let ir(G), (G), i(G), ₀(G), (G) and IR(G) be the irredundance number, the domination number, the independent domination number, the independence number, the upper domination number and the upper irredundance number of a graph G, respectively. In this paper we show that for any nonnegative integers k₁, k₂, k₃, k₄, k₅ there exists a cubic graph G satisfying the following conditions: (G) – ir(G) k₁, i(G) – (G) k₂, ₀(G) – i(G) > k₃, (G) – ₀(G) – k₄, and IR(G) – (G) – k₅. This result settles a problem posed in [9].Supported by the INTAS and the Belarus Government (Project INTAS-BELARUS 97-0093).Supported by RUTCOR.     

A priori estimates of the solution of the dirichlet problem for the Monge-ampére equation in weight spaces

One proves that a priori boundedness of the norm of the solution of the problem det(U_xx)=f(x,u,u_x)>>0,u¦=0. The magnitudes of the exponents,() depends on whether the arguments u p occur or not in f (x,u,p).Translated from Zapiski Nauchnykh Seminarov Leningradskogo Otdeleniya Matematicheskogo Instituta im. V. A. Steklova AN SSSR, Vol. 125, pp. 74–90, 1983.     

L p Spectral Independence of Elliptic Operators via Commutator Estimates

Let {T _p:q ₁ p q ₂} be a family of consistent C ₀ semigroups on L ^p(), with q ₁,q ₂ [1,) and open. We show that certain commutator conditions on T _p and on the resolvent of its generator A _p ensure the p independence of the spectrum of A _p for p [q ₁,q ₂.Applications include the case of Petrovskij correct systems with Hölder continuous coefficients, Schrödinger operators, and certain elliptic operators in divergence form with real, but not necessarily symmetric, or complex coefficients.     

Signed Total Domination Nnumber of a Graph

The signed total domination number of a graph is a certain variant of the domination number. If is a vertex of a graph G, then N() is its oper neighbourhood, i.e. the set of all vertices adjacent to in G. A mapping f: V(G)-1, 1, where V(G) is the vertex set of G, is called a signed total dominating function (STDF) on G, if for each V(G). The minimum of values , taken over all STDF's of G, is called the signed total domination number of G and denoted by _st(G). A theorem stating lower bounds for _st(G) is stated for the case of regular graphs. The values of this number are found for complete graphs, circuits, complete bipartite graphs and graphs on n-side prisms. At the end it is proved that _st(G) is not bounded from below in general.     

Turán's extremal problem in random graphs: Forbidding odd cycles

For 0<1 and graphsG andH, we writeGH if any -proportion of the edges ofG span at least one copy ofH inG. As customary, we writeC ^k for a cycle of lengthk. We show that, for every fixed integerl1 and real >0, there exists a real constantC=C(l, ), such that almost every random graphG _{n, p} withp=p(n)Cn ^–1+1/2l satisfiesG _n,p1/2+ C ^2l+1. In particular, for any fixedl1 and >0, this result implies the existence of very sparse graphsG withG _1/2+ C ^2l+1.The first author was partially supported by NSERC. The second author was partially supported by FAPESP (Proc. 93/0603-1) and by CNP_q (Proc. 300334/93-1). The third author was partially sopported by KBN grant 2 1087 91 01.     

Theorem on a convergence condition in the spaces

For a given -function (u), a condition on a -function (u) is found such that it is necessary and sufficient for the following to hold: if f_n(x) f(x) and f _n (x)M (n=1, 2, ...) where M>0 is an absolute constant, then f _n (x)–f(x)0(n). An analogous condition for convergence in Orlicz spaces is obtained as a corollary.Translated from Matematicheskie Zametki, Vol. 21, No. 5, pp. 615–626, May, 1977.The author thanks V. A. Skvortsov for his constant attention and guidance on this paper.     

Torsion and closed geodesics on complex hyperbolic manifolds

Summary LetX be a compact complex manifold covered by complex hyperbolicn-space with the induced metric. Each stable horocycle has a cocomplex structure preserved by the geodesic flow. To a closed geodesic one can thus associate a piece of the Poincaré map with a holomorphic fixed point. The resulting Atiyah-Bott fixed point indices, together with the length and multiplicity of as a periodic orbit, determine the contribution of to certain zeta functionsR _p(z), 0pn. From the leading coefficient ofR _p atZ=0 and the Hodge numbersh ^ij (X) we calculate the Ray-Singer -torsionT _p (X). This indicates that the known connections between torsion and the dynamical features of closed orbits continue to hold in the holomorphic category.Corresponding results hold for the -torsion of a flat unitary bundle, extending certain formulas of Ray and Singer to the casen>1.Partially supported by the Sloan Foundation and the National Science Foundation     

Maximum Monoreflections and Essential Extensions

An extension operator c in a category is an assignment, to each object A a monomorphism c _A : AcA. Seeking to approximate such a c by a functor, in our earlier paper Maximum monoreflections, we showed that with some hypotheses on the category, and on c, there is a monoreflection (c) maximum beneath c. Thus, in a suitable category of rings, using the complete ring of quotients operator Q, each object A has a maximum functorial ring of quotients (Q)A. But the proof gave no hint of how to calculate the general (c)A's, nor the particular (Q)A's. In the present paper, we give an explicit formula (and separate proof of existence) for the (c)A's, under more complicated hypotheses on the category and assuming the c _A 's are essential monomorphisms. We discuss briefly how the formula proves adequate to calculate the (Q)A's in Archimedean f-rings, and some related and necessary constructs in Archimedean l-groups.     

Über Tuttes Cages

An undirected graph of valencyd and girth is called a (d, )-cage if its automorphism group acts transitively on the set of alls-paths in ands(+1)/2. We discuss an elementary construction of two known families of cages which allows us to prove easily some facts about their automorphism groups. We give, for example, a new proof of the fact that the automorphism group ofSp ₄(2 ⁿ ) contains elements which are not induced by Sp ₄(2 ⁿ ).     

Interpolation theorems for a family of spanning subgraphs

Let G be a graph with order p, size q and component number . For each i between p – and q, let be the family of spanning i-edge subgraphs of G with exactly components. For an integer-valued graphical invariant if H H is an adjacent edge transformation (AET) implies |(H)-(H^')|1 then is said to be continuous with respect to AET. Similarly define the continuity of with respect to simple edge transformation (SET). Let M _j() and m _j() be the invariants defined by . It is proved that both M _p–() and m _p–(;) interpolate over , if is continuous with respect to AET, and that M _j() and m _j() interpolate over , if is continuous with respect to SET. In this way a lot of known interpolation results, including a theorem due to Schuster etc., are generalized.     

Non removable edges in 3-connected cubic graphs

LetG be a cyclicallyk-edge-connected cubic graph withk 3. Lete be an edge ofG. LetG be the cubic graph obtained fromG by deletinge and its end vertices. The edgee is said to bek-removable ifG is also cyclicallyk-edge-connected. Let us denote by S _k (G) the graph induced by thek-removable edges and by N _k (G) the graph induced by the non 3-removable edges ofG. In a previous paper [7], we have proved that N ₃(G) is empty if and only ifG is cyclically 4-edge connected and that if N ₃(G) is not empty then it is a forest containing at least three trees. Andersen, Fleischner and Jackson [1] and, independently, McCuaig [11] studied N ₄(G). Here, we study the structure of N _k (G) fork 5 and we give some constructions of graphs such thatN _k (G) = E(G). We note that the main result of this paper (Theorem 5) has been announced independently by McCuaig [11].

---

Résumé SoitG un graphe cubique cyliquementk-arête-connexe, aveck 3. Soite une arête deG et soitG le graphe cubique obtenu à partir deG en supprimante et ses extrémités. L'arêtee est ditek-suppressible siG est aussi cycliquementk-arête-connexe. Désignons par S _k (G) le graphe induit par les arêtesk-suppressibles et par N _k (G) celui induit par les arêtes nonk-suppressibles. Dans un précédent article [7], nous avons montré que N ₃(G) est vide si et seulement siG est cycliquement 4-arête-connexe et que si N ₃(G) n'est pas vide alors c'est une forêt possédant au moins trois arbres. Andersen, Fleischner and Jackson [1] et, indépendemment, McCuaig [11] ont étudié N ₄(G). Ici, nous étudions la structure de N _k (G) pourk 5 et nous donnons des constructions de graphes pour lesquelsN _k (G) = E(G). Nous signalons que le résultat principal de cet article (Théorème 5) a été annoncé indépendamment par McCuaig [11].

     

Sur certaines algèbres associées à une mesure de Guelfand

Let be a Guelfand measure (cf. [A, B]) on a locally compact groupG DenoteL ₁ (G)=*L ₁(G)* the commutative Banach algebra associated to . We show thatL ₁ (G) is semi-simple and give a characterization of the closed ideals ofL ₁ (G). Using the -spherical Fourier transform, we characterize all linear bounded operators inL ₁ (G) which are invariants by -translations (i.e. such that ¹(( _x f) )=( _x ((f)) for eachxG andfL ₁ (G); where _x f(y)=f(xy); x,y G). WhenG is compact, we study the algebraL ₁ (G) and obtain results analogous to ones obtained for the commutative case: we show thatL ₁ (G) is regular, all closed sets of its Guelfand spectrum are sets of synthesis and establish theorems of harmonic synthesis for functions inL _p (G) (p=1,2 or +).

     

Smoothness of solutions of a nonlinear ode

Smoothness of aC -functionf is measured by (Carleman) sequence {M _k} ₀ ; we sayfC _M [0, 1] if|f ^(k) (t)|CR ^k M _k,k=0, 1, ... withC, R>0. A typical statement proven in this paper isTHEOREM: Let u, b be two C -functions on [0, 1]such that (a) u=u ²+b, (b) |b ^(k) (t)|CR ^k (k!) , >1,k_–.Then |u^(k)(t)|C₁R^k((k–1)!),k_–.The first author acknowledges the hospitality of Mathematical Research Institute of the Ohio State University during his one month visit there in the spring of 1999     

Semiregular Large Sets

We develop the notion of t-homogeneous, G-semiregular large sets of t-designs, show that there are infinitely many 3-homogeneous PSL(2, q)-semiregular large sets when q 3 mod 4, two sporadic 3-homogeneous AL(1,32)-semiregular large sets, and no other interesting t-homogeneous G-semiregular large sets for t 3.     

A Variation of an Extremal Theorem Due to Woodall

We consider a variation of an extremal theorem due to Woodall [12, or 1, Chapter 3] as follows: Determine the smallest even integer (₃C₁,n), such that every n-term graphic sequence = (d₁, d₂,..., d_n) with term sum () = d₁ + d₂ + ... + d_n (₃C₁,n) has a realization G containing a cycle of length r for each r = 3,4,...,l. In this paper, the values of (₃C_l,n) are determined for l = 2m – 1,n 3m – 4 and for l = 2m,n 5m – 7, where m 4.AMS Mathematics subject classification (1991) 05C35Project supported by the National Natural Science Foundation of China (Grant No. 19971086) and the Doctoral Program Foundation of National Education Department of China     

Infinitesimal,first order bendings of smooth,convex surfaces of revolution subject to conic,sleeve-like constraints along the boundary

We prove that on a closed, smooth, convex surface of revolution , whose poles are not flattening points, there exists only a countable set of parallels _n. Each of these parallels cuts surface into two parts so that one of the parts, , admits nontrivial, infinitesimal bendings in the process of which all the points of its boundary _n are displaced on a preassigned, conic sleeve K that is coaxial with the surface. The sequence of such parallels _n converges to parallel ^*, which has the following properties: 1) the tangent cone to surface along ^* is orthogonal to sleeve K; 2) surface , cut off from surface by parallel ^*, has rigidity of first order in the indicated class of bendings.Translated from Ukrainskii Geometricheskii Sbornik, No. 33, pp. 3–8, 1990.