Prime interchange graphs of classes of matrices of zeros and ones

Let R = (r₁,…, r_m) and S = (s₁,…, s_n) be nonnegative integral vectors, and let $\text{U}$(R, S) denote the class of all m × n matrices of 0's and 1's having row sum vector R and column sum vector S. An invariant position of $\text{U}$(R, S) is a position whose entry is the same for all matrices in $\text{U}$(R, S). The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{U}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We prove that when 1 ≤ r_i ≤ n ? 1 (i = 1,…, m) and 1 ≤ s_j ≤ m ? 1 (j = 1,…, n), G(R, S) is prime if and only if $\text{U}$(R, S) has no invariant positions.     

Small diameter interchange graphs of classes of matrices of zeros and ones

Let $\text{A}$(R, S) denote the class of all m×n matrices of 0's and 1's having row sum vector R and column sum vector S. The interchange graph G(R, S) is the graph where the vertices are the matrices in $\text{A}$(R, S) and where two matrices are joined by an edge provided they differ by an interchange. We characterize those $\text{A}$(R, S) for which the graph G(R, S) has diameter at most 2 and those $\text{A}$(R, S) for which G(R, S) is bipartite.     

The relationship between the class %plane1D;518;2(R,S) of (0,1,2)-matrices and the collection of constellation matrices

Let %plane1D;518;₂(R,S) be the class of all (0, 1, 2)-matrices with a prescribed row sum vector R and column sum vector S. A (0, 1,2)-matrix in %plane1D;518;₂(R,S) is defined to be parsimonious provided no (0, 1, 2)-matrix with the same row and column sum vectors has fewer positive entries. In a parsimonious (0, 1, 2)-matrix A there are severe restrictions on the (0, 1)-matrix A⁽¹⁾ which records the positions of the 1's in A. Brualdi and Michael obtained some necessary arithmetic conditions for a set of matrices to serve simultaneously as the 1-pattern matrices for parsimonious matrices in a given class. In this paper, we provide a direct construction that proves that these conditions are also sufficient.     

Spectral theory of group representations and their nonstandard hull

We construct the nonstandard hull of a not necessarily bounded strongly continuous representationU of the locally compact semigroupS on a Banach spaceE. Then we apply our results to the theory of the spectrum σ (U) ofU, mainly in cases whereS is an abelian group, e.g.S=R. First of all we obtain generalizations to the unbounded case of results known for the bounded one. Secondly we introduce the notion of the Riesz part R σ(U) of σ(U) and characterize those representations satisfying σ(U)=R σ(U). We illustrate the theory developed so far by applications to representations on Banach lattices. Dedicated to Prof. Dr. H. H. Schaefer on the occasion of his 60th birthday     

The class A(R,S) of (0, 1)-matrices

Let R and S be two vectors whose components are m and n non-negative integers, respectively. Let $\text{A}$(R, S) be the class consisting of all (0, 1)-matrices of size m by n with row sum vector R and column sum vector S. In this paper we derive a lower bound to the cardinality of the class $\text{A}$(R, S), which can be computed readily.     

An interlacing theorem for matrices whose graph is a given tree

Let A and B be (n×n)-matrices. For an index set S ⊂ {1, …, n}, denote by A(S) the principal submatrix that lies in the rows and columns indexed by S. Denote by S′ the complement of S and define η(A, B) = det A(S) det B(S′), where the summation is over all subsets of {1, …, n} and, by convention, det A(∅) = det B(∅) = 1. C. R. Johnson conjectured that if A and B are Hermitian and A is positive semidefinite, then the polynomial η(λA,-B) has only real roots. G. Rublein and R. B. Bapat proved that this is true for n ⩽ 3. Bapat also proved this result for any n with the condition that both A and B are tridiagonal. In this paper, we generalize some little-known results concerning the characteristic polynomials and adjacency matrices of trees to matrices whose graph is a given tree and prove the conjecture for any n under the additional assumption that both A and B are matrices whose graph is a tree. __________ Translated from Fundamentalnaya i Prikladnaya Matematika, Vol. 10, No. 3, pp. 245–254, 2004.     

Recognition of finite groups by a set of orders of their elements

For G a finite group, ω(G) denotes the set of orders of elements in G. If ω is a subset of the set of natural numbers, h(ω) stands for the number of nonisomorphic groups G such that ω(G)=ω. We say that G is recognizable (by ω(G)) if h(ω(G))=1. G is almost recognizable (resp., nonrecognizable) if h(ω(G)) is finite (resp., infinite). It is shown that almost simple groups PGL_n(q) are nonrecognizable for infinitely many pairs (n, q). It is also proved that a simple group S₄(7) is recognizable, whereas A₁₀, U₃(5), U₃(7), U₄(2), and U₅(2) are not. From this, the following theorem is derived. Let G be a finite simple group such that every prime divisor of its order is at most 11. Then one of the following holds: (i) G is isomorphic to A₅, A₇, A₈, A₉, A₁₁, A₁₂, L₂(q), q=7, 8, 11, 49, L₃(4), S₄(7), U₄(3), U₆(2), M₁₁, M₁₂, M₂₂, HS, or M^cL, and G is recognizable by the set ω(G); (ii) G is isomorphic to A₆, A₁₀, U₃(3), U₄(2), U₅(2), U₃(5), or J₂, and G is nonrecognizable; (iii) G is isomorphic to S₆(2) or O ₈ ⁺ (2), and h(ω(G))=2. Supported by RFFR grant No. 96-01-01893. Translated fromAlgebra i Logika, Vol. 37, No. 6, pp. 651–666, November–December, 1998.     

Linear spaces and preservers of symmetric matrices of bounded rank-two

Let 𝔽 be a field of characteristic two. Let S _n (𝔽) denote the vector space of all n?×?n symmetric matrices over 𝔽. We characterize i. subspaces of S _n (𝔽) all whose elements have rank at most two where n???3,

ii. linear maps from S _m (𝔽) to S _n (𝔽) that sends matrices of rank at most two into matrices of rank at most two where m, n???3 and |𝔽|?≠?2.

     

Undirected power graphs of semigroups

The undirected power graph G(S) of a semigroup S is an undirected graph whose vertex set is S and two vertices a,b∈S are adjacent if and only if a≠b and a ^m =b or b ^m =a for some positive integer m. In this paper we characterize the class of semigroups S for which G(S) is connected or complete. As a consequence we prove that G(G) is connected for any finite group G and G(G) is complete if and only if G is a cyclic group of order 1 or p ^m . Particular attention is given to the multiplicative semigroup ℤ _n and its subgroup U _n , where G(U _n ) is a major component of G(ℤ _n ). It is proved that G(U _n ) is complete if and only if n=1,2,4,p or 2p, where p is a Fermat prime. In general, we compute the number of edges of G(G) for a finite group G and apply this result to determine the values of n for which G(U _n ) is planar. Finally we show that for any cyclic group of order greater than or equal to 3, G(G) is Hamiltonian and list some values of n for which G(U _n ) has no Hamiltonian cycle.     

On the toughness index of planar graphs

The toughness indexτ(G) of a graph G is defined to be the largest integer t such that for any S ? V(G) with |S| > t, c(G - S) < |S| - t, where c(G - S) denotes the number of components of G - S. In particular, 1-tough graphs are exactly those graphs for which τ(G) ≥ 0. In this paper, it is shown that if G is a planar graph, then τ(G) ≥ 2 if and only if G is 4-connected. This result suggests that there may be a polynomial-time algorithm for determining whether a planar graph is 1-tough, even though the problem for general graphs is NP-hard. The result can be restated as follows: a planar graph is 4-connected if and only if it remains 1-tough whenever two vertices are removed. Hence it establishes a weakened version of a conjecture, due to M. D. Plummer, that removing 2 vertices from a 4-connected planar graph yields a Hamiltonian graph.     

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.     

A Bicategorical Version of Masuoka’s Theorem

We give a bicategorical version of the main result of Masuoka (Tsukuba J Math 13:353–362, 1989) which proposes a non-commutative version of the fact that for a faithfully flat extension of commutative rings R í SR \subseteq S, the relative Picard group Pic(S/R) is isomorphic to the Amitsur 1–cohomology group H ¹(S/R,U) with coefficients in the units functor U.     

Steiner Numbers in Graphs

Abstract

The Steiner distance d(S) of a set S of vertices in a connected graph G is the minimum size of a connected subgraph of G that contains S. The Steiner number s(G) of a connected graph G of order p is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = p—1. A smallest set S of vertices of a connected graph G of order p for which d(S) = p—1 is called a Steiner spanning set of G. It is shown that every connected graph has a unique Steiner spanning set. If G is a connected graph of order p and k is an integer with 0 ≤ k ≤ p—1, then the kth Steiner number sk(G) of G is the smallest positive integer m for which there exists a set S of m vertices of G such that d(S) = k. The sequence s_o(G),s₁ (G),…,8_p-1(G) is called the Steiner sequence of G. Steiner sequences for trees are characterized.     

On a Spanning Tree with Specified Leaves

Let k ≥ 2 be an integer. We show that if G is a (k + 1)-connected graph and each pair of nonadjacent vertices in G has degree sum at least |G| + 1, then for each subset S of V(G) with |S| = k, G has a spanning tree such that S is the set of endvertices. This result generalizes Ore’s theorem which guarantees the existence of a Hamilton path connecting any two vertices. Dedicated to Professor Hikoe Enomoto on his 60th birthday.     

On the dualities between categories of k-completely regular modules

A semigroup S is called collapsing if there exists a positive integer n such that for every subset of n elements in S at least two distinct words of length n on these letters are equal in S. Let U(A) denote the group of units of an associative algebra A over an infinite field of characteristic p > 0. We show that if A is unitally generated by its nilpotent elements then the following conditions are equivalent: U(A) is collapsing; U(A) satisfies some semigroup identity; U(A) satisfies an Engel identity; A satisfies an Engel identity when viewed as a Lie algebra; and, A satisfies a Morse identity. The characteristic zero analogue of this result was proved by the author in a previous paper.     

The k-Restricted Edge Connectivity of Balanced Bipartite Graphs

For a connected graph G = (V, E), an edge set S ì E{S\subset E} is called a k-restricted edge cut if G − S is disconnected and every component of G − S contains at least k vertices. The k-restricted edge connectivity of G, denoted by λ _k (G), is defined as the cardinality of a minimum k-restricted edge cut. For two disjoint vertex sets U₁,U₂ ì V(G){U_1,U_2\subset V(G)}, denote the set of edges of G with one end in U ₁ and the other in U ₂ by [U ₁, U ₂]. Define x_k(G)=min{|[U,V(G)\ U]|: U{\xi_k(G)=\min\{|[U,V(G){\setminus} U]|: U} is a vertex subset of order k of G and the subgraph induced by U is connected}. A graph G is said to be λ _k -optimal if λ _k (G) = ξ _k (G). A graph is said to be super-λ _k if every minimum k-restricted edge cut is a set of edges incident to a certain connected subgraph of order k. In this paper, we present some degree-sum conditions for balanced bipartite graphs to be λ _k -optimal or super-λ _k . Moreover, we demonstrate that our results are best possible.     

Berezin transforms on the 2×2 matrix space related to theU(2)×U(2)-action

In this paper we establish the spectral decomposition of the Berezin transforms on the space Mat(2,) of complex 2×2 matrices related to the two-sided action ofU(2)×U(2). The eigenspaces are described explicitly by means of the matrix elements of a certain representation ofGL(2,) and each eigenvalue is expressed as a finite sum involving the MeijerG-functions evaluated at 1 and the Hahn polynomials.     

Spectra of Maximal 1-Sided Ideals and Primitive Ideals

R is any ring with identity. Let Spec _r (R) (resp. Max _r (R), Prim _r (R)) denote the set of all right prime ideals (resp. all maximal right ideals, all right primitive ideals) of R and let U _r (eR) = {P ? Spec _r (R)| e ? P}. Let  = ∪_{P?Prim r (R)} Spec _r ^P (R), where Spec _r ^P (R) = {Q ?Spec _r ^P (R)|P is the largest ideal contained in Q}. A ring is called right quasi-duo if every maximal right ideal is 2-sided. In this article, we study the properties of the weak Zariski topology on  and the relationships among various ring-theoretic properties and topological conditions on it. Then the following results are obtained for any ring R: (1) R is right quasi-duo ring if and only if  is a space with Zariski topology if and only if, for any Q ? , Q is irreducible as a right ideal in R. (2) For any clopen (i.e., closed and open) set U in ? = Max _r (R) ∪  Prim _r (R) (resp.  = Prim _r (R)) there is an element e in R with e ² ? e ? J(R) such that U = U _r (eR) ∩  ? (resp. U = U _r (eR) ∩  ), where J(R) is the Jacobson of R. (3) Max _r (R) ∪  Prim _r (R) is connected if and only if Max _l (R) ∪  Prim _l (R) is connected if and only if Prim _r (R) is connected.     

Properties of Subtree-Prune-and-Regraft Operations on Totally-Ordered Phylogenetic Trees

We study some properties of subtree-prune-and-regraft (SPR) operations on leaflabelled rooted binary trees in which internal vertices are totally ordered. Since biological events occur with certain time ordering, sometimes such totally-ordered trees must be used to avoid possible contradictions in representing evolutionary histories of biological sequences. Compared to the case of plain leaf-labelled rooted binary trees where internal vertices are only partially ordered, SPR operations on totally-ordered trees are more constrained and therefore more difficult to study. In this paper, we investigate the unit-neighbourhood U(T), defined as the set of totally-ordered trees one SPR operation away from a given totally-ordered tree T. We construct a recursion relation for | U(T) | and thereby arrive at an efficient method of determining | U(T) |. In contrast to the case of plain rooted trees, where the unit-neighbourhood size grows quadratically with respect to the number n of leaves, for totally-ordered trees | U(T) | grows like O(n³). For some special topology types, we are able to obtain simple closed-form formulae for | U(T) |. Using these results, we find a sharp upper bound on | U(T) | and conjecture a formula for a sharp lower bound. Lastly, we study the diameter of the space of totally-ordered trees measured using the induced SPR-metric. Received May 18, 2004