Isometric embeddings of subdivided connected graphs into hypercubes

Isometric subgraphs of hypercubes are known as partial cubes. These graphs have first been investigated by Graham and Pollack [R.L. Graham, H. Pollack, On the addressing problem for loop switching, Bell System Technol. J. 50 (1971) 2495-2519; and D. Djokovi?, Distance preserving subgraphs of hypercubes, J. Combin. Theory Ser. B 14 (1973) 263-267]. Several papers followed with various characterizations of partial cubes. In this paper, we determine all subdivisions of a given configuration which can be embedded isometrically in the hypercube. More specifically, we deal with the case where this configuration is a connected graph of order 4, a complete graph of order 5 and the case of a k-fan F_k(k≥3).     

The distinguishing number of the augmented cube and hypercube powers

The distinguishing number of a graph G, denoted D(G), is the minimum number of colors such that there exists a coloring of the vertices of G where no nontrivial graph automorphism is color-preserving. In this paper, we answer an open question posed in Bogstad and Cowen [The distinguishing number of the hypercube, Discrete Math. 283 (2004) 29-35] by showing that the distinguishing number of , the pth graph power of the n-dimensional hypercube, is 2 whenever 2<p<n-1. This completes the study of the distinguishing number of hypercube powers. We also compute the distinguishing number of the augmented cube AQ_n, a variant of the hypercube introduced in Choudum and Sunitha [Augmented cubes, Networks 40 (2002) 71-84]. We show that D(AQ₁)=2; D(AQ₂)=4; D(AQ₃)=3; and D(AQ_n)=2 for n?4. The sequence of distinguishing numbers answers a question raised in Albertson and Collins [An introduction to symmetry breaking in graphs, Graph Theory Notes N.Y. 30 (1996) 6-7].     

On embeddings of CAT(0) cube complexes into products of trees via colouring their hyperplanes

We prove that the contact graph of a 2-dimensional CAT(0) cube complex X of maximum degree Δ can be coloured with at most ?(Δ)=MΔ²⁶$?(\mathrm{\Delta })=M{\mathrm{\Delta }}^{26}$ colours, for a fixed constant M. This implies that X (and the associated median graph) isometrically embeds in the Cartesian product of at most ?(Δ)$?(\mathrm{\Delta })$ trees, and that the event structure whose domain is X admits a nice labelling with ?(Δ)$?(\mathrm{\Delta })$ labels. On the other hand, we present an example of a 5-dimensional CAT(0) cube complex with uniformly bounded degrees of 0-cubes which cannot be embedded into a Cartesian product of a finite number of trees. This answers in the negative a question raised independently by F. Haglund, G. Niblo, M. Sageev, and the first author of this paper.     

Every weakly compact set can be uniformly embedded into a reflexive Banach space

Based on an application of the Davis-Figiel-Johnson-Pelzyski procedure, this note shows that every weakly compact subset of a Banach space can be uniformly embedded into a reflexive Banach space. As its application, we present the recent renorming theorems for reflexive spaces of Odell- Schlumprecht and Hajek-Johanis can be extended and localized to weakly compact convex subsets of an arbitrary Banach space.     

Minimum embedding of Steiner triple systems into -designs I

A (K₄-e)-design on v+w points embeds a Steiner triple system (STS) if there is a subset of v points on which the graphs of the design induce the blocks of a STS. It is established that wv/3, and that when equality is met that such a minimum embedding of an STS(v) exists, except when v=15.     

The Clar formulas of a benzenoid system and the resonance graph

It is shown that the number of Clar formulas of a Kekuléan benzenoid system B is equal to the number of subgraphs of the resonance graph of B isomorphic to the Cl(B)-dimensional hypercube, where Cl(B) is the Clar number of B.     

On the Embedding of an Affine Space into a Projective Space

Let k, K be fields, and assume that |k| 4 and n, m 2, or |k| = 3 and n 3, m 2. Then, for any embedding of AG(n, k) into PG(m, K), there exists an isomorphism from k into K and an (n+1) × (m+1) matrix B with entries in K such that can be expressed as (x₁,x₂,...,x_n) = [(1,x₁ ,x₂ ,...,x_n )B], where the right-hand side is the equivalence class of (1,x₁ ,x₂ ,...,x_n )B. Moreover, in this expression, is uniquely determined, and B is uniquely determined up to a multiplication of element of K*. Let l 1, and suppose that there exists an embedding of AG(m+l, k) into PG(m, K) which has the above expression. If we put r = dim _k K, then we have r 3 and m > 2 l-1)/(r-2). Conversely, there exists an embedding of AG(l+m, k) into PG(m, K) with the above expression if K is a cyclic extension of k with dim _k K=r 3, and if m 2l/(r-2) with m even or if m 2l/(r-2) +1 with m odd.     

A Moore space with a -base which cannot be densely embedded in any Moore space with the Baire property

The author answers a question raised in the literature about twenty five years ago and raised again more recently in Open Problems in Topology, by G. M. Reed, concerning the conjecture that every Moore space with a -discrete -base can be densely embedded in a Moore space having the Baire property. Even though closely related results have made this conjecture seem likely to be true, the author shows that, surprisingly, the conjecture is false.

     

The sum of the distances between the leaves of a tree and the 'semi-regular' property

Various topological indices have been put forward in different studies, from biochemistry to pure mathematics. Among them, the Wiener index, the number of subtrees, and the Randi? index have received great attention from mathematicians. In the study of extremal problems regarding these indices among trees, one interesting phenomenon is that they share the same extremal tree structures. Much effort was devoted to the study of the correlations between these various indices. In this note we provide a common characteristic (the ‘semi-regular’ property) of these extremal structures, with respect to the above mentioned indices, among trees with a given maximum degree. This observation leads to a more unified approach for characterizing these extremal structures. As an application/example, we illustrate the idea by studying the extremal trees, regarding the sum of distances between all pairs of leaves of a tree, a new index, which recently appeared in phylogenetic tree reconstruction, and the study of the neighborhood of trees.     

Performance analysis of a hybrid switching system where voice messages can be queued

In the classical model of a hybrid switching system with movable boundary it is assumed that blocked voice messages are lost and do not affect the further functioning of the system. We describe a more realistic model where blocked voice messages are queued and then are served once a channel becomes free. The main mathematical difficulty in the analysis of such models lies in the fact that the underlying stochastic process has as state space the whole quadrant ₊ ² . We reduce the problem to a set of equations defined over the lattice semi-strip {1,...,N} × ₊. This in turn allows us to use available general mathematical theories.     

Sets of disjoint snakes based on a Reed-Muller code and covering the hypercube

A snake-in-the-box code (or snake) of word length n is a simple circuit in an n-dimensional cube Q _n , with the additional property that any two non-neighboring words in the circuit differ in at least two positions. To construct such snakes a straightforward, non-recursive method is developed based on special linear codes with minimum distance 4. An extension of this method is used for the construction of covers of Q _n consisting of 2 ^m-1 vertex-disjoint snakes, for 2 ^m-1 < n ≤ 2 ^m . These covers turn out to have a symmetry group of order 2 ^m .      

Existence of positive solutions for a class of second-order ordinary differential systems

In this paper, we present some new concepts of superlinearity and sublinearity for nonlinear terms of second-order ordinary differential systems, and then consider the existence of positive solutions for systems with such superlinear and sublinear nonlinear terms, especially proving the existence of positive solutions for systems in which one nonlinear term is superlinear and the other is sublinear.     

A multiplicity result of positive solutions for a class of multi-parameter ordinary differential systems

In this paper, we establish a result of Leray-Schauder degree on the order interval which is induced by a pair of strict lower and upper solutions for a system of second-order ordinary differential equations. As applications, we prove the global existence of positive solutions for a multi-parameter system of second-order ordinary differential equations with respect to parameters. The discussion is based on the result of Leray-Schauder degree on the order interval and the fixed point index theory in cones.     

On the limit-point case of singular linear Hamiltonian systems

This article is concerned with the limit-point case (l.p.c.) of a Hamiltonian system. We present new proofs for several existing equivalent conditions on the l.p.c. established in terms of the asymptotic behaviour of the square integrable solutions of Hamiltonian systems with different spectral parameters and functions in the domain of the corresponding maximal operator, respectively. Further, we give two equivalent conditions in terms of the asymptotic behaviour of the square integrable solutions of Hamiltonian systems with the same complex and real spectral parameters, respectively. In addition, we establish two limit-point criteria which extend the relevant existing results.     

Subharmonic solutions of Hamiltonian systems and the Maslov-type index theory

This paper deals with the subharmonic solutions of Hamiltonian systems

(H)     

Hitting Times,Cover Cost,and the Wiener Index of a Tree

We exhibit a close connection between hitting times of the simple random walk on a graph, the Wiener index, and related graph invariants. In the case of trees, we obtain a simple identity relating hitting times to the Wiener index. It is well known that the vertices of any graph can be put in a linear preorder so that vertices appearing earlier in the preorder are “easier to reach” by a random walk, but “more difficult to get out of.” We define various other natural preorders and study their relationships. These preorders coincide when the graph is a tree, but not necessarily otherwise. Our treatise is self‐contained, and puts some known results relating the behavior or random walk on a graph to its eigenvalues in a new perspective.