Graphs whose acyclic graphoidal covering number is one less than its maximum degree

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. In this paper we characterize the class of graphs G for which η_a=Δ−1 where Δ is the maximum degree of a vertex in G.     

ContributionsAcyclic graphoidal covers and path partitions in a graph

An acyclic graphoidal cover of a graph G is a collection ψ of paths in G such that every path in ψ has at least two vertices, every vertex of G is an internal vertex of at most one path in ψ and every edge of G is in exactly one path in ψ. The minimum cardinality of an acyclic graphoidal cover of G is called the acyclic graphoidal covering number of G and is denoted by η_a. A path partition of a graph G is a collection P of paths in G such that every edge of G is in exactly one path in P. The minimum cardinality of a path partition of G is called the path partition number of G and is denoted by π. In this paper we determine η_a and π for several classes of graphs and obtain a characterization of all graphs with Δ 4 and η_a = Δ − 1. We also obtain a characterization of all graphs for which η_a = π.     

Reconstruction of infinite locally finite connected graphs

Let G be an infinite locally finite connected graph. We study the reconstructibility of G in relation to the structure of its end set . We prove that an infinite locally finite connected graph G is reconstructible if there exists a finite family (Ω_i)_0i (n2) of pairwise finitely separable subsets of such that, for all x,y,x′,y′V(G) and every isomorphism f of G−{x,y} onto G−{x′,y′} there is a permutation π of {0,…,n−1} such that for 0i<n. From this theorem we deduce, as particular consequences, that G is reconstructible if it satisfies one of the following properties: (i) G contains no end-respecting subdivision of the dyadic tree and has at least two ends of maximal order; (ii) the set of thick ends or the one of thin ends of G is finite and of cardinality greater than one. We also prove that if almost all vertices of G are cutvertices, then G is reconstructible if it contains a free end or if it has at least a vertex which is not a cutvertex.     

A combinatorial decomposition of simplicial complexes

We find a decomposition of simplicial complexes that implies and sharpens the characterization (due to Björner and Kalai) of thef-vector and Betti numbers of a simplicial complex. It generalizes a result of Stanley, who proved the acyclic case, and settles a conjecture of Stanley and Kalai.     

Existence results for doubly near resolvable (υ, 3, 2)-BIBDs

Let V be a set of υ elements. A (1, 2; 3, υ, 1)-frame F is a square array of side v which satisfies the following properties. We index the rows and columns of F with the elements of V, V={x₁,x₂,…,x_υ}. (1) Each cell is either empty or contains a 3-subset of V. (2) Cell (x_i, x_i) is empty for i=1, 2,…, υ. (3) Row x_i of F contains each element of V−{x_i} once and column x_i of F contains each element of V−{x_i} once. (4) The collection of blocks obtained from the nonempty cells of F is a (υ, 3, 2)-BIBD. A (1, 2; 3, υ, 1)-frame is a doubly near resolvable (υ, 3, 2)-BIBD. In this paper, we first present a survey of existence results on doubly near resolvable (υ, 3, 2)-BIBDs and (1, 2; 3, υ, 1)-frames. We then use frame constructions to provide a new infinite class of doubly near resolvable (υ, 3, 2)-BIBDs by constructing (1, 2; 3, υ, 1)-frames.     

Resolutions of Stanley-Reisner rings and Alexander duality

Associated to any simplicial complex Δ on n vertices is a square-free monomial ideal I_Δ in the polynomial ring A = k[x₁, …, x_n], and its quotient k[Δ] = A/I_Δ known as the Stanley-Reisner ring. This note considers a simplicial complex Δ^* which is in a sense a canonical Alexander dual to Δ, previously considered in [1, 5]. Using Alexander duality and a result of Hochster computing the Betti numbers dim_k Tor_i^A (k[Δ],k), it is shown (Proposition 1) that these Betti numbers are computable from the homology of links of faces in Δ^*. As corollaries, we prove that I_Δ has a linear resolution as A-module if and only if Δ^* is Cohen-Macaulay over k, and show how to compute the Betti numbers dim_k Tor_i^A (k[Δ],k) in some cases where Δ^* is wellbehaved (shellable, Cohen-Macaulay, or Buchsbaum). Some other applications of the notion of shellability are also discussed.     

Optimal fault-tolerant routings with small routing tables for k-connected graphs

We study the problem of designing fault-tolerant routings with small routing tables for a k-connected network of n processors in the surviving route graph model. The surviving route graph R(G,ρ)/F for a graph G, a routing ρ and a set of faults F is a directed graph consisting of nonfaulty nodes of G with a directed edge from a node x to a node y iff there are no faults on the route from x to y. The diameter of the surviving route graph could be one of the fault-tolerance measures for the graph G and the routing ρ and it is denoted by D(R(G,ρ)/F). We want to reduce the total number of routes defined in the routing, and the maximum of the number of routes defined for a node (called route degree) as least as possible. In this paper, we show that we can construct a routing λ for every n-node k-connected graph such that n2k², in which the route degree is , the total number of routes is O(k²n) and D(R(G,λ)/F)3 for any fault set F (|F|<k). In particular, in the case that k=2 we can construct a routing λ′ for every biconnected graph in which the route degree is , the total number of routes is O(n) and D(R(G,λ′)/{f})3 for any fault f. We also show that we can construct a routing ρ₁ for every n-node biconnected graph, in which the total number of routes is O(n) and D(R(G,ρ₁)/{f})2 for any fault f, and a routing ρ₂ (using ρ₁) for every n-node biconnected graph, in which the route degree is , the total number of routes is and D(R(G,ρ₂)/{f})2 for any fault f.     

Complete-factors and f-factors

A factor F of a graph is called a complete-factor if each component of F is complete. Let G be a graph, F be a complete-factor of G with ω(F)2, and f be an integer-valued function defined on V(G) with ∑_xV(G)f(x) even. If G−V(C) has an f-factor for each component C of F, then G has an f-factor.     

Extending shelling orders and a hierarchy of functions of unimodal simple polytopes

Let P be a simplicial d-polytope with n facets ((d − 1)-dimensional faces) in R^d. A shelling of P is an ordering of the facets of P such that the intersection of each facet F with the union of all facets that precede it the ordering is a nonempty union of (d − 2)-faces of F. The following open question was raised by Tverberg and is recorded in [4]. Suppose for some k < n, there is an ordering of k of the facets of P so that the intersection of each of these facets with the union of all of the facets that precede it in the ordering is a nonempty union of (d − 2)-faces. Can this initial “segment” be extended to a shelling of all the facets? This question is open even in the case that P is the dual of the d-dimensional hypercube. The question in this case has resurfaced several times since G. Danaraj and V. Klee (1978) in a variety of forms. It is related to the hierarchies of completely unimodal pseudo-Boolean functions studied in P.L. Hammer et al. (1988), the author (1988) and D. Wiedemann (1986). (A pseudo-Boolean function is a function mapping the vertices of the d-dimensional hypercube into the reals). In this paper, the hierarchies are compared and combined. This hierarchy is then extended to general simple polytopes, and the relationship to the above open question is explained.     

Valuations defined by Ostrowski nets

Ostrowski proved that if v is a valuation on an algebraically closed field F and if w is a valuation extending v to the field F (x) of rational functions over F, then w is defined by a transcendental pseudo-convergent net (that is, an Ostrowski net) or w is a Rella extension of v centered about x − c for some c in F. In this paper, valuations on the field of rational functions over an arbitrary field determined by Ostrowski nets, along with the topologies they generate, are investigated.     

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.     

Oscillation theorems for second-order half-linear differential equations

Oscillation criteria for the second-order half-linear differential equation

[r(t)|ξ′(t)|⁻¹ ξ′(t)]′ + p(t)|ξ(t)|⁻¹ξ(t)=0, t t₀

are established, where > 0 is a constant and exists for t [t₀, ∞). We apply these results to the following equation:

where , D = (D₁,…, D_N), Ω_a = x ^N : |x| ≥ a} is an exterior domain, and c C([a, ∞), ), n > 1 and N ≥ 2 are integers. Here, a > 0 is a given constant.     

The complexity of irredundant sets parameterized by size

An irredundant set of vertices V′V in a graph G=(V,E) has the property that for every vertex uV′, N[V′−{u}] is a proper subset of N[V′]. We investigate the parameterized complexity of determining whether a graph has an irredundant set of size k, where k is the parameter. The interest of this problem is that while most “k-element vertex set” problems are NP-complete, several are known to be fixed-parameter tractable, and others are hard for various levels of the parameterized complexity hierarchy. Complexity classification of vertex set problems in this framework has proved to be both more interesting and more difficult. We prove that the k-element irredundant set problem is complete for W[1], and thus has the same parameterized complexity as the problem of determining whether a graph has a k-clique. We also show that the “parametric dual” problem of determining whether a graph has an irredundant set of size n−k is fixed-parameter tractable.     

Some algebraic constructions in rational homotopy theory

In this note we describe constructions in the category of differential graded commutative algebras over the rational numbers Q which are analogs of the space F(X, Y) of continuous maps of X to Y, the component F(X, Y,ƒ) containing ƒ ε F(X, Y), fibrations, induced fibrations, the space Γ(π) of sections of a fibration π: E → X, and the component Γ(π,σ) containing σ ε Γ (π). As a focus, we address the problem of expressing π^*(F(X, Y, ƒ)) = Hom(π_*(F(X,Y, ƒ)),Q) in terms of differential graded algebra models for X and Y.     

The W-convexity and normal structure in banach spaces

Let X be a Banach space, S(X) - x ε X : #x02016; = 1 be the unit sphere of X.The parameter, modulus of W^*-convexity, W^*(ε) = inf <(x − y)/2, f_x> : x, y S(X), x − y ≥ ε, f_x Δ_x , where 0 ≤ ε ≤ 2 and Δ_x S(X^*) be the set of norm 1 supporting functionals of S(X) at x, is investigated_ The relationship among uniform nonsquareness, uniform normal structure and the parameter W^*(ε) are studied, and a known result is improved. The main result is that for a Banach space X, if there is ε, where 0 < ε < 1/2, such that W^*(1 + ε) > ε/2 where W^*(1 + ε) = lim_→ε W^* (1 + ), then X has normal structure.     

Some results on characterizing the edges of connected graphs with a given domination number

A dominating set for a graph G = (V, E) is a subset of vertices V′ V such that for all v ε V − V′ there exists some u ε V′ for which {v, u} ε E. The domination number of G is the size of its smallest dominating set(s). For a given graph G with minimum size dominating set D, let m₁ (G, D) denote the number of edges that have neither endpoint in D, and let m₂ (G, D) denote the number of edges that have at least one endpoint in D. We characterize the possible values that the pair (m₁ (G, D), m₂ (G, D)) can attain for connected graphs having a given domination number.     

A matrix problem associated with computing Cohen-Macaulay type

Suppose A∈M_n×m(F), B∈M_n×t(F) for some field F. Define Г(AB) to be the set of n×n diagonal matrices D such that the column space of DA is contained in the column space of B. In this paper we determine dim Г(AB). For matrices AB of the same rank we provide an algorithm for computing dim Г(AB).     

Classical and vector sturm—liouville problems: recent advances in singular-point analysis and shooting-type algorithms

Significant advances have been made in the last year or two in algorithms and theory for Sturm—Liouville problems (SLPs). For the classical regular or singular SLP −(p(x)u′)′ + q(x)u = λw(x)u, a < x < b, we outline the algorithmic approaches of the recent library codes and what they can now routinely achieve.

For a library code, automatic treatment of singular problems is a must. New results are presented which clarify the effect of various numerical methods of handling a singular endpoint.

For the vector generalization −(P(x)u′)′+Q(x)u = λW(x)u where now u is a vector function of x, and P, Q, W are matrices, and for the corresponding higher-order vector self-adjoint problem, we outline the equally impressive advances in algorithms and theory.     

Remarks on the bondage number of planar graphs

The bondage number b(G) of a nonempty graph G is the cardinality of a smallest set of edges whose removal from G results in a graph with domination number greater than the domination number γ(G) of G. In 1998, J.E. Dunbar, T.W. Haynes, U. Teschner, and L. Volkmann posed the conjecture b(G)Δ(G)+1 for every nontrivial connected planar graph G. Two years later, L. Kang and J. Yuan proved b(G)8 for every connected planar graph G, and therefore, they confirmed the conjecture for Δ(G)7. In this paper we show that this conjecture is valid for all connected planar graphs of girth g(G)4 and maximum degree Δ(G)5 as well as for all not 3-regular graphs of girth g(G)5. Some further related results and open problems are also presented.     

Extremal properties of strong quadrature weights and maximal mass results for truncated strong moment problems

A bisequence of complex numbers {μ_n}_−∞^∞ determines a strong moment functional satisfying L[xⁿ] = μ_n. If is positive-definite on a bounded interval (a,b) R{0}, then has an integral representation , n=0, ±1, ±2,…, and quadrature rules {w_ni,x_ni} exist such that μ_k = ∑_i=i^n_ns_ni^kw_ni. This paper is concerned with establishing certain extremal properties of the weights w_ni and using these properties to obtain maximal mass results satisfied by distributions ψ(x) representing when only a finite bisequence of moments {μ_k}_k=−nⁿ⁻¹ is given.