Narrow Results

Robustness of the network topology is a key aspect in the design of computer networks. Vertex (Link, respectively) residual closeness is a new graph-theoretic concept defined as a measure of network robustness due to the failure of individual vertices (links, respectively). In this paper, we identify the trees and unicyclic graphs with the first a few smallest vertex residual closeness, and determine the graphs that minimize or maximize the vertex (link, respectively) residual closeness over some classes of graphs.

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

The irregularity of a graph $G$ is defined as $\mathrm{\text{irr}}(G)={\sum }_{uv\in E(G)}|d_u-d_v|$, where $d_u$ denotes the degree of a vertex $u\in V(G)$ and $E(G)$ is the edge set of $G$. From the class of all $n$-vertex (molecular) trees, graphs with the first five minimal $\mathrm{\text{irr}}$-values have already been characterized in the literature. The main purpose of this paper is to determine the graphs with the sixth, seventh and eighth minimal $\mathrm{\text{irr}}$-values among all the members of the aforementioned class for $n\ge 7$, $n\ge 8$ and $n\ge 8$, respectively.