An edge version of the matrix-tree theorem and the wiener index

Let T be a tree on n vertices. The Laplacian matrix is L(T)=D(T)-A(T), where D(T) is the diagonal matrix of vertex degrees and A(T) is the adjacency matrix. A special case of the Matrix-Tree Theorem is that the adjugate of L(T) is the n-by-n matrix of l's. The (n-l)-square "edge version" of L(T)is K(T). The main result is a graph-theoretic interpretation of the entries of the adjugate of K(T). As an application, it is shown that the Wiener Index from chemistry is the trace of this adjugate.     

Maximal orders containing local crossed-products

Let Λ = (S/R, ) be the crossed product order in the crossed product algebra A = (L/K, ) with factor set , where L/K is a Galois extension of the local field K, and R (resp. S) the valuation ring of K (resp. L). In this paper the maximal R-orders in A containing Λ and the irreducible Λ-lattices are determined.     

The homotopy Lie algebra of classifying spaces

Let X be a 1-connected CW-complex of finite type and L_x its rational homotopy Lie algebra. In this work, we show that there is a spectral sequence whose E² term is the Lie algebra Ext_ULx(Q, L_x), and which converges to the homotopy Lie algebra of the classifying space B autX. Moreover, some terms of this spectral sequence are related to derivations of L_x and to the Gottlieb group of X.     

On the minimal reducible bound for outerplanar and planar graphs

Let L be the set of all additive and hereditary properties of graphs. For P₁, P₂ L we define the reducible property R = P₁ P₂ as follows: G P₁P₂ if there is a bipartition (V₁, V₂) of V(G) such that V₁ P₁ and V₂ P₂. For a property P L, a reducible property R is called a minimal reducible bound for P if P R and for each reducible property R′, R′ R → P R′. It is proved that the class of all outerplanar graphs has exactly two minimal reducible bounds in L. Some related problems for planar graphs are discussed.     

Linear transformations on matrices: The invariance of commuting pairs of matrices

Let L be a linear transformation on the set of all n×n matrices over an algebraically closed field of characteristic 0. It is shown that if AB=BA implies L(A)L(B)=L(B)L(A) and if either L is nonsingular or the implication in the hypothesis can also be reversed, then L is a sum of a scalar multiple of a similarity transformation and a linear functional times the identity transformation.     

Linear mappings which are rank-k nonincreasing, II

We prove the following result. Let F be an infinite field of characteristic other than two. Let k be a positive integer. Let S_n(F) denote the space of all n × n symmetric matrices with entries in F, and let T:S_n(F)→S_n(F) be a linear operator. Suppose that T is rank-k nonincreasing and its image contains a matrix with rank higher than K. Then, there exist λεF and PεF^n,n such that T(A)=λPAP^t for all AεS_n(F). λ can be chosen to be 1 if F is algebraically closed and ±1 if F=R, the real field.     

Chapter 4:algebraic sets, polynomials, and other functions

Let T be a linear operator on the vector space V ofn×n matrices over a field F. We discuss two types of problems in this chapter. First, what can we say about T if we assume that T maps a given algebraic set such as the special linear group into itself? Second, let p(x) be a polynomial function (such as det) on V into F. What can we say about T if Tpreserves p(x), i.e. p(T(X)) = p(X) for all X in V?     

Vectors with a prescribed minimal polynomial

Let V be a finite dimensional vector space over the field Fand φ (x)∈F[x].LetxV → V be a linear operator. Let S_φbe the set consisting of the vectors whose minimal polynomial φ(x)together with the zero vector We give necessary and sufficieni condition for S _φ to be a subspace.     

Additive Maps Preserving Nilpotent Perturbation of Scalars

Let X be a Banach space over F(= R or C) with dimension greater than 2. Let N(X) be the set of all nilpotent operators and B_0(X) the set spanned by N(X). We give a structure result to the additive maps on FI + B_0(X) that preserve rank-1 perturbation of scalars in both directions. Based on it, a characterization of surjective additive maps on FI + B_0(X) that preserve nilpotent perturbation of scalars in both directions are obtained. Such a map Φ has the form either Φ(T) = cAT A~(-1)+ φ(T)I for all T ∈ FI + B_0(X) or Φ(T) = cAT*A~(-1)+ φ(T)I for all T ∈ FI + B_0(X), where c is a nonzero scalar,A is a τ-linear bijective transformation for some automorphism τ of F and φ is an additive functional.In addition, if dim X = ∞, then A is in fact a linear or conjugate linear invertible bounded operator.     

Linear transformations on tensor spaces

Let U⊗V denote the tensor product of two finite dimensional vector spaces U and V over an infinite field. Let k be a positive integer such that k≤dim U and k≤ dim V Let D_k denote the set of all non-zero elements of U⊗V of rank less than k. In this paper we study linear transformations T on U⊗V such that (TD_k)⊆D_k.     

Linear preservers of matrices of rank-2

Let T be a linear operator on the space of all m×n matrices over any field. we prove that if T maps rank-2 matrices to rank-2 matrices then there exist nonsingular matrices U and V such that either T(X)=UXV for all matrices X, or m=n and T(X)=UX^tV for all matrices X where X^t denotes the transpose of X.     

Linear transformations on symmetric matrices II

Let Tbe a linear mapping on the space of n× nsymmetric matrices over a field Fof characteristic not equal to two. We obtain the structure of Tfor the following cases:(i) Tpreserves matrices of rank less than three; (ii) Tpreserves nonzero matrices of rank less than K + 1 where Kis a fixed positive integer less than nand Fis algebraically closed; (iii) Tpreserves rank Kmatrices where Kis a fixed odd integer and Fis algebraically closed.     

Polynomials in a matrix

Let A be a matrixp(x) a polynomial. Put B=p(A). It is shown that necessary and sufficient conditions for A to be a polynomial in B are (i) if λ is any eigenvalue of A, and if some elementary divisor of A corresponding to λ is nonlinear, thenp^'(λ)≠0;and (ii) if λ,μ are distinct eigenvalues of A, then p(λ)p(μ) are also distinct. Here all computations are over some algebraically closed field.     

Algorithmic complexity of list colorings

Given a graph G = (V,E) and a finite set L(v) at each vertex v ε V, the List Coloring problem asks whether there exists a function f:V → _vεVL(V) such that (i) f(v)εL(v) for each vεV and (ii) f(u) ≠f(v) whenever u, vεV and uvεE. One of our results states that this decision problem remains NP-complete even if all of the followingconditions are met: (1) each set L(v) has at most three elements, (2) each “color” xε_vεVL(v) occurs in at most three sets L(v), (3) each vertex vεV has degree at most three, and (4) G is a planar graph. On the other hand, strengthening any of the assumptions (1)–(3) yields a polynomially solvable problem. The connection between List Coloring and Boolean Satisfiability is discussed, too.     

Choosability of planar graphs

A graph G = G(V, E) with lists L(v), associated with its vertices v V, is called L-list colourable if there is a proper vertex colouring of G in which the colour assigned to a vertex v is chosen from L(v). We say G is k-choosable if there is at least one L-list colouring for every possible list assignment L with L(v) = k v V(G).

Now, let an arbitrary vertex v of G be coloured with an arbitrary colour f of L(v). We investigate whether the colouring of v can be continued to an L-list colouring of the whole graph. G is called free k-choosable if such an L-list colouring exists for every list assignment L (L(v) = k v V(G)), every vertex v and every colour f L(v). We prove the equivalence of the well-known conjecture of Erd s et al. (1979): “Every planar graph is 5-choosable” with the following conjecture: “Every planar graph is free 5-choosable”.     

Bandwidth of the composition of two graphs

The bandwidth B(G) of a graph G is the minimum of the quantity max{|f(x)−f(y)| : xyE(G)} taken over all proper numberings f of G. The composition of two graphs G and H, written as G[H], is the graph with vertex set V(G)×V(H) and with (u₁,v₁) is adjacent to (u₂,v₂) if either u₁ is adjacent to u₂ in G or u₁=u₂ and v₁ is adjacent to v₂ in H. In this paper, we investigate the bandwidth of the composition of two graphs. Let G be a connected graph. We denote the diameter of G by D(G). For two distinct vertices x,yV(G), we define w_G(x,y) as the maximum number of internally vertex-disjoint (x,y)-paths whose lengths are the distance between x and y. We define w(G) as the minimum of w_G(x,y) over all pairs of vertices x,y of G with the distance between x and y is equal to D(G). Let G be a non-complete connected graph and let H be any graph. Among other results, we prove that if |V(G)|=B(G)D(G)−w(G)+2, then B(G[H])=(B(G)+1)|V(H)|−1. Moreover, we show that this result determines the bandwidth of the composition of some classes of graphs composed with any graph.     

Convexoid and generalized derivations

Let E,F be two Banach spaces and let S be a symmetric norm ideal of L(E,F). For AL(F) and BL(E) the generalized derivation δ_S,A,B is the operator on S that sends X to AX−XB. A bounded linear operator is said to be convexoid if its (algebraic) numerical range coincides with the convex hull of its spectrum. We show that δ_S,A,B is convexoid if and only if A and B are convexoid.     

Hopf Algebras on Schurian Quivers

Let H be a Hopf algebra with a finite-dimensional, nontrivial space of skew primitive elements, over an algebraically closed field of characteristic zero. We prove that H contains either the polynomial algebra as a Hopf subalgebra, or a certain Schurian simple-pointed Hopf subalgebra. As a consequence, a complete list of the locally finite, simple-pointed Hopf algebras is obtained. Also, the graded automorphism group of a Hopf algebra on a Schurian Hopf quiver is determined, and the relation between this group and the automorphism groups of the corresponding Hopf quiver, is clarified.     

Ramsey linear families and generalized subdivided graphs

The following results are obtained. (i) Let p, d, and k be fixed positive integers, and let G be a graph whose vertex set can be partitioned into parts V₁, V₂,…, V_a such that for each i at most d vertices in V₁ … V_i have neighbors in V_i+1 and r(K_k, V_i) p | V(G) |, where V_i denotes the subgraph of G induced by V_i. Then there exists a number c depending only on p, d, and k such that r(K_k, G)c | V(G) |. (ii) Let d be a positive integer and let G be a graph in which there is an independent set I V(G) such that each component of G−I has at most d vertices and at most two neighbors in I. Then r(G,G)c | V(G) |, where c is a number depending only on d. As a special case, r(G, G) 6 | V(G) | for a graph G in which all vertices of degree at least three are independent. The constant 6 cannot be replaced by one less than 4.     

An isomorphism criterion for modules over a principal ideal domain

Let U and V be modules of finite composition length over a principal ideal domain D. Then, denoting the composition length of the D-module Horn (U,V) by 〈U,V〉, it is shown that 〈U,V〉²≤〈U,U〉〈V,V〉 and that equality holds iff U and V are isomorphic to direct sums of copies of some common module. This gives an isomorphism criterion for U and V based entirely on composition lengths. As a special case, the theorem gives a strong version of a criterion of M. A. Gauger and C. 1. Byrnes for the similarity of two matrices.