Tree spanners in planar graphs

A tree t-spanner of a graph G is a spanning subtree T of G in which the distance between every pair of vertices is at most t times their distance in G. Spanner problems have received some attention, mostly in the context of communication networks. It is known that for general unweighted graphs, the problem of deciding the existence of a tree t-spanner can be solved in polynomial time for t=2, while it is NP-hard for any t⩾4; the case t=3 is open, but has been conjectured to be hard. In this paper, we consider tree spanners in planar graphs. We show that even for planar unweighted graphs, it is NP-hard to determine the minimum t for which a tree t-spanner exists. On the other hand, we give a polynomial algorithm for any fixed t that decides for planar unweighted graphs with bounded face length whether there is a tree t-spanner. Furthermore, we prove that it can be decided in polynomial time whether a planar unweighted graph has a tree t-spanner for t=3.     

A recognition algorithm for the intersection graphs of paths in trees

Let F be a finite family of non-empty sets. An undirected graph G is an intersection graph for F if there is a one-to-one correspondence between the vertices of G and the sets of F such that two sets have a non-empty intersection exactly when the corresponding vertices are adjacent in G. If this is the case then F is said to be an intersection model for the graph G. If F is a family of paths within a tree T, then G is called a path graph. This paper proves a characterization for the path graphs and then gives a polynomial time algorithm for their recognition. If G is a path graph the algorithm constructs a path intersection model for G.     

Set-valued contractions and fixed points

A common fixed point theorem is proved for a family of set-valued contraction mappings in gauge spaces. This result is related to a recent result of Frigon for ‘generalized contractions’ and it includes a method for approximating the fixed point. The remainder of the paper is devoted to results for families of set-valued contraction mappings in hyperconvex spaces. It is proved, for example, that if M is a hyperconvex metric space and f_α is a family of set-valued contractions indexed over a directed set Λ and taking values in the space of all nonempty admissible subsets of M endowed with the Hausdorff metric, then the condition f_β(x)⊆f_α(x) for all x∈M and β⩾α implies that the set of points x∈M for which x∈⋂_α∈Λf_β(x) is nonempty and hyperconvex.     

On 3-Steiner simplicial orderings

Let G be a connected graph and S a nonempty set of vertices of G. A Steiner tree for S is a connected subgraph of G containing S that has a minimum number of edges. The Steiner interval for S is the collection of all vertices in G that belong to some Steiner tree for S. Let k≥2 be an integer. A set X of vertices of G is k-Steiner convex if it contains the Steiner interval of every set of k vertices in X. A vertex x∈X is an extreme vertex of X if X?{x} is also k-Steiner convex. We call such vertices k-Steiner simplicial vertices. We characterize vertices that are 3-Steiner simplicial and give characterizations of two classes of graphs, namely the class of graphs for which every ordering produced by Lexicographic Breadth First Search is a 3-Steiner simplicial ordering and the class for which every ordering of every induced subgraph produced by Maximum Cardinality Search is a 3-Steiner simplicial ordering.     

C(α) preserving operators on separable Banach spaces

Let T be a bounded linear operator from a separable Banach space X to a Banach space Y. A necessary and sufficient condition on T for the existence of a subspace Z of X such that Z is isomorphic to C(α) and the restriction of T to Z is an isomorphism is given. The special case where X is the disc algebra is then considered and results similar to those previously obtained by the author for C(K) spaces are obtained for the disc algebra. Finally some additional results of the same type are proved for subspaces of C(K) with small annihilator.     

The price of anarchy for non-atomic congestion games with symmetric cost maps and elastic demands

By showing that there is an upper bound for the price of anarchyρ(Γ) for a non-atomic congestion game Γ with only separable cost maps and fixed demands, Roughgarden and Tardos show that the cost of forgoing centralized control is mild. This letter shows that there is an upper bound for ρ(Γ) in Γ for fixed demands with symmetric cost maps. It also shows that there is a weaker bound for ρ(Γ) in Γ with elastic demands.     

An upper bound for the minimum rank of a graph

For a graph G of order n, the minimum rank of G is defined to be the smallest possible rank over all real symmetric n×n matrices A whose (i,j)th entry (for i≠j) is nonzero whenever {i,j} is an edge in G and is zero otherwise. We prove an upper bound for minimum rank in terms of minimum degree of a vertex is valid for many graphs, including all bipartite graphs, and conjecture this bound is true over for all graphs, and prove a related bound for all zero-nonzero patterns of (not necessarily symmetric) matrices. Most of the results are valid for matrices over any infinite field, but need not be true for matrices over finite fields.     

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.     

An upper bound for the competition numbers of graphs

A hole of a graph is an induced cycle of length at least 4. Kim (2005) [2] conjectured that the competition number k(G) is bounded by h(G)+1 for any graph G, where h(G) is the number of holes of G. In Lee et al. [3], it is proved that the conjecture is true for a graph whose holes are mutually edge-disjoint. In Li et al. (2009) [4], it is proved that the conjecture is true for a graph, all of whose holes are independent. In this paper, we prove that Kim’s conjecture is true for a graph G satisfying the following condition: for each hole C of G, there exists an edge which is contained only in C among all induced cycles of G.     

On universal spaces and absorbing sets related to a transfinite extension of covering dimension

R. Pol has shown that for every countable ordinal number α there exists a universal space for separable metrizable spaces X with trindX?α. W. Olszewski has shown that for every countable limit ordinal number λ there is no universal space for separable metrizable space with trIndX?λ. T. Radul and M. Zarichnyi have proved that for every countable limit ordinal number there is no universal space for separable metrizable spaces with dimWX?α where dimW is a transfinite extension of covering dimension introduced by P. Borst. We prove the same result for another transfinite extension dimC of the covering dimension.As an application, we show that there is no absorbing sets (in the sense of Bestvina and Mogilski) for the classes of spaces X with dimCX?α belonging to some absolute Borel class.     

Archimedean lattices

Anarchimedean lattice is a complete algebraic latticeL with the property that for each compact elementc∈L, the meet of all the maximal elements in the interval [0,c] is 0.L ishyper-archimedean if it is archimedean and for eachx∈L, [x, 1] is archimedean. The structure of these lattices is analysed from the point of view of their meet-irreducible elements. If the lattices are also Brouwer, then the existence of complements for the compact elements characterizes a particular class of hyper-archimedean lattices. The lattice ofl-ideals of an archimedean lattice ordered group is archimedean, and that of a hyper-archimedean lattice ordered group is hyper-archimedean. In the hyper-archimedean case those arising as lattices ofl-ideals are fully characterized.     

The Logical vs. the Ontological Understanding of Conditions

According to the truth-functional analysis of conditions, to be ‘necessary for’ and ‘sufficient for’ are converse relations. From this, it follows that to be ‘necessary and sufficient for’ is a symmetric relation, that is, that if P is a necessary and sufficient condition for Q, then Q is a necessary and sufficient condition for P. This view is contrary to common sense. In this paper, I point out that it is also contrary to a widely accepted ontological view of conditions, according to which if P is a necessary and sufficient condition for Q, then Q is in no sense a condition for P; it is a mere consequence of P.     

Retractions onto series-parallel posets

The poset retraction problem for a poset P is whether a given poset Q containing P as a subposet admits a retraction onto P, that is, whether there is a homomorphism from Q onto P which fixes every element of P. We study this problem for finite series-parallel posets P. We present equivalent combinatorial, algebraic, and topological charaterisations of posets for which the problem is tractable, and, for such a poset P, we describe posets admitting a retraction onto P.     

On list critical graphs

In this paper we discuss some basic properties of k-list critical graphs. A graph G is k-list critical if there exists a list assignment L for G with |L(v)|=k−1 for all vertices v of G such that every proper subgraph of G is L-colorable, but G itself is not L-colorable. This generalizes the usual definition of a k-chromatic critical graph, where L(v)={1,…,k−1} for all vertices v of G. While the investigation of k-critical graphs is a well established part of coloring theory, not much is known about k-list critical graphs. Several unexpected phenomena occur, for instance a k-list critical graph may contain another one as a proper induced subgraph, with the same value of k. We also show that, for all 2≤p≤k, there is a minimal k-list critical graph with chromatic number p. Furthermore, we discuss the question, for which values of k and n is the complete graph K_nk-list critical. While this is the case for all 5≤k≤n, K_n is not 4-list critical if n is large.     

Fast enclosure for all eigenvalues in generalized eigenvalue problems

A fast method for enclosing all eigenvalues in generalized eigenvalue problems Ax=λBx is proposed. Firstly a theorem for enclosing all eigenvalues, which is applicable even if A is not Hermitian and/or B is not Hermitian positive definite, is presented. Next a theorem for accelerating the enclosure is presented. The proposed method is established based on these theorems. Numerical examples show the performance and property of the proposed method. As an application of the proposed method, an efficient method for enclosing all eigenvalues in polynomial eigenvalue problems is also sketched.     

G-Strands

A G-strand is a map g(t,s):?×?→G for a Lie group G that follows from Hamilton’s principle for a certain class of G-invariant Lagrangians. The SO(3)-strand is the G-strand version of the rigid body equation and it may be regarded physically as a continuous spin chain. Here, SO(3) _K -strand dynamics for ellipsoidal rotations is derived as an Euler–Poincaré system for a certain class of variations and recast as a Lie–Poisson system for coadjoint flow with the same Hamiltonian structure as for a perfect complex fluid. For a special Hamiltonian, the SO(3) _K -strand is mapped into a completely integrable generalization of the classical chiral model for the SO(3)-strand. Analogous results are obtained for the Sp(2)-strand. The Sp(2)-strand is the G-strand version of the Sp(2) Bloch–Iserles ordinary differential equation, whose solutions exhibit dynamical sorting. Numerical solutions show nonlinear interactions of coherent wave-like solutions in both cases. Diff(?)-strand equations on the diffeomorphism group G=Diff(?) are also introduced and shown to admit solutions with singular support (e.g., peakons).     

All-shortest-path 2-interval routing is NP-complete

k-Interval Routing Scheme (k-IRS) is a compact routing method that allows up to k interval labels to be assigned to an arc. A fundamental problem is to characterize the networks that admit k-IRS. All of the problems related to single-shortest-path k-IRS have already been shown to be NP-complete. For all-shortest-path k-IRS, the characterization problems have been proved to be NP-complete for every k≥3, and remain open for k=1,2. In this paper, we close the open case of k=2 by showing that it is NP-complete to decide whether a graph admits an all-shortest-path 2-IRS. The same proof is also valid for all-shortest-path Strict 2-IRS. All-shortest-path Strict k-IRS is previously known to be polynomial for k=1, open for k=2,3, and NP-complete for every constant k≥4.     

Higher rank numerical ranges and low rank perturbations of quantum channels

For a positive integer k, the rank-k numerical range Λk(A) of an operator A acting on a Hilbert space H of dimension at least k is the set of scalars λ such that PAP=λP for some rank k orthogonal projection P. In this paper, a close connection between low rank perturbation of an operator A and Λk(A) is established. In particular, for 1?r<k it is shown that Λk(A)⊆Λk−r(A+F) for any operator F with rank(F)?r. In quantum computing, this result implies that a quantum channel with a k-dimensional error correcting code under a perturbation of rank at most r will still have a (k−r)-dimensional error correcting code. Moreover, it is shown that if A is normal or if the dimension of A is finite, then Λk(A) can be obtained as the intersection of Λk−r(A+F) for a collection of rank r operators F. Examples are given to show that the result fails if A is a general operator. The closure and the interior of the convex set Λk(A) are completely determined. Analogous results are obtained for Λ_∞(A) defined as the set of scalars λ such that PAP=λP for an infinite rank orthogonal projection P. It is shown that Λ_∞(A) is the intersection of all Λk(A) for k=1,2,…. If A−μI is not compact for all μ∈C, then the closure and the interior of Λ_∞(A) coincide with those of the essential numerical range of A. The situation for the special case when A−μI is compact for some μ∈C is also studied.     

Inverses of tridiagonal Toeplitz and periodic matrices with applications to mechanics

The linear algebraic equation Ax = b with tridiagonal coefficient matrix of A is solved by the analytical matrix inversion. An explicit formula is known if A is a Toeplitz matrix. New formulas are presented for the following cases: (1) A is of Toeplitz type except that A(1, 1) and A(n, n) are different from the remaining diagonal elements. (2) A is p-periodic (p > 1), by which is meant that in each of the three bands of A a group of p elements is periodically repeated. (3) The tridiagonal matrix A is composed of periodic submatrices of different periods. In cases (2) and(3) the problem of matrix inversion is reduced to a second-order difference equation with periodic coefficients. The solution is based on Floquet's theorem. It is shown that for p = 1 the formulae found for periodic matrices reduce to special forms valid for Toeplitz matrices. The results are applied to problems of elastostatics and of vibration theory.