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.     

Generalization of a theorem of Gonchar

Let X and Y be two complex manifolds, let D⊂X and G⊂Y be two nonempty open sets, let A (resp. B) be an open subset of ∂D (resp. ∂G), and let W be the 2-fold cross ((D∪A)×B)∪(A×(B∪G)). Under a geometric condition on the boundary sets A and B, we show that every function locally bounded, separately continuous on W, continuous on A×B, and separately holomorphic on (A×G)∪(D×B) “extends” to a function continuous on a “domain of holomorphy” and holomorphic on the interior of .     

A lower bound on the total signed domination numbers of graphs

Let G be a finite connected simple graph with a vertex set V(G)and an edge set E(G). A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1}.The weight of f is W(f)=∑_(x∈V)(G)∪E(G))f(X).For an element x∈V(G)∪E(G),we define f[x]=∑_(y∈NT[x])f(y).A total signed domination function of G is a function f:V(G)∪E(G)→{-1,1} such that f[x]≥1 for all x∈V(G)∪E(G).The total signed domination numberγ_s~*(G)of G is the minimum weight of a total signed domination function on G. In this paper,we obtain some lower bounds for the total signed domination number of a graph G and compute the exact values ofγ_s~*(G)when G is C_n and P_n.     

Certain Homology Cycles of the Independence Complex of Grids

Let G be an infinite graph such that the automorphism group of G contains a subgroup K ?? ^d with the property that G/K is finite. We examine the homology of the independence complex Σ(G/I) of G/I for subgroups I of K of full rank, focusing on the case that G is the square, triangular, or hexagonal grid. Specifically, we look for a certain kind of homology cycles that we refer to as “cross-cycles,” the rationale for the terminology being that they are fundamental cycles of the boundary complex of some cross-polytope. For the special cases just mentioned, we determine the set Q(G,K) of rational numbers r such that there is a group I with the property that Σ(G/I) contains cross-cycles of degree exactly r?|G/I|?1; |G/I| denotes the size of the vertex set of G/I. In each of the three cases, Q(G,K) turns out to be an interval of the form [a,b]∩?={r∈?:a≤r≤b}. For example, for the square grid, we obtain the interval $[\frac{1}{5},\frac{1}{4}]\cap \mathbb{Q}Let G be an infinite graph such that the automorphism group of G contains a subgroup K ≅ℤ ^d with the property that G/K is finite. We examine the homology of the independence complex Σ(G/I) of G/I for subgroups I of K of full rank, focusing on the case that G is the square, triangular, or hexagonal grid. Specifically, we look for a certain kind of homology cycles that we refer to as “cross-cycles,” the rationale for the terminology being that they are fundamental cycles of the boundary complex of some cross-polytope. For the special cases just mentioned, we determine the set Q(G,K) of rational numbers r such that there is a group I with the property that Σ(G/I) contains cross-cycles of degree exactly r⋅|G/I|−1; |G/I| denotes the size of the vertex set of G/I. In each of the three cases, Q(G,K) turns out to be an interval of the form [a,b]∩ℚ={r∈ℚ:a≤r≤b}. For example, for the square grid, we obtain the interval [\frac15,\frac14]?\mathbbQ[\frac{1}{5},\frac{1}{4}]\cap \mathbb{Q}.     

Disjoint homotopic paths and trees in a planar graph

In this paper we describe a polynomial-time algorithm for the following problem:given: a planar graphG embedded in ℝ², a subset {I ₁, …,I _p} of the faces ofG, and pathsC ₁, …,C _k inG, with endpoints on the boundary ofI ₁ ∪ … ∪I _p; find: pairwise disjoint simple pathsP ₁, …,P _k inG so that, for eachi=1, …,k, P _i is homotopic toC _i in the space ℝ²\(I ₁ ∪ … ∪I _p). Moreover, we prove a theorem characterizing the existence of a solution to this problem. Finally, we extend the algorithm to disjoint homotopic trees. As a corollary we derive that, for each fixedp, there exists a polynormial-time algorithm for the problem:given: a planar graphG embedded in ℝ² and pairwise disjoint setsW ₁, …,W _k of vertices, which can be covered by the boundaries of at mostp faces ofG;find: pairwise vertex-disjoint subtreesT ₁, …,T _k ofG whereT _i (i=1, …, k).     

A topological position of the set of continuous maps in the set of upper semicontinuous maps

Let (X, ρ) be a metric space and ↓USCC(X) and ↓CC(X) be the families of the regions below all upper semi-continuous compact-supported maps and below all continuous compact-supported maps from X to I = [0, 1], respectively. With the Hausdorff-metric, they are topological spaces. In this paper, we prove that, if X is an infinite compact metric space with a dense set of isolated points, then (↓USCC(X), ↓CC(X)) ≈ (Q, c0 ∪ (Q \ Σ)), i.e., there is a homeomorphism h :↓USCC(X) → Q such that h(↓CC(X)) = c0 ∪ (Q \ Σ...     

Probability measures on [SIN] groups and some related ideals in group algebras

Given a locally compact group G, let J(G){\cal J}(G) denote the set of closed left ideals in L ¹(G), of the form J _μ = [L¹(G) * (δ _e − μ)]⁻, where μ is a probability measure on G. Let J_d(G)={\cal J}_d(G)= {J_m;m is discrete}\{J_{\mu};\mu\ {\rm is discrete}\} , J_a(G)={J_m;m is absolutely continuous}{\cal J}_a(G)=\{J_{\mu};\mu\ {\rm is absolutely continuous}\} . When G is a second countable [SIN] group, we prove that J(G)=J_d(G){\cal J}(G)={\cal J}_d(G) and that J_a(G){\cal J}_a(G) , being a proper subset of J(G){\cal J}(G) when G is nondiscrete, contains every maximal element of J(G){\cal J}(G) . Some results concerning the ideals J _μ in general locally compact second countable groups are also obtained.     

Dilations and Completions for Gabor Systems

Let be a full rank time-frequency lattice in ℝ ^d ×ℝ ^d . In this note we first prove that any dual Gabor frame pair for a Λ-shift invariant subspace M can be dilated to a dual Gabor frame pair for the whole space L ²(ℝ ^d ) when the volume v(Λ) of the lattice Λ satisfies the condition v(Λ)≤1, and to a dual Gabor Riesz basis pair for a Λ-shift invariant subspace containing M when v(Λ)>1. This generalizes the dilation result in Gabardo and Han (J. Fourier Anal. Appl. 7:419–433, [2001]) to both higher dimensions and dual subspace Gabor frame pairs. Secondly, for any fixed positive integer N, we investigate the problem whether any Bessel–Gabor family G(g,Λ) can be completed to a tight Gabor (multi-)frame G(g,Λ)∪(∪ _j=1 ^N G(g _j ,Λ)) for L ²(ℝ ^d ). We show that this is true whenever v(Λ)≤N. In particular, when v(Λ)≤1, any Bessel–Gabor system is a subset of a tight Gabor frame G(g,Λ)∪G(h,Λ) for L ²(ℝ ^d ). Related results for affine systems are also discussed. Communicated by Chris Heil.     

The Convexity Number of a Graph

 For two vertices u and v of a connected graph G, the set I[u,v] consists of all those vertices lying on a u−v shortest path in G, while for a set S of vertices of G, the set I[S] is the union of all sets I[u,v] for u,v∈S. A set S is convex if I[S]=S. The convexity number con(G) of G is the maximum cardinality of a proper convex set of G. The clique number ω(G) is the maximum cardinality of a clique in G. If G is a connected graph of order n that is not complete, then n≥3 and 2≤ω(G)≤con(G)≤n−1. It is shown that for every triple l,k,n of integers with n≥3 and 2≤l≤k≤n−1, there exists a noncomplete connected graph G of order n with ω(G)=l and con(G)=k. Other results on convex numbers are also presented. Received: August 19, 1998 Final version received: May 17, 2000     

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     

On uniformly continuous Nemytskij operators generated by set-valued functions

Let I = [0, 1], let Y be a real normed linear space, C a convex cone in Y and Z a real Banach space. Denote by clb(Z) the set of all nonempty, convex, closed and bounded subsets of Z. If a superposition operator N generated by a set-valued function F : I × C → clb(Z) maps the set H _α (I, C) of all Hölder functions ${\varphi : I \to C}Let I = [0, 1], let Y be a real normed linear space, C a convex cone in Y and Z a real Banach space. Denote by clb(Z) the set of all nonempty, convex, closed and bounded subsets of Z. If a superposition operator N generated by a set-valued function F : I × C → clb(Z) maps the set H _α (I, C) of all H?lder functions j: I ? C{\varphi : I \to C} into the set H _β (I, clb(Z)) of all H?lder set-valued functions f: I ? clb(Z){\phi : I \to clb(Z)} and is uniformly continuous, then

F(x,y)=A(x,y) \text+* B(x),       x ? I, y ? CF(x,y)=A(x,y) \stackrel{*}{\text{+}} B(x),\qquad x \in I, y \in C      12. On intrinsic ergodicity of piecewise monotonic transformations with positive entropy II      Franz Hofbauer 《Israel Journal of Mathematics》1981,38(1-2):107-115 The results about measures with maximal entropy, which are proved in [3], are extended to the following more general class of transformations on the unit intervalI : I=∪ i =1/n Ji, theJ i are disjoint intervals,f/J i is increasing or decreasing and continuous, andh top(f)>0.      13. Analytic Multifunctions, Holomorphic Motions and Hausdorff Dimension in IFSs      Line Baribeau  Mario Roy 《Monatshefte für Mathematik》2006,147(3):199-217 We study iterated function systems of contractions which depend holomorphically on a complex parameter λ. We first restrict our attention to systems which consist of similarities that satisfy the OSC. In this setting, we prove that the Hausdorff dimension of the limit set J(λ) is a continuous, subharmonic function of λ. In the remainder of the paper, systems consisting of conformal contractions are considered. We give conditions under which J(λ) and A(λ) = describe a holomorphic motion, and construct an example that shows that this is not the case in general. We finally show that A(λ) is best described as an analytic multifunction of λ, a notion that generalizes that of holomorphic motion. This research was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) and by the Fonds Québécois de Recherche sur la Nature et les Technologies (FQRNT). This research was supported by the FQRNT.      14. Dominating sets of the comaximal and ideal-based zero-divisor graphs of commutative rings      《Quaestiones Mathematicae》2013,36(5):613-629 Abstract Let R be a commutative ring with nonzero identity, and let I be an ideal of R. The ideal-based zero-divisor graph of R, denoted by ΓI (R), is the graph whose vertices are the set {x ∈ R \ I| xy ∈ I for some y∈ R \ I} and two distinct vertices x and y are adjacent if and only if xy ∈ I. Define the comaximal graph of R, denoted by CG(R), to be a graph whose vertices are the elements of R, where two distinct vertices a and b are adjacent if and only if Ra+Rb=R. A nonempty set S ? V of a graph G=(V, E) 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 paper is to study the dominating sets and domination number of ΓI (R) and the comaximal graph CG2(R) \ J (R) (or CGJ (R) for short) where CG2(R) is the subgraph of CG(R) induced on the nonunit elements of R and J (R) is the Jacobson radical of R.      15. Cycles in Partially Square Graphs      Ahmed Ainouche  Mekkia Kouider 《Graphs and Combinatorics》2001,17(1):1-9 . In this work we consider finite undirected simple graphs. If G=(V,E) is a graph we denote by α(G) the stability number of G. For any vertex x let N[x] be the union of x and the neighborhood N(x). For each pair of vertices ab of G we associate the set J(a,b) as follows. J(a,b)={u∈N[a]∩N[b]∣N(u)⊆N[a]∪N[b]}. Given a graph G, its partially squareG * is the graph obtained by adding an edge uv for each pair u,v of vertices of G at distance 2 whenever J(u,v) is not empty. In the case G is a claw-free graph, G * is equal to G 2. If G is k-connected, we cover the vertices of G by at most ⌈α(G *)/k⌉ cycles, where α(G *) is the stability number of the partially square graph of G. On the other hand we consider in G * conditions on the sum of the degrees. Let G be any 2-connected graph and t be any integer (t≥2). If ∑ x ∈ S deg G (x)≥|G|, for every t-stable set S⊆V(G) of G * then the vertex set of G can be covered with t−1 cycles. Different corollaries on covering by paths are given. Received: January 22, 1997 Final version received: February 15, 2000      16. Movement of Intransitive Permutation Groups Having Maximum Degree      Mehdi ALAEIYAN  Mehdi REZAEI 《数学年刊B辑(英文版)》2012,33(1):143-148 Let G be a permutation group on a set Ω with no fixed points in,and m be a positive integer.Then the movement of G is defined as move(G):=sup Γ {|Γg\Γ| | g ∈ G}.It was shown by Praeger that if move(G) = m,then |Ω| 3m + t-1,where t is the number of G-orbits on.In this paper,all intransitive permutation groups with degree 3m+t-1 which have maximum bound are classified.Indeed,a positive answer to her question that whether the upper bound |Ω| = 3m + t-1 for |Ω| is sharp for every t > 1 is given.      17. A construction of two distinct canonical sets of lifts of Brauer characters of a p-solvable group      James P. Cossey 《Archiv der Mathematik》2006,87(5):385-389 In [5], Navarro defines the set , where Q is a p-subgroup of a p-solvable group G, and shows that if δ is the trivial character of Q, then Irr(G|Q, δ) provides a set of canonical lifts of IBrp(G), the irreducible Brauer characters with vertex Q. Previously, in [2], Isaacs defined a canonical set of lifts Bπ(G) of Iπ(G). Both of these results extend the Fong-Swan Theorem to π-separable groups, and both construct canonical sets of lifts of the generalized Brauer characters. It is known that in the case that 2∈π, or if |G| is odd, we have Bπ(G) = Irr(G|Q, 1Q). In this note we give a counterexample to show that this is not the case when . It is known that if and χ∈Bπ(G), then the constituents of χN are in Bπ (N). However, we use the same counterexample to show that if , and χ∈Irr(G|Q, 1Q) is such that θ ∈Irr(N) and [θ, χ N] ≠ 0, then it is not necessarily the case that θ ∈Irr(N) inherits this property. Received: 17 October 2005      18. A theorem on level lines of continuous functions      Z. Waksman  J. Wasilewsky 《Israel Journal of Mathematics》1977,27(3-4):247-251 A property of a continuous functionf(x), x ∈ E 2, similar to the classical intermediate value property is established. Namely, let a Jordan compactJ ⊂ E 2 be the domain of definition off. Then, for each parametrizationx(t), 0≦t≦T,x(0)=x(T), of the boundary Fr(J) ofJ there exists a unique real λ and a unique connected component Φ of the level set {x ∈ J: f(x)=λ} with the following property: any connected subset Ω ofJ containing “opposite” points of Fr(J) (i.e. pointsx(t′) andx(t″) such thatt″−t′=T/2) has a common element with Φ.      19. Every 4-connected line graph of a quasi claw-free graph is hamiltonian connected      Hong-Jian Lai  Yehong Shao  Mingquan Zhan   《Discrete Mathematics》2008,308(22):5312-5316 Let G be a graph. For u,vV(G) with distG(u,v)=2, denote JG(u,v)={wNG(u)∩NG(v)|NG(w)NG(u)NG(v){u,v}}. A graph G is called quasi claw-free if JG(u,v)≠ for any u,vV(G) with distG(u,v)=2. In 1986, Thomassen conjectured that every 4-connected line graph is hamiltonian. In this paper we show that every 4-connected line graph of a quasi claw-free graph is hamiltonian connected.      20. Irreducible disconnected systems in groups      Gil Kaplan 《Israel Journal of Mathematics》1999,111(1):203-219 LetG be an arbitrary group with a subgroupA. The subdegrees of (A, G) are the indices [A:A ∪A 9] (wheregεG). Equivalent definitions of that concept are given in [IP] and [K]. IfA is not normal inG and all the subdegrees of (A, G) are finite, we attach to (A, G) the common divisor graph Γ: its vertices are the non-unit subdegrees of (A, G), and two different subdegrees are joined by an edge iff they arenot coprime. It is proved in [IP] that Γ has at most two connected components. Assume that Γ is disconnected. LetD denote the subdegree set of (A, G) and letD 1 be the set of all the subdegrees in the component of Γ containing min(D−{1}). We proved [K, Theorem A] that ifA is stable inG (a property which holds whenA or [G:A] is finite), then the setH={g ε G| [A:A ∪A g ] εD 1 ∪ {1}} is a subgroup ofG. In this case we say thatA<H<G is a disconnected system (briefly: a system). In the current paper we deal with some fundamental types of systems. A systemA<H<G is irreducible if there does not exist 1<N△G such thatAN<H andAN/N<H/N<G/N is a system. Theorem A gives restrictions on the finite nilpotent normal subgroups ofG, whenG possesses an irreducible system. In particular, ifG is finite then Fit(G) is aq-group for a certain primeq. We deal also with general systems. Corollary (4.2) gives information about the structure of a finite groupG which possesses a system. Theorem B says that for any systemA<H<G,N G (N G (A))=N G (A). Theorem C and Corollary C’ generalize a result of Praeger [P, Theorem 2]. The content of this paper corresponds to a part of the author’s Ph.D. thesis carried out at Tel Aviv University under the supervision of Prof. Marcel Herzog.

On intrinsic ergodicity of piecewise monotonic transformations with positive entropy II

The results about measures with maximal entropy, which are proved in [3], are extended to the following more general class of transformations on the unit intervalI : I=∪ _i ^=1/n J_i, theJ _i are disjoint intervals,f/J _i is increasing or decreasing and continuous, andh _top(f)>0.     

Analytic Multifunctions, Holomorphic Motions and Hausdorff Dimension in IFSs

We study iterated function systems of contractions which depend holomorphically on a complex parameter λ. We first restrict our attention to systems which consist of similarities that satisfy the OSC. In this setting, we prove that the Hausdorff dimension of the limit set J(λ) is a continuous, subharmonic function of λ. In the remainder of the paper, systems consisting of conformal contractions are considered. We give conditions under which J(λ) and A(λ) = describe a holomorphic motion, and construct an example that shows that this is not the case in general. We finally show that A(λ) is best described as an analytic multifunction of λ, a notion that generalizes that of holomorphic motion. This research was supported by the Natural Sciences and Engineering Research Council of Canada (NSERC) and by the Fonds Québécois de Recherche sur la Nature et les Technologies (FQRNT). This research was supported by the FQRNT.     

Dominating sets of the comaximal and ideal-based zero-divisor graphs of commutative rings

Abstract

Let R be a commutative ring with nonzero identity, and let I be an ideal of R. The ideal-based zero-divisor graph of R, denoted by Γ_I (R), is the graph whose vertices are the set {x ∈ R \ I| xy ∈ I for some y∈ R \ I} and two distinct vertices x and y are adjacent if and only if xy ∈ I. Define the comaximal graph of R, denoted by CG(R), to be a graph whose vertices are the elements of R, where two distinct vertices a and b are adjacent if and only if Ra+Rb=R. A nonempty set S ? V of a graph G=(V, E) 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 paper is to study the dominating sets and domination number of Γ_I (R) and the comaximal graph CG₂(R) \ J (R) (or CGJ (R) for short) where CG₂(R) is the subgraph of CG(R) induced on the nonunit elements of R and J (R) is the Jacobson radical of R.     

Cycles in Partially Square Graphs

. In this work we consider finite undirected simple graphs. If G=(V,E) is a graph we denote by α(G) the stability number of G. For any vertex x let N[x] be the union of x and the neighborhood N(x). For each pair of vertices ab of G we associate the set J(a,b) as follows. J(a,b)={u∈N[a]∩N[b]∣N(u)⊆N[a]∪N[b]}. Given a graph G, its partially squareG ^* is the graph obtained by adding an edge uv for each pair u,v of vertices of G at distance 2 whenever J(u,v) is not empty. In the case G is a claw-free graph, G ^* is equal to G ². If G is k-connected, we cover the vertices of G by at most ⌈α(G ^*)/k⌉ cycles, where α(G ^*) is the stability number of the partially square graph of G. On the other hand we consider in G ^* conditions on the sum of the degrees. Let G be any 2-connected graph and t be any integer (t≥2). If ∑ _{x ∈ S} deg _G (x)≥|G|, for every t-stable set S⊆V(G) of G ^* then the vertex set of G can be covered with t−1 cycles. Different corollaries on covering by paths are given. Received: January 22, 1997 Final version received: February 15, 2000     

Movement of Intransitive Permutation Groups Having Maximum Degree

Let G be a permutation group on a set Ω with no fixed points in,and m be a positive integer.Then the movement of G is defined as move(G):=sup Γ {|Γg\Γ| | g ∈ G}.It was shown by Praeger that if move(G) = m,then |Ω| 3m + t-1,where t is the number of G-orbits on.In this paper,all intransitive permutation groups with degree 3m+t-1 which have maximum bound are classified.Indeed,a positive answer to her question that whether the upper bound |Ω| = 3m + t-1 for |Ω| is sharp for every t > 1 is given.     

A construction of two distinct canonical sets of lifts of Brauer characters of a p-solvable group

In [5], Navarro defines the set , where Q is a p-subgroup of a p-solvable group G, and shows that if δ is the trivial character of Q, then Irr(G|Q, δ) provides a set of canonical lifts of IBr_p(G), the irreducible Brauer characters with vertex Q. Previously, in [2], Isaacs defined a canonical set of lifts B_π(G) of I_π(G). Both of these results extend the Fong-Swan Theorem to π-separable groups, and both construct canonical sets of lifts of the generalized Brauer characters. It is known that in the case that 2∈π, or if |G| is odd, we have B_π(G) = Irr(G|Q, 1_Q). In this note we give a counterexample to show that this is not the case when . It is known that if and χ∈B_π(G), then the constituents of χ_N are in B_π (N). However, we use the same counterexample to show that if , and χ∈Irr(G|Q, 1_Q) is such that θ ∈Irr(N) and [θ, χ _N] ≠ 0, then it is not necessarily the case that θ ∈Irr(N) inherits this property. Received: 17 October 2005     

A theorem on level lines of continuous functions

A property of a continuous functionf(x), x ∈ E ₂, similar to the classical intermediate value property is established. Namely, let a Jordan compactJ ⊂ E ₂ be the domain of definition off. Then, for each parametrizationx(t), 0≦t≦T,x(0)=x(T), of the boundary Fr(J) ofJ there exists a unique real λ and a unique connected component Φ of the level set {x ∈ J: f(x)=λ} with the following property: any connected subset Ω ofJ containing “opposite” points of Fr(J) (i.e. pointsx(t′) andx(t″) such thatt″−t′=T/2) has a common element with Φ.     

Every 4-connected line graph of a quasi claw-free graph is hamiltonian connected

Let G be a graph. For u,vV(G) with dist_G(u,v)=2, denote J_G(u,v)={wN_G(u)∩N_G(v)|N_G(w)N_G(u)N_G(v){u,v}}. A graph G is called quasi claw-free if J_G(u,v)≠ for any u,vV(G) with dist_G(u,v)=2. In 1986, Thomassen conjectured that every 4-connected line graph is hamiltonian. In this paper we show that every 4-connected line graph of a quasi claw-free graph is hamiltonian connected.     

Irreducible disconnected systems in groups

LetG be an arbitrary group with a subgroupA. The subdegrees of (A, G) are the indices [A:A ∪A ⁹] (wheregεG). Equivalent definitions of that concept are given in [IP] and [K]. IfA is not normal inG and all the subdegrees of (A, G) are finite, we attach to (A, G) the common divisor graph Γ: its vertices are the non-unit subdegrees of (A, G), and two different subdegrees are joined by an edge iff they arenot coprime. It is proved in [IP] that Γ has at most two connected components. Assume that Γ is disconnected. LetD denote the subdegree set of (A, G) and letD ₁ be the set of all the subdegrees in the component of Γ containing min(D−{1}). We proved [K, Theorem A] that ifA is stable inG (a property which holds whenA or [G:A] is finite), then the setH={g ε G| [A:A ∪A ^g ] εD ₁ ∪ {1}} is a subgroup ofG. In this case we say thatA<H<G is a disconnected system (briefly: a system). In the current paper we deal with some fundamental types of systems. A systemA<H<G is irreducible if there does not exist 1<N△G such thatAN<H andAN/N<H/N<G/N is a system. Theorem A gives restrictions on the finite nilpotent normal subgroups ofG, whenG possesses an irreducible system. In particular, ifG is finite then Fit(G) is aq-group for a certain primeq. We deal also with general systems. Corollary (4.2) gives information about the structure of a finite groupG which possesses a system. Theorem B says that for any systemA<H<G,N _G (N _G (A))=N _G (A). Theorem C and Corollary C’ generalize a result of Praeger [P, Theorem 2]. The content of this paper corresponds to a part of the author’s Ph.D. thesis carried out at Tel Aviv University under the supervision of Prof. Marcel Herzog.