Steiner intervals and Steiner geodetic numbers in distance-hereditary graphs

A Steiner tree for a set S of vertices in a connected graph G is a connected subgraph of G with a smallest number of edges that contains S. The Steiner interval I(S) of S is the union of all the vertices of G that belong to some Steiner tree for S. If S={u,v}, then I(S)=I[u,v] is called the interval between u and v and consists of all vertices that lie on some shortest u-v path in G. The smallest cardinality of a set S of vertices such that ?_u,v∈SI[u,v]=V(G) is called the geodetic number and is denoted by g(G). The smallest cardinality of a set S of vertices of G such that I(S)=V(G) is called the Steiner geodetic number of G and is denoted by sg(G). We show that for distance-hereditary graphs g(G)?sg(G) but that g(G)/sg(G) can be arbitrarily large if G is not distance hereditary. An efficient algorithm for finding the Steiner interval for a set of vertices in a distance-hereditary graph is described and it is shown how contour vertices can be used in developing an efficient algorithm for finding the Steiner geodetic number of a distance-hereditary graph.     

The relaxed game chromatic index of k-degenerate graphs

The (r,d)-relaxed coloring game is a two-player game played on the vertex set of a graph G. We consider a natural analogue to this game on the edge set of G called the (r,d)-relaxed edge-coloring game. We consider this game on trees and more generally, on k-degenerate graphs. We show that if G is k-degenerate with Δ(G)=Δ, then the first player, Alice, has a winning strategy for this game with r=Δ+k-1 and d?2k²+4k.     

On equality in an upper bound for the restrained and total domination numbers of a graph

Let G=(V,E) be a graph. A set S⊆V is a restrained dominating set (RDS) if every vertex not in S is adjacent to a vertex in S and to a vertex in V?S. The restrained domination number of G, denoted by γ_r(G), is the minimum cardinality of an RDS of G. A set S⊆V is a total dominating set (TDS) if every vertex in V is adjacent to a vertex in S. The total domination number of a graph G without isolated vertices, denoted by γ_t(G), is the minimum cardinality of a TDS of G.Let δ and Δ denote the minimum and maximum degrees, respectively, in G. If G is a graph of order n with δ?2, then it is shown that γ_r(G)?n-Δ, and we characterize the connected graphs with δ?2 achieving this bound that have no 3-cycle as well as those connected graphs with δ?2 that have neither a 3-cycle nor a 5-cycle. Cockayne et al. [Total domination in graphs, Networks 10 (1980) 211-219] showed that if G is a connected graph of order n?3 and Δ?n-2, then γ_t(G)?n-Δ. We further characterize the connected graphs G of order n?3 with Δ?n-2 that have no 3-cycle and achieve γ_t(G)=n-Δ.     

The cleanness of (symbolic) powers of Stanley-Reisner ideals

Let Δ be a pure simplicial complex on the vertex set [n] = {1,..., n} and I _Δ its Stanley-Reisner ideal in the polynomial ring S = K[x ₁,..., x _n]. We show that Δ is a matroid (complete intersection) if and only if S/I _Δ ^(m) (S/I _Δ ^(m)) is clean for all m ∈ N and this is equivalent to saying that S/I _Δ ^(m) (S/I _Δ ^(m), respectively) is Cohen-Macaulay for all m ∈ N. By this result, we show that there exists a monomial ideal I with (pretty) cleanness property while S/I ^m or S/I ^m is not (pretty) clean for all integer m ≥ 3. If dim(Δ) = 1, we also prove that S/I _Δ ⁽²⁾ Δ (S/I _Δ ²) is clean if and only if S/I _Δ ⁽²⁾ (S/I _Δ ², respectively) is Cohen-Macaulay.     

A class of (4,2)-disk pairs which are trivial

Suppose Δ?S³ is a ribbon disk and let D (Δ) denote the cononical properly embedded 2-disk obtained by pushing the interior of Δ into B⁴. A well-known conjecture states that the disk pair (B⁴, D(Δ)) is trivial provided the sphere pair ?(B⁴, D(Δ)) is trivial. We show here that the conjecture is true for those D(Δ) with the property that there is an embedded 2-disk, D²?S³, whose boundary is ?D(Δ) and which intersects Δ in ‘transverse double points’.     

Integral Schur algebras forGL 2

The structure of Schur algebrasS(2,r) over the integral domainZ is intensively studied from the quasi-hereditary algebra point of view. We introduce certain new bases forS(2,r) and show that the Schur algebraS(2,r) modulo any ideal in the defining sequence is still such a Schur algebra of lower degree inr. A Wedderburn-Artin decomposition ofS _K (2,r) over a fieldK of characteristic 0 is described. Finally, we investigate the extension groups between two Weyl modules and classify the indecomposable Weyl-filtered modules for the Schur algebrasS _Zp(2,r) withr<p ² . Research supported by ARC Large Grant L20.24210     

Embedding infinite cyclic covers of knot spaces into 3-space

We say a knot k in the 3-sphere S³ has PropertyIE if the infinite cyclic cover of the knot exterior embeds into S³. Clearly all fibred knots have Property IE.There are infinitely many non-fibred knots with Property IE and infinitely many non-fibred knots without property IE. Both kinds of examples are established here for the first time. Indeed we show that if a genus 1 non-fibred knot has Property IE, then its Alexander polynomial Δ_k(t) must be either 1 or 2t²−5t+2, and we give two infinite families of non-fibred genus 1 knots with Property IE and having Δ_k(t)=1 and 2t²−5t+2 respectively.Hence among genus 1 non-fibred knots, no alternating knot has Property IE, and there is only one knot with Property IE up to ten crossings.We also give an obstruction to embedding infinite cyclic covers of a compact 3-manifold into any compact 3-manifold.     

Geodetic and Steiner geodetic sets in 3-Steiner distance hereditary graphs

Let G be a connected graph and S⊆V(G). Then the Steiner distance of S, denoted by d_G(S), is the smallest number of edges in a connected subgraph of G containing S. Such a subgraph is necessarily a tree called a Steiner tree for S. The Steiner interval for a set S of vertices in a graph, denoted by I(S) is the union of all vertices that belong to some Steiner tree for S. If S={u,v}, then I(S) is the interval I[u,v] between u and v. A connected graph G is 3-Steiner distance hereditary (3-SDH) if, for every connected induced subgraph H of order at least 3 and every set S of three vertices of H, d_H(S)=d_G(S). The eccentricity of a vertex v in a connected graph G is defined as e(v)=max{d(v,x)|x∈V(G)}. A vertex v in a graph G is a contour vertex if for every vertex u adjacent with v, e(u)?e(v). The closure of a set S of vertices, denoted by I[S], is defined to be the union of intervals between pairs of vertices of S taken over all pairs of vertices in S. A set of vertices of a graph G is a geodetic set if its closure is the vertex set of G. The smallest cardinality of a geodetic set of G is called the geodetic number of G and is denoted by g(G). A set S of vertices of a connected graph G is a Steiner geodetic set for G if I(S)=V(G). The smallest cardinality of a Steiner geodetic set of G is called the Steiner geodetic number of G and is denoted by sg(G). We show that the contour vertices of 3-SDH and HHD-free graphs are geodetic sets. For 3-SDH graphs we also show that g(G)?sg(G). An efficient algorithm for finding Steiner intervals in 3-SDH graphs is developed.     

Tychonoff expansions with prescribed resolvability properties

The recent literature offers examples, specific and hand-crafted, of Tychonoff spaces (in ZFC) which respond negatively to these questions, due respectively to Ceder and Pearson (1967) [3] and to Comfort and García-Ferreira (2001) [5]: (1) Is every ω-resolvable space maximally resolvable? (2) Is every maximally resolvable space extraresolvable? Now using the method of KID expansion, the authors show that every suitably restricted Tychonoff topological space (X,T) admits a larger Tychonoff topology (that is, an “expansion”) witnessing such failure. Specifically the authors show in ZFC that if (X,T) is a maximally resolvable Tychonoff space with S(X,T)?Δ(X,T)=κ, then (X,T) has Tychonoff expansions U=Ui (1?i?5), with Δ(X,Ui)=Δ(X,T) and S(X,Ui)?Δ(X,Ui), such that (X,Ui) is: (i=1) ω-resolvable but not maximally resolvable; (i=2) [if κ^′ is regular, with S(X,T)?κ^′?κ] τ-resolvable for all τ<κ^′, but not κ^′-resolvable; (i=3) maximally resolvable, but not extraresolvable; (i=4) extraresolvable, but not maximally resolvable; (i=5) maximally resolvable and extraresolvable, but not strongly extraresolvable.     

On the roots of independence polynomials of almost all very well-covered graphs

If s_k denotes the number of stable sets of cardinality k in graph G, and α(G) is the size of a maximum stable set, then is the independence polynomial of G [I. Gutman, F. Harary, Generalizations of the matching polynomial, Utilitas Math. 24 (1983) 97-106]. A graph G is very well-covered [O. Favaron, Very well-covered graphs, Discrete Math. 42 (1982) 177-187] if it has no isolated vertices, its order equals 2α(G) and it is well-covered, i.e., all its maximal independent sets are of the same size [M.D. Plummer, Some covering concepts in graphs, J. Combin. Theory 8 (1970) 91-98]. For instance, appending a single pendant edge to each vertex of G yields a very well-covered graph, which we denote by G^*. Under certain conditions, any well-covered graph equals G^* for some G [A. Finbow, B. Hartnell, R.J. Nowakowski, A characterization of well-covered graphs of girth 5 or greater, J. Combin. Theory Ser B 57 (1993) 44-68].The root of the smallest modulus of the independence polynomial of any graph is real [J.I. Brown, K. Dilcher, R.J. Nowakowski, Roots of independence polynomials of well-covered graphs, J. Algebraic Combin. 11 (2000) 197-210]. The location of the roots of the independence polynomial in the complex plane, and the multiplicity of the root of the smallest modulus are investigated in a number of articles.In this paper we establish formulae connecting the coefficients of I(G;x) and I(G^*;x), which allow us to show that the number of roots of I(G;x) is equal to the number of roots of I(G^*;x) different from -1, which appears as a root of multiplicity α(G^*)-α(G) for I(G^*;x). We also prove that the real roots of I(G^*;x) are in [-1,-1/2α(G^*)), while for a general graph of order n we show that its roots lie in |z|>1/(2n-1).Hoede and Li [Clique polynomials and independent set polynomials of graphs, Discrete Math. 125 (1994) 219-228] posed the problem of finding graphs that can be uniquely defined by their clique polynomials (clique-unique graphs). Stevanovic [Clique polynomials of threshold graphs, Univ. Beograd Publ. Elektrotehn. Fac., Ser. Mat. 8 (1997) 84-87] proved that threshold graphs are clique-unique. Here, we demonstrate that the independence polynomial distinguishes well-covered spiders among well-covered trees.     

A semialgebraic closure for commutative algebra

Let A⊂R be rings containing the rationals. In R let S be a multiplicatively closed subset such that 1∈S and 0∉S, T a preorder of R (a proper subsemiring containing the squares) such that S⊂T and I an A-submodule of R. Define ρ(I) (or ρ_S,T(I)) to be

ρ(I)={a∈R|sa^2m+t∈I^2m for some m∈N,s∈S and t∈T}.     

The product of operators with closed range in Hilbert C-modules

Suppose T and S are bounded adjointable operators with close range between Hilbert C^∗-modules, then TS has closed range if and only if Ker(T)+Ran(S) is an orthogonal summand, if and only if Ker(S^∗)+Ran(T^∗) is an orthogonal summand. Moreover, if the Dixmier (or minimal) angle between Ran(S) and Ker(T)∩[Ker(T)∩Ran(S)]^⊥ is positive and is an orthogonal summand then TS has closed range.     

Holomorphic extensions of Laplacians and their determinants

The Teichmüller space Teich(S) of a surface S in genus g>1 is a totally real submanifold of the quasifuchsian space QF(S). We show that the determinant of the Laplacian det^′(Δ) on Teich(S) has a unique holomorphic extension to QF(S). To realize this holomorphic extension as the determinant of differential operators on S, we introduce a holomorphic family {Δμ,ν} of elliptic second order differential operators on S whose parameter space is the space of pairs of Beltrami differentials on S and which naturally extends the Laplace operators of hyperbolic metrics on S. We study the determinant of this family {Δμ,ν} and show how this family realizes the holomorphic extension of det^′(Δ) as its determinant.     

Submodule categories of wild representation type

Let Λ be a commutative local uniserial ring with radical factor field k. We consider the category S(Λ) of embeddings of all possible submodules of finitely generated Λ-modules. In case Λ=Z/〈pⁿ〉, where p is a prime, the problem of classifying the objects in S(Λ), up to isomorphism, has been posed by Garrett Birkhoff in 1934. In this paper we assume that Λ has Loewy length at least seven. We show that S(Λ) is controlled k-wild with a single control object I∈S(Λ). It follows that each finite dimensional k-algebra can be realized as a quotient End(X)/End(X)_I of the endomorphism ring of some object X∈S(Λ) modulo the ideal End(X)_I of all maps which factor through a finite direct sum of copies of I.     

On the generating graph of direct powers of a simple group

Let S be a nonabelian finite simple group and let n be an integer such that the direct product S ⁿ is 2-generated. Let Γ(S ⁿ ) be the generating graph of S ⁿ and let Γ _n (S) be the graph obtained from Γ(S ⁿ ) by removing all isolated vertices. A recent result of Crestani and Lucchini states that Γ _n (S) is connected, and in this note we investigate its diameter. A deep theorem of Breuer, Guralnick and Kantor implies that diam(Γ ₁(S))=2, and we define Δ(S) to be the maximal n such that diam(Γ _n (S))=2. We prove that Δ(S)≥2 for all S, which is best possible since Δ(A ₅)=2, and we show that Δ(S) tends to infinity as |S| tends to infinity. Explicit upper and lower bounds are established for direct powers of alternating groups.     

On the existence of an invariant non-degenerate bilinear form under a linear map

Let V be a vector space over a field F. Assume that the characteristic of F is large, i.e. char(F)>dimV. Let T:V→V be an invertible linear map. We answer the following question in this paper. When doesVadmit a T-invariant non-degenerate symmetric (resp. skew-symmetric) bilinear form? We also answer the infinitesimal version of this question.Following Feit and Zuckerman 2, an element g in a group G is called real if it is conjugate in G to its own inverse. So it is important to characterize real elements in GL(V,F). As a consequence of the answers to the above question, we offer a characterization of the real elements in GL(V,F).Suppose V is equipped with a non-degenerate symmetric (resp. skew-symmetric) bilinear form B. Let S be an element in the isometry group I(V,B). A non-degenerate S-invariant subspace W of (V,B) is called orthogonally indecomposable with respect to S if it is not an orthogonal sum of proper S-invariant subspaces. We classify the orthogonally indecomposable subspaces. This problem is non-trivial for the unipotent elements in I(V,B). The level of a unipotent T is the least integer k such that (T-I)^k=0. We also classify the levels of unipotents in I(V,B).     

The bitwisted Cartesian model for the free loop fibration

Using the notion of truncating twisting function from a simplicial set to a cubical set a special, bitwisted, Cartesian product of these sets is defined. For the universal truncating twisting function, the (co)chain complex of the corresponding bitwisted Cartesian product agrees with the standard Cartier (Hochschild) chain complex of the simplicial (co)chains. The modelling polytopes Fn are constructed. An explicit diagonal on Fn is defined and a multiplicative model for the free loop fibration ΩY→ΛY→Y is obtained. As an application we establish an algebra isomorphism H^∗(ΛY;Z)≈S(U)⊗Λ(s−1U) for the polynomial cohomology algebra H^∗(Y;Z)=S(U).     

The singular locus of the secant varieties of a smooth projective curve

Let X be a smooth irreducible non-degenerated projective curve in some projective space P^N. Let r be a positive integer such that 2r + 1 < N and let S_r(X) be the r-th secant variety of X. It is a variety of dimension 2r + 1. In this paper we prove that the singular locus is the (r - 1)-th secant variety S_{r- 1}(X) if X does not have any (2r + 2)-secant 2r-space divisor. Received: 26 November 2002     

The eccentric connectivity index of nanotubes and nanotori

Let G be a molecular graph. The eccentric connectivity index ξ^c(G) is defined as ξ^c(G)=∑_u∈V(G)deg_G(u)ε_G(u), where deg_G(u) denotes the degree of vertex u and ε_G(u) is the largest distance between u and any other vertex v of G. In this paper exact formulas for the eccentric connectivity index of TUC₄C₈(S) nanotube and TC₄C₈(S) nanotorus are given.     

New upper bounds on the spectral radius of unicyclic graphs

Let G=(V(G),E(G)) be a unicyclic simple undirected graph with largest vertex degree Δ. Let C_r be the unique cycle of G. The graph G-E(C_r) is a forest of r rooted trees T₁,T₂,…,T_r with root vertices v₁,v₂,…,v_r, respectively. Let