Mean distance and minimum degree

We prove that in a graph of order n and minimum degree d, the mean distance μ must satisfy . This asymptotically confirms, and improves, a conjecture of the computer program GRAFFITI. The result is close to optimal; examples show that for any d, μ may be larger than n/(d + 1). © 1997 John Wiley & Sons, Inc. J Graph Theory 25: 95–99, 1997     

A bound on the minimum distance of generalized quasi-twisted codes

Generalized quasi-twisted (GQT) codes form a generalization of quasi-twisted (QT) codes and generalized quasi-cyclic (GQC) codes. By the Chinese remainder theorem, the GQT codes can be decomposed into a direct sum of some linear codes over Galois extension fields, which leads to the trace representation of the GQT codes. Using this trace representation, we first prove the minimum distance bound for GQT codes with two constituents. Then we generalize the result to GQT codes with s constituents. Finally, we present some examples to show that the bound is better than the well-known Esmaeili-Yari bound and sharp in many instances.     

On the existence of minimum contrast estimates in binary response model

When random samples are drawn from a 3-parameter distribution with a shifted origin and the observations corresponding to each sample are binary, criteria for the existence of minimum contrast estimates are given. These criteria can be drived by a method, called the probability contents boundary analysis. The probabilities of the existence of maximum likelihood estimates and least squares estimates are evaluated, by simulation with 1000 replications, in the case where the underlying distribution is a 3-parameter lognormal distribution or a 3-parameter loglogistic distribution.     

A note on dominating sets and average distance

We show that the total domination number of a simple connected graph is greater than the average distance of the graph minus one-half, and that this inequality is best possible. In addition, we show that the domination number of the graph is greater than two-thirds of the average distance minus one-third, and that this inequality is best possible. Although the latter inequality is a corollary to a result of P. Dankelmann, we present a short and direct proof.     

A note on the simple structural regression model

In this paper we investigate some aspects like estimation and hypothesis testing in the simple structural regression model with measurement errors. Use is made of orthogonal parametrizations obtained in the literature. Emphasis is placed on some properties of the maximum likelihood estimators and also on the distribution of the likelihood ratio statistics.     

Inverse problem of minimum cuts

Given a networkN = (V,A,c), a sources V, a. sinkt V and somes —t cuts and suppose each element of the capacity vectorc can be changed with a cost proportional to the changes, the inverse problem of minimum cuts we study here is to change the original capacities with the least total cost under restrictions on the changes of the capacities, so that all thoses —t cuts become minimum cuts with respect to the new capacities.In this paper we shall show that the inverse problem of minimum cuts can be directly transformed into a minimum cost circulation problem and therefore can be solved efficiently by strongly polynomial algorithms.The author is grateful to the partial support of the Universities Grant Council of Hong Kong under the grant CITYU #9040189Work partially supported by the National Natural Science Foundation of China     

A note on Bartholdi zeta function and graph invariants based on resistance distance

Let $G$ be a finite connected graph. In this note, we show that the complexity of $G$ can be obtained from the partial derivatives at $(1?\frac{1}{t},t)$ of a determinant in terms of the Bartholdi zeta function of $G$. Moreover, the second order partial derivatives at $(1?\frac{1}{t},t)$ of this determinant can all be expressed as the linear combination of the Kirchhoff index, the additive degree-Kirchhoff index, and the multiplicative degree-Kirchhoff index of the graph $G$.     

Lower bounds on the minimum average distance of binary codes

Let β(n,M) denote the minimum average Hamming distance of a binary code of length n and cardinality M. In this paper we consider lower bounds on β(n,M). All the known lower bounds on β(n,M) are useful when M is at least of size about 2ⁿ⁻¹/n. We derive new lower bounds which give good estimations when size of M is about n. These bounds are obtained using a linear programming approach. In particular, it is proved that lim_n→∞β(n,2n)=5/2. We also give a new recursive inequality for β(n,M).     

Properties of connected graphs having minimum degree distance

The degree distance of a connected graph, introduced by Dobrynin, Kochetova and Gutman, has been studied in mathematical chemistry. In this paper some properties of graphs having minimum degree distance in the class of connected graphs of order n and size m≥n−1 are deduced. It is shown that any such graph G has no induced subgraph isomorphic to P₄, contains a vertex z of degree n−1 such that G−z has at most one connected component C such that |C|≥2 and C has properties similar to those of G.For any fixed k such that k=0,1 or k≥3, if m=n+k and n≥k+3 then the extremal graph is unique and it is isomorphic to K₁+(K_1,k+1∪(n−k−3)K₁).     

Unicyclic and bicyclic graphs having minimum degree distance

In this paper characterizations of connected unicyclic and bicyclic graphs in terms of the degree sequence, as well as the graphs in these classes minimal with respect to the degree distance are given.     

A note on generalized twisted anomaly cancellation formulas

In this note, by studying modular invariance properties of some characteristic forms, we get some new twisted anomaly cancellation formulas.     

Average distance,minimum degree,and spanning trees

The average distance μ(G) of a connected graph G of order n is the average of the distances between all pairs of vertices of G, i.e., μ(G) = ()⁻¹ Σ_{x,y}⊂V(G) d_G(x, y), where V(G) denotes the vertex set of G and d_G(x, y) is the distance between x and y. We prove that every connected graph of order n and minimum degree δ has a spanning tree T with average distance at most . We give improved bounds for K₃‐free graphs, C₄‐free graphs, and for graphs of given girth. © 2000 John Wiley & Sons, Inc. J Graph Theory 33: 1–13, 2000     

A note on multivariate Gaussian estimates

An upper bound of multivariate Gaussian probability for a general convex domain D is given based on a geometric observation. The bound is sharper than known ones on multivariate Mills' ratio in many cases.     

A note on fast approximate minimum degree orderings for symmetric matrices with some dense rows

Recently, a number of variants of the approximate minimum degree algorithm have been proposed that aim to efficiently order symmetric matrices containing some dense rows. We compare the performance of these variants on a range of problems and highlight their potential limitations. This leads us to propose a new variant that offers both speed and robustness. Copyright © 2009 John Wiley & Sons, Ltd.     

Improving bounds on the minimum Euclidean distance for block codes by inner distance measure optimization

The minimum Euclidean distance is a fundamental quantity for block coded phase shift keying (PSK). In this paper we improve the bounds for this quantity that are explicit functions of the alphabet size q, block length n and code size |C|. For q=8, we improve previous results by introducing a general inner distance measure allowing different shapes of a neighborhood for a codeword. By optimizing the parameters of this inner distance measure, we find sharper bounds for the outer distance measure, which is Euclidean.The proof is built upon the Elias critical sphere argument, which localizes the optimization problem to one neighborhood. We remark that any code with q=8 that fulfills the bound with equality is best possible in terms of the minimum Euclidean distance, for given parameters n and |C|. This is true for many multilevel codes.     

A note on distinct distance subsets

It is shown that given a set of N points in the plane, sphere or hyperbolic plane, there is a subset of size ${\gtrsim (N/\log N)^{1/3}}$ with all pairwise distances between points distinct.     

Minimum distance regression-type estimates with rates under weak dependence

Under weak dependence, a minimum distance estimate is obtained for a smooth function and its derivatives in a regression-type framework. The upper bound of the risk depends on the Kolmogorov entropy of the underlying space and the mixing coefficient. It is shown that the proposed estimates have the same rate of convergence, in the L ₁-norm sense, as in the independent case.This work was partially supported by a research grant from the Natural Sciences and Engineering Research Council of Canada.     

A NOTE ON CITY BLOCK DISTANCE

In this paper, problem of characterizing the city block distance between two lattice points in k-dimensional Euclidean space is discussed.     

Maximum distance holey packings of type 3n with triples

Maximum distance holey packings of type gⁿ with triples, MDHP(2, 3, n, g)'s, are equivalent to optimal (g+1)‐ary (n, 3, 3) codes. The problem of existence of MDHP(2, 3, n, 2)'s has been settled completely. For g = 3, only the case of odd n has been investigated. With the aid of a computer, we provides the existence result for an MDHP(2, 3, n, 3) with n even, in which singular indirect product construction for MDHPs is developed. © 2000 John Wiley & Sons, Inc. J Combin Designs 8: 132–140, 2000     

The maximum and minimum degrees of random bipartite multigraphs

In this paper the authors generalize the classic random bipartite graph model, and define a model of the random bipartite multigraphs as follows:let m = m（n） be a positive integer-valued function on n and ζ（n,m;{pk}） the probability space consisting of all the labeled bipartite multigraphs with two vertex sets A ={a₁,a₂,...,a_n} and B = {b₁,b₂,...,b_m}, in which the numbers t_ai,b_j of the edges between any two vertices a_i∈A and b_j∈ B are identically distributed independent random variables with distribution P{t_ai,b_j=k}=pk,k=0,1,2,...,where pk ≥0 and ∞Σk=0 pk=1. They obtain that X_c,d,A, the number of vertices in A with degree between c and d of G_n,m∈ζ（n, m;{pk}） has asymptotically Poisson distribution, and answer the following two questions about the space ζ（n,m;{pk}） with {pk} having geometric distribution, binomial distribution and Poisson distribution, respectively. Under which condition for {pk} can there be a function D（n） such that almost every random multigraph G_n,m∈ζ（n,m;{pk}） has maximum degree D（n）in A? under which condition for {pk} has almost every multigraph G（n,m）∈ζ（n,m;{pk}） a unique vertex of maximum degree in A?