A bound on the <Emphasis Type="Italic">k</Emphasis>-domination number of a graph

Let G be a graph with vertex set V(G), and let k ⩾ 1 be an integer. A subset D ⊆ V(G) is called a k-dominating set if every vertex υ ∈ V(G)-D has at least k neighbors in D. The k-domination number γ _k (G) of G is the minimum cardinality of a k-dominating set in G. If G is a graph with minimum degree δ(G) ⩾ k + 1, then we prove that

Disproof of a Conjecture on the Subdivision Domination Number of a Graph

A set S of vertices of a graph G = (V,E) is a dominating set if every vertex of is adjacent to some vertex in S. The domination number γ(G) is the minimum cardinality of a dominating set of G. The domination subdivision number sd_γ(G) is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the domination number. Haynes et al. (Discussiones Mathematicae Graph Theory 21 (2001) 239-253) conjectured that for any graph G with . In this note we first give a counterexample to this conjecture in general and then we prove it for a particular class of graphs.     

A New Bound on the Total Domination Subdivision Number

A set S of vertices of a graph G = (V, E) without isolated vertex is a total dominating set if every vertex of V(G) is adjacent to some vertex in S. The total domination number γ _t (G) is the minimum cardinality of a total dominating set of G. The total domination subdivision number is the minimum number of edges that must be subdivided (each edge in G can be subdivided at most once) in order to increase the total domination number. In this paper we prove that for every simple connected graph G of order n ≥ 3,

Paired Domination Vertex Critical Graphs

Let γ _pr (G) denote the paired domination number of graph G. A graph G with no isolated vertex is paired domination vertex critical if for any vertex v of G that is not adjacent to a vertex of degree one, γ _pr (G – v) < γ _pr (G). We call these graphs γ _pr -critical. In this paper, we present a method of constructing γ _pr -critical graphs from smaller ones. Moreover, we show that the diameter of a γ _pr -critical graph is at most and the upper bound is sharp, which answers a question proposed by Henning and Mynhardt [The diameter of paired-domination vertex critical graphs, Czechoslovak Math. J., to appear]. Xinmin Hou: Research supported by NNSF of China (No.10701068 and No.10671191).     

Total Domination in Partitioned Graphs

We present results on total domination in a partitioned graph G = (V, E). Let γ _t (G) denote the total dominating number of G. For a partition , k ≥ 2, of V, let γ _t (G; V _i ) be the cardinality of a smallest subset of V such that every vertex of V _i has a neighbour in it and define the following

A necessary and sufficient condition for singular nonlinear second-order boundary value problems to have positive solutions

In this paper the following result is obtained: Suppose f(g,u,v) is nonnegative, continuous in (a, 6) ×R⁺ ×R ⁺ ; f may be singular at κ = a(and/or κ = b) and υ = 0; f is nondecreasing on u for each κ,υ,nonincreasing on υ for each κ,u; there exists a constant q ε (0,1) such that

The Extremal Function For Noncomplete Minors

  We investigate the maximum number of edges that a graph G can have if it does not contain a given graph H as a minor (subcontraction). Let

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.     

Inequalities involving independence domination, f-domination, connected and total f-domination numbers

Let f be an integer-valued function defined on the vertex set V(G) of a graph G. A subset D of V(G) is an f-dominating set if each vertex x outside D is adjacent to at least f(x) vertices in D. The minimum number of vertices in an f-dominating set is defined to be the f-domination number, denoted by _f (G). In a similar way one can define the connected and total f-domination numbers _c,f (G) and _t,f (G). If f(x) = 1 for all vertices x, then these are the ordinary domination number, connected domination number and total domination number of G, respectively. In this paper we prove some inequalities involving _f (G), _c,f (G), _t,f (G) and the independence domination number i(G). In particular, several known results are generalized.     

Trees with Equal Domination and Restrained Domination Numbers

Let G = (V,E) be a graph and let S V. The set S is a packing in G if the vertices of S are pairwise at distance at least three apart in G. The set S is a dominating set (DS) if every vertex in V − S is adjacent to a vertex in S. Further, if every vertex in V − S is also adjacent to a vertex in V − S, then S is a restrained dominating set (RDS). The domination number of G, denoted by γ(G), is the minimum cardinality of a DS of G, while the restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of a RDS of G. The graph G is γ-excellent if every vertex of G belongs to some minimum DS of G. A constructive characterization of trees with equal domination and restrained domination numbers is presented. As a consequence of this characterization we show that the following statements are equivalent: (i) T is a tree with γ(T)=γ_r(T); (ii) T is a γ-excellent tree and T ≠ K₂; and (iii) T is a tree that has a unique maximum packing and this set is a dominating set of T. We show that if T is a tree of order n with ℓ leaves, then γ_r(T) ≤ (n + ℓ + 1)/2, and we characterize those trees achieving equality.     

Upper Embeddability,Girth and the Degree-Sum of Nonadjacent Vertices

Let G be a 2-edge-connected simple graph with girth g, independence number α(G), and if one of the following two conditions holds

Remarks on Spectral Radius and Laplacian Eigenvalues of a Graph

Let G be a graph with n vertices, m edges and a vertex degree sequence (d ₁, d ₂,..., d _n ), where d ₁ ≥ d ₂ ≥ ... ≥ d _n . The spectral radius and the largest Laplacian eigenvalue are denoted by ϱ(G) and μ(G), respectively. We determine the graphs with

Extremum problems for Golubev sums

Suppose thatG is a finitely connected domain with rectifiable boundary γ, ∞εG, the domainsD ₁,...,D _s are the complements ofG, the subsetsF _j ⊂D _j are infinite and compact,n _j ≥1,j=1,...,s, are integers, λ₀ is a complex-valued measure on γ, and

The Fractional Chromatic Number Of The Categorical Product Of Graphs

We prove that the identity

A characteristic property of spherical caps

It is proved that given H ≥ 0 and an embedded compact orientable constant mean curvature H surface M included in the half space z ≥ 0, not everywhere tangent to z = 0 along its boundary , the inequality

Hamiltonian cycles and 2-dominating induced cycles in claw-free graphs

Let G = (V, E) be a connected graph. For a vertex subset , G[S] is the subgraph of G induced by S. A cycle C (a path, respectively) is said to be an induced cycle (path, respectively) if G[V(C)] = C (G[V(P)] = P, respectively). The distance between a vertex x and a subgraph H of G is denoted by , where d(x, y) is the distance between x and y. A subgraph H of G is called 2-dominating if d(x, H) ≤ 2 for all . An induced path P of G is said to be maximal if there is no induced path P′ satisfying and . In this paper, we assume that G is a connected claw-free graph satisfying the following condition: for every maximal induced path P of length p ≥ 2 with end vertices u, v it holds:

A note on the Hoffman-Wielandt theorem for generalized eigenvalue problems

Let {A, B} and {C, D} be diagonalizable pairs of order n, i.e., there exist invertible matrices P, Q and X, Ysuchthat A = P∧Q, B = PΩQ, C =XГY, D= X△Y, where
∧ = diag（α1, α2, …, αn）, Ω= diag（βl, β2, …βn）,
Г=diag（γ1,γ2,…,γn）, △=diag（δl,δ2,…,δn）.
Let ρ（（α,β）, （γ,δ））=｜αδ-βγ｜/√｜α｜^2＋｜β｜^2√｜γ｜^2＋｜δ｜^2.In this paper, it will be proved that there is a permutation τ of {1,2,... ,n} such that
n∑i=1[ρ（（αi,βi）,（γτ（i）,δτ（i）））]^2≤n[1-1/κ^2（Y）κ^2（Q）（1-d2F（Z,W）/n）],
where κ（Y） = ｜｜Y｜｜2｜｜Y^-1｜｜2,Z= （A,B）,W= （C, D） and dF（Z,W） = 1/√2｜｜Pz＊ -Pw＊｜｜F.     

An extension of almost sure central limit theorem for order statistics

Let {X _n ,n ≥ 1} be a sequence of i.i.d. random variables. Let M _n and m _n denote the first and the second largest maxima. Assume that there are normalizing sequences a _n  > 0, b _n and a nondegenerate limit distribution G, such that . Assume also that {d _k ,k ≥ 1} are positive weights obeying some mild conditions. Then for x > y we have

Total Restrained Domination in Cubic Graphs

A set S of vertices in a graph G = (V, E) is a total restrained dominating set (TRDS) of G if every vertex of G is adjacent to a vertex in S and every vertex of V − S is adjacent to a vertex in V − S. The total restrained domination number of G, denoted by γ _tr (G), is the minimum cardinality of a TRDS of G. Let G be a cubic graph of order n. In this paper we establish an upper bound on γ _tr (G). If adding the restriction that G is claw-free, then we show that γ _tr (G) = γ _t (G) where γ _t (G) is the total domination number of G, and thus some results on total domination in claw-free cubic graphs are valid for total restrained domination. Research was partially supported by the NNSF of China (Nos. 60773078, 10832006), the ShuGuang Plan of Shanghai Education Development Foundation (No. 06SG42) and Shanghai Leading Academic Discipline Project (No. S30104).     

Existence of limits of maximal means

For the class II(ℝ ^m ) of continuous almost periodic functionsf: ℝ ^m → ℝ, we consider the problem of the existence of the limit