Journal of Interconnection Networks

A red-white coloring of a nontrivial connected graph $G$ of diameter $d$ is an assignment of red and white colors to the vertices of $G$ where at least one vertex is colored red. Associated with each vertex $v$ of $G$ is a $d$-vector, called the code of $v$, whose $i$th coordinate is the number of red vertices at distance $i$ from $v$. A red-white coloring of $G$ for which distinct vertices have distinct codes is called an identification coloring or ID-coloring of $G$. A graph $G$ possessing an ID-coloring is an ID-graph. The minimum number of red vertices among all ID-colorings of an ID-graph $G$ is the identification number or ID-number of $G$. It is shown that the grid $P_m\square P_n$ is an ID-graph if and only $(m,n)\ne (2,2)$ and the prism $C_n\square K_2$ is an ID-graph if and only if $n\ge 6$.

Let ${𝒫}$ be a set of edges whose induced subgraph consists of vertex-disjoint paths in an $n$-dimensional locally twisted cube $LT{Q}_n$. In this paper, we prove that if ${𝒫}$ contains at most $n-1$ edges, then $LT{Q}_n$ contains a Hamiltonian cycle passing through every edge of ${𝒫}$, where $n\ge 4$. $LT{Q}_3$ has a Hamiltonian cycle passing through at most one prescribed edge.

For a vertex set $S$ of $G$, we use ${\kappa }_S(G)$ to denote the maximum number of edge-disjoint Steiner trees of $G$ such that any two of such trees intersect in $S$. The generalized $k$-connectivity of $G$ is defined as ${\kappa }_k(G)={min}_{S\subseteq V(G),\left|S\right|=k}{\kappa }_S(G)$. We get that for any generalized Petersen graph $G=GP(n,k)$ with $n\ge k+3$, ${\kappa }_t(G)=1$ when $t\ge 2k+5$. We give the values of ${\kappa }_k(G)$ for Petersen graph $GP(5,2)$, where $3\le k\le 10$, and the values of ${\kappa }_k(G)$ for generalized Petersen graph $GP(n,1)$, where $n\ge 3$ and $3\le k\le 2n$.

The diagnosability of a multiprocessor system is of great significance in measuring the reliability and faulty tolerance of interconnection networks. In this paper, we firstly study the diagnosability of the $n$-dimensional folded hypercube $F{Q}_n(n\ge 4)$ under the PMC model. We prove that $F{Q}_n-F$ keeps the strong local diagnosability property even if it has the set $F$ of $(n-1)$ faulty edges and $n-1$ is maximum number of faulty edges. Secondly, we study the diagnosability of $F{Q}_n$ $(n\ge 5$ and $n$ is odd) with conditional faulty edges under the PMC model. We prove that $F{Q}_n-F$ keeps strong local diagnosability property even if it has the set $F$ of $(3n-4)$ faulty edges, provided that each vertex of $F{Q}_n-F$ is incident with at least two fault-free edges, where $3n-4$ is maximum number of faulty edges. Finally, we prove that $F{Q}_n-F$ keeps strong local diagnosability property no matter how many edges are faulty, provided that each vertex of $F{Q}_n-F$ is incident with at least three fault-free edges.

As a variant of $Q_n$, Huang and Wu in [IEEE Transactions on Computers 46 (1997) 484–490] introduced the balanced hypercube $B{H}_n$ as an interconnection network topology for computing systems. In this paper, we show that $B{H}_n$ is a lexicographic product of two graphs, and using this, we show that every minimum cyclic vertex-cut of $B{H}_n$ isolates a 4-cycle, and prove that the edge neighbor connectivity of $B{H}_n$ is $2n$.

The minimum stretch spanning tree problem for a connected graph $G$ is to find a spanning tree $T$ of $G$ such that the maximum distance in $T$ between two adjacent vertices of $G$ is minimized, where the minimum value is called the tree-stretch of $G$. This paper presents the tree-stretch of a graph constructed by the Cartesian product of two trees. This result is a generalization of the result for the grid graphs obtained by Lin and Lin (L. Lin, Y. Lin, The minimum stretch spanning tree problem for typical graphs, Acta Mathematicae Applicatae Sinica, English Series, 37(3) (2021) 510–522). Then, we give the tree-stretch of the $k$-th power of a tree.