Journal of Interconnection Networks

An important and interesting parameter of an interconnection network is the number of vertices of a specific distance from a specific vertex. This is known as the surface area or the Whitney number of the second kind. In this paper, we give explicit formulas for the surface areas of the (n, k)-star graphs and the arrangement graphs via the generating function technique. As a direct consequence, these formulas will also provide such explicit formulas for the star graphs, the alternating group graphs and the split-stars since these graphs are related to the (n, k)-star graphs and the arrangement graphs. In addition, we derive the average distances for these graphs.

For a graph G with n vertices and a permutation α on V(G), a permutation graph P_α(G) is obtained from two identical copies of G by adding an edge between v and α(V) for any v ϵ V(G). Let γ(G) be the domination number of a graph G. It has been shown that γ(G) ≤ γ(P_α(G) ≤ 2γ(G) for any permutation α on V(G). In this paper, we investigate specific graphs for which there exists a permutation α such that γ(P_α(G)) ≻ γ(G) in terms of the domination number of G or the maximum degree of G. Additionally, we construct a class of graphs for which the domination number of any permutation graph is twice the domination number of the original graph, as well as explore finding a specific graph G and permutation α for any two positive integers a and b with a ≤ b ≤ 2a, to have γ(G) = a and γ(P_α(G)) = b.

Because of its applications in network theory, the wide diameter of graphs has been studied extensively in recent years. It is still an open problem to compute the wide diameter of Cayley graphs. This paper investigates the wide diameter of Cayley graphs of ℤ_m, the cyclic group of residue classes modulo m. It is proved that the k-wide diameter of the Cayley graph Cay(Z_m, A) generated by a k-element set A is d + 1 for k = 2 and ≤ d + 1 for k = 3, where d is the diameter of Cay(ℤ_m, A).

In this paper we study the fault diameter of the n-dimensional hypercube (or n-cube for short), Q_n, for n ≥ 3. Let F be a set of hybrid node-faults and/or link-faults in Q_n such that every node of Q_n is still connected to at least one fault-free node by a fault-free link. Then we compute the exact diameter of Q_n - F for |F| ≤ 2n - 3. As an immediate consequence, our result improves upon those presented by S. Latifi (1993), in which only node-faults were addressed.

A bipartite graph G is hamiltonian laceable if there is a hamiltonian path between any two vertices of G from distinct vertex bipartite sets. A bipartite graph G is k-edge fault-tolerant hamiltonian laceable if G - F is hamiltonian laceable for every F ⊆ E(G) with |F| ≤ k. A graph G is k-edge fault-tolerant conditional hamiltonian if G - F is hamiltonian for every F ⊆ E(G) with |F| ≤ k and δ(G - F) ≥ 2. Let G₀ = (V₀, E₀) and G₁ = (V₁, E₁) be two disjoint graphs with |V₀| = |V₁|. Let E_r = {(v,ɸ(v)) | v ϵ V₀,ɸ(v) ϵ V₁, and ɸ: V₀ → V₁ is a bijection}. Let G = G₀ ⊕ G₁ = (V₀ ⋃ V₁, E₀ ⋃ E₁ ⋃ E_r). The set of n-dimensional hypercube-like graphH_n is defined recursively as (a) H₁ = K₂, K₂ is the complete graph with two vertices, and (b) if G₀ and G₁ are in H_n, then G = G₀ ⊕ G₁ is in H_n+1. Let B_n be the set of graphs G where G is bipartite and G ϵ H_n. In this paper, we show that every graph in B_n is (n - 2)-edge fault-tolerant hamiltonian laceable if n ≥ 2 and every graph in B_n is (2n - 5)-edge fault-tolerant conditional hamiltonian if n ≥ 3.

The local connectivity of two vertices is defined as the maximum number of internally vertex-disjoint paths between them. In this paper, we define two vertices as maximally local-connected, if the maximum number of internally vertex-disjoint paths between them equals the minimum degree of these two vertices. Moreover, we show that an (n-1)-regular Cayley graph generated by transposition tree is maximally local-connected, even if there are at most (n-3) faulty vertices in it, and prove that it is also (n-1)-fault-tolerant one-to-many maximally local-connected.