Narrow Results

The star graph, though an attractive alternative to the hypercube, has a major drawback in that the number of nodes for an n-star graph must be n!, and thus considerably limits the choice of the number of nodes in the graph. In order to alleviate this drawback, the arrangement graph was recently proposed as a generalization of the star graph topology. The arrangement graph provides more flexibility than the star graph in choosing the number of nodes, but the degree of the resulting network may be very high. To overcome that disadvantage, this paper presents another generalization of the star graph, called the (n,k)-star graph. We examine some topological properties of the (n,k)-star graph from the graph-theory point of view. It is shown that two different types of edges in the (n,k)-star prevent it from being edge-symmetric, but edges in each class are essentially symmetric with respect to each other. Also, the diameter and the exact average distance of the (n,k)-star graph are derived. In addition, the fault-diameter for the (n,k)-star graph is shown to be at most the fault-free diameter plus three.

We present a surface area lemma to characterize the surface area of a product graph in terms of those of its factors via a generating function approach. We then apply this lemma to derive surface area related results for meshes and tori. Moreover, we also provide explicit formulas for the average distances of these networks.

The average distance between points of a fractal is proposed as a natural measure of the way in which the points of a fractal are distributed. The average distance between points of the Cantor Set is found to be , the average distance between points of the Cantor p-set is , and the average distance between points of the Fat Cantor p-set is . A general formula for computing the average distance between points of a self-similar set satisfying the open set condition is found.

In this paper, we introduce a method which can generate a family of growing symmetrical tree networks. The networks are constructed by replacing each edge with a reduced-scale of the initial graph. Repeating this procedure, we obtain the fractal networks. In this paper, we define the average geodesic distance of fractal tree in terms of some integral, and calculate its accurate value. We find that the limit of the average geodesic distance of the finite networks tends to the average geodesic distance of the fractal tree. This result generalizes the paper [Z. Zhang, S. Zhou, L. Chen, M. Yin and J. Guan, Exact solution of mean geodesic distance for Vicsek fractals, J. Phys. A: Math. Gen.41(48) (2008) 7199–7200] for which the mean geodesic distance of Vicsek fractals was considered.

In this paper, we investigate the average geodesic distance on the Sierpinski hexagon in terms of finite patterns on integrals. Applying this result, we also obtain the asymptotic formula for average distances of Sierpinski hexagon networks.

The substitution network is a deterministic model of evolving self-similar networks. For normalized substitution networks, the limit of metric spaces with respect to networks is a self-similar fractal and the limit of average distances on networks is the integral of geodesic distance of the fractal on the self-similar measure. After some technical handles, we establish the finiteness of integrals and obtain a linear equation set to solve the average distance on the fractal.

This paper discusses the asymptotic formula of average distances on node-weighted Sierpinski skeleton networks by using the integral of geodesic distance in terms of self-similar measure on the Sierpinski gasket with respect to the weight vector.

In this paper, we discuss a family of non-p.c.f. self-similar networks. Although the boundary of each fractal piece is not a finite set, we obtain the finite geometric patterns for the integral of geodesic distance on the self-similar measure, and then calculate its average distance.

In this paper, we discuss a family of p.c.f. self-similar fractal networks which have reflection transformations. We obtain the average geodesic distance on the corresponding fractal in terms of finite pattern of integrals. With these results, we also obtain the asymptotic formula for average distances of the skeleton networks.

The geodesic structures on self-similar fractals are interesting. One feature of geodesic structures is average distance on fractal. We investigate the Sierpinski-like carpet and obtain the average distance in terms of self-similar measure.

In this paper, we establish the theory of finite geodesic patterns on limit space to calculate the average distances of touching networks.

Let Γ be a finite group with a nonempty subset A. The Cayley graphCay(Γ, A) of Γ generated by A is defined as the digraph with vertex set Γ and edge set {(x,y) | x^-1 y ∈ A}. Cay(Γ, A) can be regarded as an undirected graph if x^-1 ∈ A for all x ∈ A. Let denote the largest integer M so that there exists a set of integers A = {±1, ±a₂;…, ±a_k} such that the average distance between all pairs of vertices of Cay(ℤ_M,A) is at most r, where ℤ_M is the additive group of residue classes modulo M. It is proved in this paper that

Let denote the average Hamming distance of a binary constant weight code C. A_i is the distance distribution of C and B_j is the transform quantity of A_i. Let β(n, M, w) denote the minimum average Hamming distance of a binary constant weight code with length n, size M, and weight w. In this paper, we have established the relation among B_j, and A_i. We also study the problem of determining β(n, M, w) and bounds of β(n, M, w) for different values of M.

Using Ore's structural characterization on diameter-maximal graphs, we determine the extremal graphs with the minimum average distance among the graphs with given order and diameter, thereby solving a conjecture of Aouchiche and Hansen [Automated results and conjectures on average distance in graphs, in Graph Theory in Paris, eds. A. Bondy, J. Fonlupt, J.-L. Fouquet, J.-C. Fournier and J.-L. Ramírez Alfonsín, Trends in Mathematics, Vol. 6 (Birkhäuser Boston, Boston, 2007), pp. 21–36].

Many large networks can be constructed from some existing small networks by using, in terms of graph theory, Cartesian product and Lexicographic product. The model of these networks possessing the property of small average distance and high connectivity which is a good network model. In this paper, we give the average distance and Wiener index of the Cartesian product of networks.