Journal of Interconnection Networks

Connectivity is an important measure parameter to evaluate the fault tolerance of networks. With the continuous expansion of networks scale, it is inevitable that the processor fails. Once the processor fails, the information processed by the failed processor will be unreliable, which may cause fatal consequences. Therefore, it is of great significance to study the connectivity and diagnosability of networks. In this paper, we establish that the $(r+1)$-component connectivity of DQcube is $c{\kappa }_{r+1}(DQ(m,d,n))=-\frac{1}{2}{r}^2+(n+\frac{1}{2})r+1$, where $n\ge 2$ and $1\le r\le n$. Furthermore, we determine that the $(r+1)$-component diagnosability of DQcube is $c{t}_{r+1}(DQ(m,d,n))=-\frac{1}{2}{r}^2+(n-\frac{1}{2})r+n+1$ under the PMC model and the MM* model, where $n\ge 3$ and $1\le r\le n-3$.

Let $G$ be a vertex-colored graph. For a vertex set $S\subseteq V(G)$ of at least two vertices, a tree $T$ that connects $S$ in $G$ is vertex-rainbow if no two vertices of $V(T)\setminus S$ have the same color, such a tree is called a vertex-rainbow $S$-tree or a vertex-rainbow tree connecting $S$. Let $k$ be a fixed integer with $2\le k\le |V(G)|$, $G$ is said to be vertex-rainbow $k$-tree connected if every $k$-subset $S$ of $V(G)$ has a vertex-rainbow $S$-tree. The $k$-vertex-rainbow index $rv{x}_k(G)$ of a graph $G$ is the minimum number of colors are needed in order to make $G$ vertex-rainbow $k$-tree connected. In this paper, we focus on $k=3$. When $G$ is $2$-connected or $2$-edge-connected, we provide a sharp upper bound for $rv{x}_3(G)$, respectively, and determine the graphs $G$, where $rv{x}_3(G)$ reaches the upper bound.

In this paper, we introduce the notion of a finite non-simple directed graph called, an ornated graph. An ornated graph is a directed graph on $n$ vertices, denoted by $O_n(s_l)$, whose vertices are consecutively labeled clockwise on the circumference of a circle and constructed from an ordered string $s_l$. Joining vertices is such that for an odd indexed entry $a_t$ of the string, a tail vertex $v_i$ has clockwise heads $v_j$ if and only if $(i+a_t)\ge j$. For an even indexed entry $a_s$ of the string, a tail vertex $v_i$ has anticlockwise heads $v_j$ if and only if $(i-a_s)\le j$. Some interesting results for certain types of ornated graphs are presented.

Let $D=(V,A)$ be a digraph of order $n$, $S$ a subset of $V$ of size $k$ and $2\le k\le n$. A strong subgraph $H$ of $D$ is called an $S$-strong subgraph if $S\subseteq V(H)$. A pair of $S$-strong subgraphs $D_1$ and $D_2$ is said to be arc-disjoint if $A(D_1)\cap A(D_2)=\varnothing$. Let ${\lambda }_S(D)$ be the maximum number of arc-disjoint $S$-strong subgraphs in $D$. Sun and Gutin defined the strong subgraph $k$-arc-connectivity as

Broadcasting is disseminating information in a network where a specific message must spread to all network vertices as quickly as possible. Finding the minimum broadcast time of a vertex in an arbitrary network is proven to be NP-complete. However, this problem is solvable for a few families of networks. In this paper, we present an optimal algorithm for finding the broadcast time of any vertex in a fully connected tree (${\mathrm{\text{FCT}}}_n$) in $O(|V|loglogn)$ time. An ${\mathrm{\text{FCT}}}_n$ is formed by attaching arbitrary trees to vertices of a complete graph of size $n$ where $\left|V\right|$ is the total number of vertices in the graph.

Large-scale multiprocessor systems or multicomputer systems based on networking have been extensively used in the big data era and social network. Fault tolerance is becoming an essential attribute in multiprocessor systems with the increase of the system scale. For any distinct vertices $u,v\in V$, the local connectivity of $u$ and $v$, denoted by $\kappa (u,v)$, is the maximum number of independent $(u,v)$-paths in system graph $G$. The local edge connectivity of $u$, $v$, $\lambda (u,v)$, is defined similarly. For any $t\in [1,D(G)]$, $d(u,v)=t$, if $\kappa (u,v)$ (or $\lambda (u,v))=min\{d(u),d(v)\}$, then $G$ is $t$-distance optimally (edge) connected, where $D(G)$ is the diameter of $G$ and $d(u)$ is the degree of $u$. For any integers $k$ subject to $0\le k\le t$, if $G$ is $k$-distance optimally (edge) connected, then we call $G$ is $t$-distance local optimally (edge) connected. In this work, we show that $A_{n,k}-A_{n,k}^{n-h,k-h}$ ($A_{n,k}$ is $(n,k)$-arrangement graph) is $2$-distance local optimally edge connected for $n>k+2$ and $1\le h\le k-1$.

One of the significant approaches in implementing the routing of WSNs is clustering that leads to scalability and extending of network lifetime. In the clustered WSN, cluster heads (CHs) utilize maximum energy to another node. Moreover, it balanced the load present in the sensor nodes (SNs) between the CHS for enhancing the network lifespan. Moreover, the CH plays an important part in efficient routing, as well as it must be selected in an optimal way. Thus, this work intends to introduce a cluster-based routing approach in WSN, where it selects the CHs by the optimization algorithm. A new hybrid seagull rock swarm with opposition-based learning (HSROBL) is introduced for this purpose, which is the hybridized concept of rock hyraxes swarm optimization (RHSO) and seagull optimization algorithm (SOA). Further, the optimal CH selection is based on various parameters including distance, security, delay, and energy. At the end, the outcomes of the presented approach are analyzed to extant algorithms based on delay, alive nodes, average throughput, and residual energy, respectively. Based on throughput, alive node, residual energy, as well as delay, the overall improvement in performance is about 28.50%.