Upper domination and upper irredundance perfect graphs

Let β(G), Γ(G) and IR(G) be the independence number, the upper domination number and the upper irredundance number, respectively. A graph G is called Γ-perfect if β(H) = Γ(H), for every induced subgraph H of G. A graph G is called IR-perfect if Γ(H) =IR(H), for every induced subgraph H of G. In this paper, we present a characterization of Γ-perfect graphs in terms of a family of forbidden induced subgraphs, and show that the class of Γ-perfect graphs is a subclass of IR-perfect graphs and that the class of absorbantly perfect graphs is a subclass of Γ-perfect graphs. These results imply a number of known theorems on Γ-perfect graphs and IR-perfect graphs. Moreover, we prove a sufficient condition for a graph to be Γ-perfect and IR-perfect which improves a known analogous result.     

The Terwilliger Algebra Associated with a Set of Vertices in a Distance-Regular Graph

Let Γ be a distance-regular graph of diameter D. Let X denote the vertex set of Γ and let Y be a nonempty subset of X. We define an algebra τ = τ(Y). This algebra is finite dimensional and semisimple. If Y consists of a single vertex then τ is the corresponding subconstituent algebra defined by P. Terwilliger. We investigate the irreducible τ-modules. We define endpoints and thin condition on irreducible τ-modules as a generalization of the case when Y consists of a single vertex. We determine when an irreducible module is thin. When the module is generated by the characteristic vector of Y, it is thin if and only if Y is a completely regular code of Γ. By considering a suitable subset Y, every irreducible τ(x)-module of endpoint i can be regarded as an irreducible τ(Y)-module of endpoint 0.This research was partially supported by the Grant-in-Aid for Scientific Research (No. 12640039), Japan Society of the Promotion of Science. A part of the research was done when the author was visiting the Ohio State University.     

A game-theoretic equivalence to the Hahn-Banach theorem

Let Γ_X() = X, A (X), υ be a cooperative von Neumann game with side payments, where X is a nonempty set of arbitrary cardinality, A(X) the Boolean ring generated from P(X) with the operations Δ and ∩ for addition and multiplication, respectively, such that S² =S for all S ε A (X), and with ;() = 0. The Shapley-Bondareva-Schmeidler Theorem, which states that a game of the form Γ_X() = X, A (X), is weak if and only if the core of Γ_X(),ζ(Γ_X()), is normal, may be regarded as the fundamental theorem for weak cooperative games with side-payments. In this paper we use an ultrapower construction on the reals, , to summarize a common mathematical theme employed in various constructions used to establish the Shapley-Bondareva-Schmeidler Theorem in the literature (Dalbaen, 1974; Kannai, 1969; Schmeidler, 1967, 1972). This common mathematical theme is that the space L, comprised of finite, real linear combinations of the collection of functions, {χ_a : a ε A (X)}, possesses a certain extension property that is intimately related to the Hahn-Banach Theorem of functional analysis. A close inspection of the extension property reveals that the Shapley-Bondareva-Schmeidler Theorem is in fact equivalent to the Hahn-Banach Theorem.     

Multifunctions of faces for conditional expectations of selectors and Jensen's inequality

Let (T, , P) be a probability space, a P-complete sub-δ-algebra of and X a Banach space. Let multifunction t → Γ(t), t T, have a (X)-measurable graph and closed convex subsets of X for values. If x(t) ε Γ(t) P-a.e. and y(·) ε E_p x(·), then y(t) ε Γ(t) P-a.e. Conversely, x(t) ε F(Γ(t), y(t)) P-a.e., where F(Γ(t), y(t)) is the face of point y(t) in Γ(t). If X = , then the same holds true if Γ(t) is Borel and convex, only. These results imply, in particular, extensions of Jensen's inequality for conditional expectations of random convex functions and provide a complete characterization of the cases when the equality holds in the extended Jensen inequality.     

Special Uniform Approximations of Continuous Vector-Valued Functions. Part I: Special Approximations in CX(T)

In this paper, we give special uniform approximations of functions u from the spaces C_X(T) and C_∞(T,X), with elements of the tensor products C_Γ(T)X, respectively C₀(T,Γ)X, for a topological space T and a Γ-locally convex space X. We call an approximation special, if satisfies additional constraints, namely supp vu⁻¹(X\{0}) and (T) co(u(T)) (resp. co(u(T){0})). In Section 3, we give three distinct applications, which are due exactly to these constraints: a density result with respect to the inductive limit topology, a Tietze–Dugundji's type extension new theorem and a proof of Schauder–Tihonov's fixed point theorem.     

Dominating Sets of Some Graphs Associated to Commutative Rings

Let G = (V, E) be a graph. A set S ? V is a dominating set of G if every vertex in V is either in S or is adjacent to a vertex in S. The domination number γ(G) of G is the minimum cardinality among the dominating sets of G. The main object of this article is to study and characterize the dominating sets of the zero-divisor graph Γ(R) and ideal-based zero-divisor graph Γ _I (R) of a commutative ring R.     

Total outer-connected domination numbers of trees

Let G=(V,E) be a graph without an isolated vertex. A set DV(G) is a total dominating set if D is dominating, and the induced subgraph G[D] does not contain an isolated vertex. The total domination number of G is the minimum cardinality of a total dominating set of G. A set DV(G) is a total outer-connected dominating set if D is total dominating, and the induced subgraph G[V(G)−D] is a connected graph. The total outer-connected domination number of G is the minimum cardinality of a total outer-connected dominating set of G. We characterize trees with equal total domination and total outer-connected domination numbers. We give a lower bound for the total outer-connected domination number of trees and we characterize the extremal trees.     

Canonical forms of Borel-measurable mappings Δ: [ω] →

We show that for every Borel-measurable mapping Δ: [ω]^ω → there exists A [ω]^ω and there exists a continuous mapping Γ: [A]^ω → [A]^ω with Γ(X) X such that for all X, Y [A]^ω it follows that Δ(X) = Δ(Y) if Γ(X) = Γ(Y). In a sense, this is generalization of the Erdös-Rado canonization theorem     

Total domination in graphs with minimum degree three

A set S of vertices of a graph G is a total dominating set, if every vertex of V(G) is adjacent to some vertex in S. The total domination number of G, denoted by γ_t(G), is the minimum cardinality of a total dominating set of G. We prove that, if G is a graph of order n with minimum degree at least 3, then γ_t(G) ≤ 7n/13. © 2000 John Wiley & Sons, Inc. J Graph Theory 34:9–19, 2000     

On minimum secure dominating sets of graphs

A subset X of the vertex set of a graph G is a secure dominating set of G if X is a dominating set of G and if, for each vertex u not in X, there is a neighbouring vertex v of u in X such that the swap set (X/{v}) ? {u} is again a dominating set of G, in which case v is called a defender. The secure domination number of G is the cardinality of a smallest secure dominating set of G. In this paper, we show that every graph of minimum degree at least 2 possesses a minimum secure dominating set in which all vertices are defenders. We also characterise the classes of graphs that have secure domination numbers 1, 2 and 3.     

Twice Q-polynomial distance-regular graphs are thin

Let Γ be a distance-regular graph of diameter d 3. For each vertex χ of Γ, let T(χ) denote the subconstituent algebra for Γ with respect to χ. An irreducible T(χ)-module W is said to be thin if dim E_i^*(χ) W 1 for 0 i d, where E_i^*(χ) is the projection onto the ith subconstituent for Γ with respect to χ. The graph Γ is said to be thin if, for each vertex χ of Γ, very irreducible T(χ)-module is thin. Our main result is the following Theorem: If Γ has two Q-polynomial structures, then Γ is thin.     

An upper bound for domination number of 5-regular graphs

Let G = (V, E) be a simple graph. A subset S ⊆ V is a dominating set of G, if for any vertex u ∈ V-S, there exists a vertex v ∈ S such that uv ∈ E. The domination number, denoted by γ(G), is the minimum cardinality of a dominating set. In this paper we will prove that if G is a 5-regular graph, then γ(G) ⩽ 5/14n.     

Topological properties of the multifunction space <Emphasis Type="Italic">L</Emphasis>(<Emphasis Type="Italic">X</Emphasis>) of cusco maps

A set-valued mapping F from a topological space X to a topological space Y is called a cusco map if F is upper semicontinuous and F(x) is a nonempty, compact and connected subset of Y for each x ∈ X. We denote by L(X), the space of all subsets F of X × ℝ such that F is the graph of a cusco map from the space X to the real line ℝ. In this paper, we study topological properties of L(X) endowed with the Vietoris topology. The second author is supported by the SPM fellowship awarded by the Council of Scientific and Industrial Research, India.     

On the doubly connected domination number of a graph

For a given connected graph G = (V, E), a set is a doubly connected dominating set if it is dominating and both 〈D〉 and 〈V (G)-D〉 are connected. The cardinality of the minimum doubly connected dominating set in G is the doubly connected domination number. We investigate several properties of doubly connected dominating sets and give some bounds on the doubly connected domination number.     

Sum and intersection of summand ideals in C(X)

Summand sum property (SSP) and summand intersection property (SIP) of modules are studied in [8] and [15] respectively. In this paper we give some topological characterizations of these properties in C(X). It is shown that the ring C(X) has SIPif and only if every intersection of closed-open subsets of Xhas a closed interior. This characterization then shows that for a large class of topological spaces, such as locally connected spaces and extremally disconnected spaces, the ring C(X) has SIP. It is also shown that C(X) has SSPif and only if the space Xhas only finitely many components. Finally, using summand ideals of C(X), we will give several algebraic characterizations of some disconnected spaces.     

A note on the weakly convex and convex domination numbers of a torus

The distanced_G(u,v) between two vertices u and v in a connected graph G is the length of the shortest (u,v) path in G. A (u,v) path of length d_G(u,v) is called a (u,v)-geodesic. A set X⊆V is called weakly convex in G if for every two vertices a,b∈X, exists an (a,b)-geodesic, all of whose vertices belong to X. A set X is convex in G if for all a,b∈X all vertices from every (a,b)-geodesic belong to X. The weakly convex domination number of a graph G is the minimum cardinality of a weakly convex dominating set of G, while the convex domination number of a graph G is the minimum cardinality of a convex dominating set of G. In this paper we consider weakly convex and convex domination numbers of tori.     

Positive circuits and maximal number of fixed points in discrete dynamical systems

We consider a product X of n finite intervals of integers, a map F from X to itself, the asynchronous state transition graph Γ(F) on X that Thomas proposed as a model for the dynamics of a network of n genes, and the interaction graph G(F) that describes the topology of the system in terms of positive and negative interactions between its n components. Then, we establish an upper bound on the number of fixed points for F, and more generally on the number of attractors in Γ(F), which only depends on X and on the topology of the positive circuits of G(F). This result generalizes the following discrete version of Thomas’ conjecture recently proved by Richard and Comet: If G(F) has no positive circuit, then Γ(F) has a unique attractor. This result also generalizes a result on the maximal number of fixed points in Boolean networks obtained by Aracena, Demongeot and Goles. The interest of this work in the context of gene network modeling is briefly discussed.     

Noncommutative Localizations of Lie-Complete Rings

In this paper we investigate the topological localizations of Lie-complete rings. It has been proved that a topological localization of a Lie-complete ring is commutative modulo its topological nilradical. Based on the topological localizations we define a noncommutative affine scheme X = Spf(A) for a Lie-complete ring A. The main result of the paper asserts that the topological localization A_(f) of A at f ∈ A is embedded into the ring 𝒪_A(X_f) of all sections of the structure sheaf 𝒪_A on the principal open set X_f as a dense subring with respect to the weak I₁-adic topology, where I₁ is the two-sided ideal generated by all commutators in A. The equality A_(f) = 𝒪_A(X_f) can only be achieved in the case of an NC-complete ring A.     

Fell topology on the space of functions with closed graph

LetX andY beT ₁ topological spaces andG(X, Y) the space of all functions with closed graph. Conditions under which the Fell topology and the weak Fell topology coincide onG(X,Y) are given. Relations between the convergence in the Fell topologyτF, Kuratowski and continuous convergence are studied too. Characterizations of a topological spaceX by separation axioms of (G(X, R), τF) and topological properties of (G(X, R), τF) are investigated.     

无爪3 -正则图的独立数

如果图G的一个集合X中任两个点不相邻, 则称 X 为独立集合. 如果 N[X]=V(G), 则称X是一个控制集合. i(G)(β(G))分别表示所有极大独立集合的最小(最大)基数. γ(G)(Γ(G))表示所有极小控制集合的最小(最大)基数. 在这篇论文中, 作者证明如下结论: (1) 如果 G ∈R 且G 是n阶3 -正则图, 则 γ(G)= i(G), β(G)=n/3. (2) 每个n阶连通无爪3 -正则图 G, 如果 G(G≠ K₄) 且不含诱导子图K₄-e, 则 β(G) =n/3.