On the existence and uniqueness of pairwise stable networks

In this paper we show how externalities between links affect the existence and uniqueness of pairwise stable (PS) networks. For this we introduce the properties ordinal convexity (concavity) and ordinal strategic complements (substitutes) of utility functions on networks. It is shown that there exists at least one PS network if the profile of utility functions is ordinal convex and satisfies the ordinal strategic complements property. On the other hand, ordinal concavity and ordinal strategic substitutes are sufficient for some uniqueness properties of PS networks. Additionally, we elaborate on the relation of the link externality properties to definitions in the literature.     

On the existence of shortest networks in banach spaces

For dual spaces, and also for L ₁, it is proved that every system of points in such a space admits a shortest network connecting the points. An example of a Banach space is presented in which, for every n ≥ 3, there is a system of n points which cannot be connected by a shortest network.     

On the Diameter of Wenger Graphs

Let q be a prime power, the field of q elements, and n≥1 a positive integer. The Wenger graph W _n (q) is defined as follows: the vertex set of W _n (q) is the union of two copies P and L of (n+1)-dimensional vector spaces over , with two vertices (p ₁,p ₂,…,p _n+1)∈P and [l ₁,l ₂,…,l _n+1]∈L being adjacent if and only if l _i +p _i =p ₁ l _i−1 for 2≤i≤n+1. Graphs W _n (q) have several interesting properties. In particular, it is known that when connected, their diameter is at most 2n+2. In this note we prove that the diameter of connected Wenger graphs is 2n+2 under the assumption that 1≤n≤q−1.     

On the existence and stability of cycles in five-dimensional models of gene networks

Sufficient conditions for the existence and stability of closed trajectories in five-dimensional nonlinear dynamical systems that model gene networks with negative feedback are obtained.     

On the diameter of generalized Kneser graphs

Let r, k be positive integers, s(<r), a nonnegative integer, and n=2r-s+k. The set of r-subsets of [n]={1,2,…,n} is denoted by [n]^r. The generalized Kneser graph K(n,r,s) is the graph whose vertex-set is [n]^r where two r-subsets A and B are joined by an edge if |A∩B|?s. This note determines the diameter of generalized Kneser graphs. More precisely, the diameter of K(n,r,s) is equal to , which generalizes a result of Valencia-Pabon and Vera [On the diameter of Kneser graphs, Discrete Math. 305 (2005) 383-385].     

On the diameter of a domination dot-critical graph

A graph G is domination dot-critical, or just dot-critical, if contracting any edge decreases the domination number. It is totally dot-critical if identifying any two vertices decreases the domination number. In this paper, we study an open question concerning of the diameter of a domination dot-critical graph G.     

On the degree distance of a graph

If G is a connected graph with vertex set V, then the degree distance of G, D^′(G), is defined as , where degw is the degree of vertex w, and d(u,v) denotes the distance between u and v. We prove the asymptotically sharp upper bound for graphs of order n and diameter d. As a corollary we obtain the bound for graphs of order n. This essentially proves a conjecture by Tomescu [I. Tomescu, Some extremal properties of the degree distance of a graph, Discrete Appl. Math. (98) (1999) 159-163].     

On the Number of Vertices with Specified Eccentricity

The eccentricity of a vertex v in a graph is the maximum of the distances from v to all other vertices. The diameter of a graph is the maximum of the eccentricities of its vertices. Fix the parameters n, d, c. Over all graphs with order n and diameter d, we determine the maximum (within 1) and the minimum of the number of vertices with eccentricity c. Revised: May 7, 1999     

On minimum metric dimension of honeycomb networks

A minimum metric basis is a minimum set W of vertices of a graph G(V,E) such that for every pair of vertices u and v of G, there exists a vertex wW with the condition that the length of a shortest path from u to w is different from the length of a shortest path from v to w. The honeycomb and hexagonal networks are popular mesh-derived parallel architectures. Using the duality of these networks we determine minimum metric bases for hexagonal and honeycomb networks.     

Super connectivity of k-regular interconnection networks

Super connectivity is an important issue in interconnection networks. It has been shown that if a network possesses the super connectivity property, it has a high reliability and a small vertex failure rate. Many interconnection networks, like the hypercubes, twisted-cubes, crossed-cubes, möbius cubes, split-stars, and recursive circulant graphs, are proven to be super connected; and the augmented cubes are maximum connected. However, each network vertex has a higher degree as long as the number of vertices increases exponentially. For example, each vertex of the hypercube Q_n has a degree of n, and each vertex of the augmented cube AQ_n has a degree of 2n − 1. In this paper, we not only show that the augmented cube AQ_n is super connected for n = 1, 2 and n ? 4, but also propose a variation of AQ_n, denoted by AQ_n,i, such that V(AQ_n,i) = V(AQ_n), E(AQ_n,i) ⊆ E(AQ_n), and AQ_n,i is i-regular with n ? 3 and 3 ? i ? 2n − 1, in which AQ_n,i is also super connected. In addition, we state the diameter of AQ_n,i.     

On the eccentric connectivity index of a graph

If G is a connected graph with vertex set V, then the eccentric connectivity index of G, ξ^C(G), is defined as where is the degree of a vertex v and is its eccentricity. We obtain an exact lower bound on ξ^C(G) in terms of order, and show that this bound is sharp. An asymptotically sharp upper bound is also derived. In addition, for trees of given order, when the diameter is also prescribed, precise upper and lower bounds are provided.     

On the existence of frames

This paper deals with two topics, namely, frames and pairwise balanced designs (PBD's). Frames, which were introduced by W.D. Wallis for the construction of (skew) Room squares, are shown to exist for most orders congruent to 1 (mod 4). This result relies heavily on the existence of PBD's since the set F = {v | there is a frame of order v] is shown to be PBD-closed. By employing a generalization of the usual recursive construction for PBD's, it is shown that $\text{B}${5, 9, 13, 17}?$\text{B}${5, 9, 13}∪{69, 77, 97, 137, 237, 277, 317, 377, 569}?{n | n  1 (mod 4), n>0}?{29, 33, 49, 57, 93, 129, 133}, where $\text{B}$(K) denotes the set of orders of PBD's of index one having block-sizes from the set K. Frames of orders 5, 9, 13 and 17 are exhibited which immediately implies that F?$\text{B}${5, 9, 13, 17}. D.R. Stinson and W.D. Wallis have shown that {29, 49}?F. Thus there is a frame of order υ for every positive integer υ congruent to 1 (mod 4) with the possible exceptions of υ ? {33, 57, 93, 133}.     

On the existence of interpolatingSK-splines

We establish new sufficient conditions for the existence and uniqueness of generalized interpolatingSK-splines with uniformly distributed interpolation nodes. Our results include all known important assertions obtained in this field as special cases.Translated from Ukrainskii Matematicheskii Zhurnal, Vol.46, No. 11, pp. 1546–1553, November, 1994.     

On the diameter of Kronecker graphs

We prove that a.a.s. as soon as a Kronecker graph becomes connected it has a finite diameter.     

On the complexity of recognizing a class of generalized networks

The problem of determining whether a given linear programming problem can be converted to a generalized network flow problem having no unit-weight cycles is shown to be NP-hard. The same argument also shows that the problem of determining whether a gain matroid is bicircular is NP-hard.     

On the distance distribution of trees

Let G be a tree and k a non-negative integer. We determine best possible upper and lower bounds on the number of pairs of vertices at distance exactly k in G in terms of order alone, and in terms of order and radius or diameter.     

On the existence of polyanalytic functions

We give a sharp estimate for the codimension of the poly‐Bergman space in the poly‐Bergman space over the punctured domain. It is established the behaviour at the infinity point of polyanalytic Bergman functions on the complement of closed disks. In the main result of the paper, we prove that for and the j‐polyanalytic Bergman space over the domain U is trivial precisely when the complement of U has at most one point and at most two points or three points lying in a circle, respectively. We point out the differences between the domains over which the Bergman space and the non‐analytic poly‐Bergman space are trivial.