Path-closed sets

Given a digraphG = (V, E), call a node setT ⊆V path-closed ifv, v′ εT andw εV is on a path fromv tov′ impliesw εT. IfG is the comparability graph of a posetP, the path-closed sets ofG are the convex sets ofP. We characterize the convex hull of (the incidence vectors of) all path-closed sets ofG and its antiblocking polyhedron inR ^v , using lattice polyhedra, and give a minmax theorem on partitioning a given subset ofV into path-closed sets. We then derive good algorithms for the linear programs associated to the convex hull, solving the problem of finding a path-closed set of maximum weight sum, and prove another min-max result closely resembling Dilworth’s theorem.     

Constructive characterizations of （γp, γ）- and （γp, γpr）-trees

Let G = （V, E） be a graph without isolated vertices. A set S lohtain in V is a domination set of G if every vertex in V - S is adjacent to a vertex in S, that is N[S] = V. The domination number of G, denoted by γ（G）, is the minimum cardinality of a domination set of G. A set S lohtain in V is a paired-domination set of G if S is a domination set of G and the induced subgraph G[S] has a perfect matching. The paired-domination number, denoted by γpr（G）, is defined to be the minimum cardinality of a paired-domination set S in G. A subset S lohtain in V is a power domination set of G if all vertices of V can be observed recursively by the following rules： （i） all vertices in N[S] are observed initially, and （ii） if an observed vertex u has all neighbors observed except one neighbor v, then v is observed （by u）. The power domination number, denoted by γp（G）, is the minimum cardinality of a power domination set of G. In this paper, the constructive characterizations for trees with γp=γ and γpr = γp are provided respectively.     

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.     

Dichotomies of the set of test measures of a Haar-null set

We prove that ifX is a Polish space andF a face ofP(X) with the Baire property, thenF is either a meager or a co-meager subset ofP(X). As a consequence we show that for every abelian Polish groupX and every analytic Haar-null set Λ⊆X, the set of test measuresT(Λ) of Λ is either meager or co-meager. We characterize the non-locally-compact groups as the ones for which there exists a closed Haar-null setF⊆X withT(F) meager, Moreover, we answer negatively a question of J. Mycielski by showing that for every non-locally-compact abelian Polish group and every σ-compact subgroupG ofX there exists aG-invariantF _σ subset ofX which is neither prevalent nor Haar-null. Research supported by a grant of EPEAEK program “Pythagoras”.     

THE TOTAL CHROMATIC NUMBER OF PSEUDO-OUTERPLANAR GRAPHS

A Planar graph g is called a ipseudo outerplanar graph if there is a subset v.∈V(G),[V.]=i,such that G-V. is an outerplanar graph in particular when G-V.is a forest ,g is called a i-pseudo-tree .in this paper.the following results are proved;(1)the conjecture on the total coloring is true for all 1-pseudo-outerplanar graphs;(2)X1(G) 1 fo any 1-pseudo outerplanar graph g with △(G)≥3,where x4(G)is the total chromatic number of a graph g.     

A covering subgroup system for the class of <Emphasis Type="Italic">p</Emphasis>-nilpotent groups

Let ℱ be a class of groups and let G be a finite group. We call a set Σ of subgroups of G a covering subgroup system of G for ℱ (or directly an ℱ-covering subgroup system of G) if G ∈ ℱ whenever every subgroup in Σ is in ℱ. We give some covering subgroup systems for the class of all p-nilpotent groups.     

A new approach to chordal graphs

By a chordal graph is meant a graph with no induced cycle of length ⩾ 4. By a ternary system is meant an ordered pair (W, T), where W is a finite nonempty set, and T ⊆ W × W × W. Ternary systems satisfying certain axioms (A1)–(A5) are studied in this paper; note that these axioms can be formulated in a language of the first-order logic. For every finite nonempty set W, a bijective mapping from the set of all connected chordal graphs G with V(G) = W onto the set of all ternary systems (W, T) satisfying the axioms (A1)–(A5) is found in this paper.     

Classifying almost-disjoint families with applications toβN − N

A family of infinite subsets of the setN of natural numbers will be called almost disjoint iff any two of its members have finite intersection. We shall define such a family ℱ to ben-separable iff for every decompositionD = {D ₁, …D _n } ofN inton or fewer disjoint subsets there exist setsF ∈ ℱ andD ∃D such thatF ⊆D, and we shall use this and related notions to classify almost-disjoint families, using, on occasion, special axioms of set theory.     

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.     

ℱ-subnormal and ℱ-subabnormal chains in finite groups

The class ℱ_pc of all finite groupsG is defined such thatX≤G implies that there exists an ℱ-subnormal subgroupS ofG containingX such thatX is ℱ-subabnormal inS, where ℱ is a saturated formation, closed under taken subgroups. Groups in ℱ_pc are characterized by ℱ-projectors and ℱ-covering subgroups. Project supported by the National Natural Science Foundation of China (Grant No. 19760001) and the Natural Science Foundation of Guangxi Autonomous Region.     

A module as a torsion-free cover

LetR be a ring, and let (ℐ, ℱ) be an hereditary torsion theory of leftR-modules. An epimorphism ψ:M→X is called a torsion-free cover ofX if (1)M∈ ℱ, (2) every homomorphism from a torsion-free module intoX can be factored throughM, and (3) ker ψ contains no nonzero ℐ -closed submodules ofM. Conditions onM andN are studied to determine when the natural mapsM→M/N andQ(M)→Q(M)/N are torsion-free covers, whenQ(M) is the localization ofM with respect to (ℐ, ℱ). IfM→M/N is a torsion-free cover andM is projective, thenN⊆radM. Consequently, the concepts of projective cover and torsion-free cover coincide in some interesting cases.     

Some remarks on subgroups determined by certain ideals in integral group rings

LetG be a group,ZG the integral group ring ofG andI(G) its augmentation ideal. Subgroups determined by certain ideals ofZG contained inI(G) are identified. For example, whenG=HK, whereH, K are normal subgroups ofG andH∩K⊆ζ(H), then the subgroups ofG determined byI(G)I(H)I(G), andI ³(G)I(H) are obtained. The subgroups of any groupG with normal subgroupH determined by (i)I ²(G)I(H)+I(G)I(H)I(G)+I(H)I²(G), whenH′⊆[H,G,G] and (ii)I(G)I(H)I(G) when degH ²(G/H′, T)≤1, are computed. the subgroup ofG determined byI ⁿ(G)+I(G)I(H) whenH is a normal subgroup ofG withG/H free Abelian is also obtained     

Bounds on the Distance Two-Domination Number of a Graph

 For a graph G = (V, E), a subset D⊆V(G) is said to be distance two-dominating set in G if for each vertex u∈V−D, there exists a vertex v∈D such that d(u,v)≤2. The minimum cardinality of a distance two-dominating set in G is called a distance two-domination number and is denoted by γ₂(G). In this note we obtain various upper bounds for γ₂(G) and characterize the classes of graphs attaining these bounds. Received: May 31, 1999 Final version received: July 13, 2000     

Domination in Graphs of Minimum Degree Five

Let G=(V,E) be a simple graph. A subset D⊆V is a dominating set of G, if for any vertex x ∈ V−D, there exists a vertex y ∈ D such that xy ∈ E. By using the so-called vertex disjoint paths cover introduced by Reed, in this paper we prove that every graph G on n vertices with minimum degree at least five has a dominating set of order at most 5n/14.     

No distribution is prime

Summary Letℱ denote the convolution semigroup of probability distributions on the real line. We prove thatno element of ℱ is prime in the sense that given anℱ one can always find two distributionsG,H∈ℱ such thatF is a convolution factor ofG#x002A;H but neither ofG nor ofH. In contrast,ℱ is known to possess many irreducible elements.     

Closed Separator Sets

A smallest separator in a finite, simple, undirected graph G is a set S ⊆ V (G) such that G–S is disconnected and |S|=κ(G), where κ(G) denotes the connectivity of G. A set S of smallest separators in G is defined to be closed if for every pair S,T ∈ S, every component C of G–S, and every component S of G–T intersecting C either X(C,D) := (V (C) ∩ T) ∪ (T ∩ S) ∪ (S ∩ V (D)) is in S or |X(C,D)| > κ(G). This leads, canonically, to a closure system on the (closed) set of all smallest separators of G. A graph H with is defined to be S-augmenting if no member of S is a smallest separator in G ∪ H:=(V (G) ∪ V (H), E(G) ∪ E(H)). It is proved that if S is closed then every minimally S-augmenting graph is a forest, which generalizes a result of Jordán. Several applications are included, among them a generalization of a Theorem of Mader on disjoint fragments in critically k-connected graphs, a Theorem of Su on highly critically k-connected graphs, and an affirmative answer to a conjecture of Su on disjoint fragments in contraction critically k-connected graphs of maximal minimum degree.     

On the Structure of Graphs with Bounded Asteroidal Number

 A set A⊆V of the vertices of a graph G=(V,E) is an asteroidal set if for each vertex a∈A, the set A\{a} is contained in one component of G−N[a]. The maximum cardinality of an asteroidal set of G, denoted by an (G), is said to be the asteroidal number of G. We investigate structural properties of graphs of bounded asteroidal number. For every k≥1, an (G)≤k if and only if an (H)≤k for every minimal triangulation H of G. A dominating target is a set D of vertices such that D∪S is a dominating set of G for every set S such that G[D∪S] is connected. We show that every graph G has a dominating target with at most an (G) vertices. Finally, a connected graph G has a spanning tree T such that d _T (x,y)−d _G (x,y)≤3·|D|−1 for every pair x,y of vertices and every dominating target D of G. Received: July 3, 1998 Final version received: August 10, 1999     

A Note on Range-Restricted Circuit Covers

 Let Cone(G), Int.Cone(G) and Lat(G) be the cone, the integer cone and the lattice of the incidence vectors of the circuits of graph G. A good range is a set ?⊆ℕ such that Cone (G)∩Lat (G)∩?^E⊆Int.Cone(G) for every graph G(V,E). We give a counterexample to a conjecture of Goddyn [1] stating that ℕ\{1} is a good range. Received: November 26, 1997     

On s-quasinormal and c-normal subgroups of a finite group

Let F be a saturated formation containing the class of supersolvable groups and let G be a finite group. The following theorems are shown： （1） G ∈ F if and only if there is a normal subgroup H such that G/H ∈ F and every maximal subgroup of all Sylow subgroups of H is either c-normal or s-quasinormally embedded in G; （2） G ∈F if and only if there is a soluble normal subgroup H such that G/H∈F and every maximal subgroup of all Sylow subgroups of F（H）, the Fitting subgroup of H, is either e-normally or s-quasinormally embedded in G.     

Regelflächenscharen

Let K be any commutative field and V:=K ⁴. A collection of ruled quadrics in V is called a flock of ruled quadrics if the following holds true. (1) ⋃_{ℱ∈ G} ℱ = V; (2) There is a line S⊂V such that ℱ₁⋂ℱ₂= S for all distinct ℱ₁, ℱ₂∈ . The group ΓL(V) decomposes the set of all those flocks into equivalence classes. Besides that, we consider any cone R in V, say R:= {x∈V|x ₁ x ₃ - x ₂ ² = 0}. Let R denote the set of all regular points of R. Plane sections of R which do not contain the singular point of ℜ are called regular sections. We consider decompositions of R ^* by regular sections and their equivalence classes with respect to the symmetry group ΓL(V)R of the cone ℜ. The main result is as follows. There is a (natural) bijection between the classes of equivalent flocks of rules quadrics and the classes of equivalent decompositions of R ^* by regular sections. A brief discussion of those flocks of ruled quadrics on which the construction of the so-called Betten-Walker planes is based ends the paper. Provided that char K≠3, these planes exist if and only if x∈K→x ³∈K is bijective.