Groups with an element permuting with finitely many of its conjugates

We study the problem as to which is the cardinality of connected components of the graph Γ_α, defined as follows. Let G be a group and a an element of G. The vertex set V(Γ_α) of the graph is the conjugacy class of elements,Cl _G(a), and two vertices x and y of the graph Γ_α are bridged by an edge iff x=y. If the intersectionC _G(a)∩Cl _G(a) is finite, Γ_α is locally finite. We prove that connected components of the locally finite graph Γ_α are finite in some classes of groups. Supported by RFFR grant No. 94-01-01084. Translated fromAlgebra i Logika, Vol. 35, No. 5, pp. 543–551, September–October, 1996.     

One-regular Normal Cayley Graphs on Dihedral Groups of Valency 4 or 6 with Cyclic Vertex Stabilizer

A graph G is one-regular if its automorphism group Aut（G） acts transitively and semiregularly on the arc set. A Cayley graph Cay（Г, S） is normal if Г is a normal subgroup of the full automorphism group of Cay（Г, S）. Xu, M. Y., Xu, J. （Southeast Asian Bulletin of Math., 25, 355-363 （2001）） classified one-regular Cayley graphs of valency at most 4 on finite abelian groups. Marusic, D., Pisanski, T. （Croat. Chemica Acta, 73, 969-981 （2000）） classified cubic one-regular Cayley graphs on a dihedral group, and all of such graphs turn out to be normal. In this paper, we classify the 4-valent one-regular normal Cayley graphs G on a dihedral group whose vertex stabilizers in Aut（G） are cyclic. A classification of the same kind of graphs of valency 6 is also discussed.     

Unique ergodicity of flows on homogeneous spaces

LetG be a unimodular Lie group, Γ a co-compact discrete subgroup ofG and ‘a’ a semisimple element ofG. LetT _a be the mapgΓ →ag Γ:G/Γ →G/Γ. The following statements are pairwise equivalent: (1) (T _a, G/Γ,θ) is weak-mixing. (2) (T _a, G/Γ) is topologically weak-mixing. (3) (G ^u, G/Γ) is uniquely ergodic. (4) (G ^u, G/Γ,θ) is ergodic. (5) (G ^u, G/Γ) is point transitive. (6) (G ^u, G/Γ) is minimal. If in additionG is semisimple with finite center and no compact factors, then the statement “(T _a, G/Γ,θ) is ergodic” may be added to the above list. The authors were partially supported by NSF grant MCS 75-05250.     

Some results on R 2-edge-connectivity of even regular graphs

Let G be a connected k(≥3)-regular graph with girth g. A set S of the edges in G is called an Rredge-cut if G-S is disconnected and comains neither an isolated vertex nor a one-degree vertex. The R2-edge-connectivity of G, denoted by λ^n(G), is the minimum cardinality over all R2-edge-cuts, which is an important measure for fault-tolerance of computer interconnection networks. In this paper, λ^n(G)=g(2k-2) for any 2k-regular connected graph G (≠K5) that is either edge-transitive or vertex-transitive and g≥5 is given.     

An Upper Bound for the Total Domination Subdivision Number of a Graph

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 sd_gt(G){{\rm sd}_{\gamma_t}(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 total domination number. In this paper, we prove that sd_gt(G) ￡ 2g_t(G)-1{{\rm sd}_{\gamma_t}(G)\leq 2\gamma_t(G)-1} for every simple connected graph G of order n ≥ 3.     

Černý’s conjecture and group representation theory

Let us say that a Cayley graph Γ of a group G of order n is a Černy Cayley graph if every synchronizing automaton containing Γ as a subgraph with the same vertex set admits a synchronizing word of length at most (n−1)². In this paper we use the representation theory of groups over the rational numbers to obtain a number of new infinite families of Černy Cayley graphs.     

Structure of the automorphism group for partially commutative class two nilpotent groups

Let R be a ring, which is either a ring of integers or a field of zero characteristic. For every finite graph Γ, we construct an R-arithmetic linear group H(Γ). The group H(Γ) is realized as the factor automorphism group of a partially commutative class two nilpotent R-group G _Γ. Also we describe the structure of the entire automorphism group of a partially commutative nilpotent R-group of class two.     

A characterization of alternating groups. II

Let G be a group. A subset X of G is called an A-subset if X consists of elements of order 3, X is invariant in G, and every two non-commuting members of X generate a subgroup isomorphic to A₄ or to A₅. Let X be the A-subset of G. Define a non-oriented graph Γ(X) with vertex set X in which two vertices are adjacent iff they generate a subgroup isomorphic to A₄. Theorem 1 states the following. Let X be a non-empty A-subset of G. (1) Suppose that C is a connected component of Γ(X) and H = 〈C〉. If H ∩ X does not contain a pair of elements generating a subgroup isomorphic to A₅ then H contains a normal elementary Abelian 2-subgroup of index 3 and a subgroup of order 3 which coincides with its centralizer in H. In the opposite case, H is isomorphic to the alternating group A(I) for some (possibly infinite) set I, |I| ≥ 5. (2) The subgroup 〈X^G〉 is a direct product of subgroups 〈C _α〉-generated by some connected components C _α of Γ(X). Theorem 2 asserts the following. Let G be a group and X⊆G be a non-empty G-invariant set of elements of order 5 such that every two non-commuting members of X generate a subgroup isomorphic to A₅. Then 〈XG〉 is a direct product of groups each of which either is isomorphic to A₅ or is cyclic of order 5. Supported by RFBR grant No. 05-01-00797; FP “Universities of Russia,” grant No. UR.04.01.028; RF Ministry of Education Developmental Program for Scientific Potential of the Higher School of Learning, project No. 511; Council for Grants (under RF President) and State Aid of Fundamental Science Schools, project NSh-2069.2003.1. __________ Translated from Algebra i Logika, Vol. 45, No. 2, pp. 203–214, March–April, 2006.     

Commutative rings whose zero-divisor graph is a proper refinement of a star graph

A graph is called a proper refinement of a star graph if it is a refinement of a star graph, but it is neither a star graph nor a complete graph. For a refinement of a star graph G with center c, let G _c ^* be the subgraph of G induced on the vertex set V (G)\ {c or end vertices adjacent to c}. In this paper, we study the isomorphic classification of some finite commutative local rings R by investigating their zero-divisor graphs G = Γ(R), which is a proper refinement of a star graph with exactly one center c. We determine all finite commutative local rings R such that G _c ^* has at least two connected components. We prove that the diameter of the induced graph G _c ^* is two if Z(R)² ≠ {0}, Z(R)³ = {0} and G _c ^* is connected. We determine the structure of R which has two distinct nonadjacent vertices α, β ∈ Z(R)* \ {c} such that the ideal [N(α) ∩ N(β)]∪ {0} is generated by only one element of Z(R)*\{c}. We also completely determine the correspondence between commutative rings and finite complete graphs K _n with some end vertices adjacent to a single vertex of K _n .     

The diameter of paired-domination vertex critical graphs

In this paper we continue the study of paired-domination in graphs introduced by Haynes and Slater (Networks 32 (1998), 199–206). A paired-dominating set of a graph G with no isolated vertex is a dominating set of vertices whose induced subgraph has a perfect matching. The paired-domination number of G, denoted by γ _pr(G), is the minimum cardinality of a paired-dominating set of G. The graph G is paired-domination vertex critical if for every vertex v of G that is not adjacent to a vertex of degree one, γ _pr(G − v) < γ _pr(G). We characterize the connected graphs with minimum degree one that are paired-domination vertex critical and we obtain sharp bounds on their maximum diameter. We provide an example which shows that the maximum diameter of a paired-domination vertex critical graph is at least 3/2 (γ _pr(G) − 2). For γ _pr(G) ⩽ 8, we show that this lower bound is precisely the maximum diameter of a paired-domination vertex critical graph. The first author was supported in part by the South African National Research Foundation and the University of KwaZulu-Natal, the second author was supported by the Natural Sciences and Engineering Research Council of Canada.     

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.     

Connected Domination Number of a Graph and its Complement

A set S of vertices in a graph G is a connected dominating set if every vertex not in S is adjacent to some vertex in S and the subgraph induced by S is connected. The connected domination number γ _c (G) is the minimum size of such a set. Let d^*(G)=min{d(G),d([`(G)])}{\delta^*(G)={\rm min}\{\delta(G),\delta({\overline{G}})\}} , where [`(G)]{{\overline{G}}} is the complement of G and δ(G) is the minimum vertex degree. We prove that when G and [`(G)]{{\overline{G}}} are both connected, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ d^*(G)+4-(g_c(G)-3)(g_c([`(G)])-3){{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+4-({\gamma_c}(G)-3)({\gamma_c}({\overline{G}})-3)} . As a corollary, g<sub>c</sub>(G)+g<sub>c</sub>([`(G)]) ￡ \frac3n4{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \frac{3n}{4}} when δ*(G) ≥ 3 and n ≥ 14, where G has n vertices. We also prove that g_c(G)+g_c([`(G)]) ￡ d<sup>*</sup>(G)+2{{\gamma_c}(G)+{\gamma_c}({\overline{G}})\le \delta^*(G)+2} when g<sub>c</sub>(G),g<sub>c</sub>([`(G)]) 3 4{{\gamma_c}(G),{\gamma_c}({\overline{G}})\ge 4} . This bound is sharp when δ*(G) = 6, and equality can only hold when δ*(G) = 6. Finally, we prove that g_c(G)g_c([`(G)]) ￡ 2n-4{{\gamma_c}(G){\gamma_c}({\overline{G}})\le 2n-4} when n ≥ 7, with equality only for paths and cycles.     

Mutual isomorphisms of translations of a homogeneous flow

Ergodic one-parameter flows (G/Γ,g _ℝ) induced by the left action of a subgroupg _ℝ ⊂G on homogeneous spaces of finite volume are considered. Letℳ ⊂ ℝ⁺ be the set of allt>0 such that the cascade (G/Γ,g _t ℤ) is metrically isomorphic to the cascade (G/Γ,g _ℤ). We prove that eitherℳ is at most countable or the subgroupg _ℝ is horocyclic andℳ=ℝ⁺. We prove that a metric isomorphism of ergodic quasi-unipotent cascades (or flows) is affine on almost all fibers of a certain natural bundle. The result generalizes Witte's theorem on the affinity of such isomorphisms of cascades with the mixing property; this is applied to the study of the structure of the setℳ ⊂ ℝ⁺. The proof is based on the fundamental Ratner theorem stating that the ergodic measures of unipotent cascades are algebraic. Translated fromMatematicheskie Zametki, Vol. 58, No. 1, pp. 98–110, July, 1995. This research was partially supported by the Russian Foundation for Basic Research under grant No. 94-01-00082a and by the International Science Foundation.     

On semisymmetric cubic graphs of order 6p~2

A graph r is said to be G-semisymmetric if it is regular and there exists a subgroup G of A := Aut(Г) acting transitively on its edge set but not on its vertex set. In the case of G. = A, we call r a semisymmetric graph. The aim of this paper is to investigate (G-)semisymmetric graphs of prime degree. We give a group-theoretical construction of such graphs, and give a classification of semisymmetric cubic graphs of order 6p2 for an odd prime p.     

Total Domination in Graphs with Given Girth

A set S of vertices in a graph G without isolated vertices is a total dominating set of G if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number γ _t (G) of G. In this paper, we establish an upper bound on the total domination number of a graph with minimum degree at least two in terms of its order and girth. We prove that if G is a graph of order n with minimum degree at least two and girth g, then γ _t (G) ≤ n/2 + n/g, and this bound is sharp. Our proof is an interplay between graph theory and transversals in hypergraphs. Michael A. Henning: Research supported in part by the South African National Research Foundation and the University of KwaZulu-Natal.     

Affinely equivalent complete flat manifolds

Let E _Aff(Γ,G, m) be the set of affine equivalence classes of m-dimensional complete flat manifolds with a fixed fundamental group Γ and a fixed holonomy group G. Let n be the dimension of a closed flat manifold whose fundamental group is isomorphic to Γ. We describe E _Aff(Γ,G, m) in terms of equivalence classes of pairs (ε, ρ), consisting of epimorphisms of Γ onto G and representations of G in ℝ ^m-n . As an application we give some estimates of card E _Aff(Γ,G, m).     

Characterization of $ {\mathbb{A}_{16}} $ by a noncommuting graph

Let G be a finite non-Abelian group. We define a graph Γ _G ; called the noncommuting graph of G; with a vertex set G − Z(G) such that two vertices x and y are adjacent if and only if xy ≠ yx: Abdollahi, Akbari, and Maimani put forward the following conjecture (the AAM conjecture): If S is a finite non-Abelian simple group and G is a group such that Γ _S ≅ Γ _G ; then S ≅ G: It is still unknown if this conjecture holds for all simple finite groups with connected prime graph except \mathbbA₁₀ {\mathbb{A}_{10}} , L ₄(8), L ₄(4), and U ₄(4). In this paper, we prove that if \mathbbA₁₆ {\mathbb{A}_{16}} denotes the alternating group of degree 16; then, for any finite group G; the graph isomorphism G_\mathbbA16 @ G_G {\Gamma_{{\mathbb{A}_{16}}}} \cong {\Gamma_G} implies that \mathbbA₁₆ @ G {\mathbb{A}_{16}} \cong G .     

（g, f）-Factorizations Randomly Orthogonal to a Subgraph in Graphs

Let G be a graph with vertex set V(G) and edge set E(G) and let g and f be two integervalued functions defined on V(G) such that 2k - 2 ≤g(x)≤f(x) for all x∈V(G). Let H be a subgraph of G with mk edges. In this paper, it is proved that every (mg m-1,mf-m 1)-graph G has (g, f)-factorizations randomly k-orthogonal to H under some special conditions.     

Spectra of ergodic group actions

LetG be a locally compact second countable abelian group, (X, μ) aσ-finite Lebesgue space, and (g, x) →gx a non-singular, properly ergodic action ofG on (X, μ). Let furthermore Γ be the character group ofG and let Sp(G, X) ⊂ Γ denote theL ^∞-spectrum ofG on (X, μ). It has been shown in [5] that Sp(G, X) is a Borel subgroup of Γ and thatσ (Sp(G, X))<1 for every probability measureσ on Γ with lim sup_g→∞Re (g)<1, where is the Fourier transform ofσ. In this note we prove the following converse: ifσ is a probability measure on Γ with lim sup_g→∞Re (g)<1 (g)=1 then there exists a non-singular, properly ergodic action ofG on (X, μ) withσ(Sp(G, X))=1.