Search

Given a connected graph |$G$| and a positive integer |$\ell $|⁠ , the |$\ell $| -extra (resp. |$\ell $| -component) edge connectivity of |$G$|⁠ , denoted by |$\lambda ^{(\ell)}(G)$| (resp. |$\lambda _{\ell }(G)$|⁠), is the minimum number of edges whose removal from |$G$| results in a disconnected graph so that every component has more than |$\ell $| vertices (resp. so that it contains at least |$\ell $| components). This naturally generalizes the classical edge connectivity of graphs defined in term of the minimum edge cut. In this paper, we proposed a general approach to derive component (resp. extra) edge connectivity for a connected graph |$G$|⁠. For a connected graph |$G$|⁠ , let |$S$| be a vertex subset of |$G$| for |$G\in \{\Gamma _{n}(\Delta),AG_n,S_n^2\}$| such that |$|S|=s\leq |V(G)|/2$|⁠ , |$G[S]$| is connected and |$|E(S,G-S)|=\min \limits _{U\subseteq V(G)}\{|E(U, G-U)|: |U|=s, G[U]\ \textrm{is connected}\ \}$|⁠ , then we prove that |$\lambda ^{(s-1)}(G)=|E(S,G-S)|$| and |$\lambda _{s+1}(G)=|E(S,G-S)|+|E(G[S])|$| for |$s=3,4,5$|⁠. By exploring the reliability analysis of |$AG_n$| and |$S_n^2$| based on extra (component) edge faults, we obtain the following results: (i) |$\lambda _3(AG_n)-1=\lambda ^{(1)}(AG_n)=4n-10$|⁠ , |$\lambda _4(AG_n)-3=\lambda ^{(2)}(AG_n)=6n-18$| and |$\lambda _5(AG_n)-4=\lambda ^{(3)}(AG_n)=8n-24$|⁠ ; (ii) |$\lambda _3(S_n^2)-1=\lambda ^{(1)}(S_n^2)=4n-8$|⁠ , |$\lambda _4(S_n^2)-3=\lambda ^{(2)}(S_n^2)=6n-15$| and |$\lambda _5(S_n^2)-4=\lambda ^{(3)}(S_n^2)=8n-20$|⁠. This general approach maybe applied to many diverse networks. [ABSTRACT FROM AUTHOR]

A connected graph |$G$| is called strongly Menger (edge) connected if for any two distinct vertices |$x,y$| of |$G$|⁠ , there are |$\min \{\textrm{deg}_G(x), \textrm{deg}_G(y)\}$| internally disjoint (edge disjoint) paths between |$x$| and |$y$|⁠. Motivated by parallel routing in networks with faults, Oh and Chen (resp. Qiao and Yang) proposed the (fault-tolerant) strong Menger (edge) connectivity as follows. A graph |$G$| is called |$m$| -strongly Menger (edge) connected if |$G-F$| remains strongly Menger (edge) connected for an arbitrary vertex set |$F\subseteq V(G)$| (resp. edge set |$F\subseteq E(G)$|⁠) with |$|F|\leq m$|⁠. A graph |$G$| is called |$m$| -conditional strongly Menger (edge) connected if |$G-F$| remains strongly Menger (edge) connected for an arbitrary vertex set |$F\subseteq V(G)$| (resp. edge set |$F\subseteq E(G)$|⁠) with |$|F|\leq m$| and |$\delta (G-F)\geq 2$|⁠. In this paper, we consider strong Menger (edge) connectedness of the augmented |$k$| -ary |$n$| -cube |$AQ_{n,k}$|⁠ , which is a variant of |$k$| -ary |$n$| -cube |$Q_n^k$|⁠. By exploring the topological proprieties of |$AQ_{n,k}$|⁠ , we show that |$AQ_{n,3}$| (resp. |$AQ_{n,k}$|⁠ , |$k\geq 4$|⁠) is |$(4n-9)$| -strongly (resp. |$(4n-8)$| -strongly) Menger connected for |$n\geq 4$| (resp. |$n\geq 2$|⁠) and |$AQ_{n,k}$| is |$(4n-4)$| -strongly Menger edge connected for |$n\geq 2$| and |$k\geq 3$|⁠. Moreover, we obtain that |$AQ_{n,k}$| is |$(8n-10)$| -conditional strongly Menger edge connected for |$n\geq 2$| and |$k\geq 3$|⁠. These results are all optimal in the sense of the maximum number of tolerated vertex (resp. edge) faults. [ABSTRACT FROM AUTHOR]

For an integer |$\ell \geqslant 2$|⁠ , the |$\ell $| -component connectivity (resp. |$\ell $| -component edge connectivity) of a graph |$G$|⁠ , denoted by |$\kappa _{\ell }(G)$| (resp. |$\lambda _{\ell }(G)$|⁠), is the minimum number of vertices (resp. edges) whose removal from |$G$| results in a disconnected graph with at least |$\ell $| components. The two parameters naturally generalize the classical connectivity and edge connectivity of graphs defined in term of the minimum vertex-cut and the minimum edge-cut, respectively. The two kinds of connectivities can help us to measure the robustness of the graph corresponding to a network. In this paper, by exploring algebraic and combinatorial properties of |$n$| -dimensional balanced hypercubes |$BH_n$|⁠ , we obtain the |$\ell $| -component (edge) connectivity |$\kappa _{\ell }(BH_n)$| (⁠|$\lambda _{\ell }(BH_n)$|⁠). For |$\ell $| -component connectivity, we prove that |$\kappa _2(BH_n)=\kappa _3(BH_n)=2n$| for |$n\geq 2$|⁠ , |$\kappa _4(BH_n)=\kappa _5(BH_n)=4n-2$| for |$n\geq 4$|⁠ , |$\kappa _6(BH_n)=\kappa _7(BH_n)=6n-6$| for |$n\geq 5$|⁠. For |$\ell $| -component edge connectivity, we prove that |$\lambda _3(BH_n)=4n-1$|⁠ , |$\lambda _4(BH_n)=6n-2$| for |$n\geq 2$| and |$\lambda _5(BH_n)=8n-4$| for |$n\geq 3$|⁠. Moreover, we also prove |$\lambda _\ell (BH_n)\leq 2n(\ell -1)-2\ell +6$| for |$4\leq \ell \leq 2n+3$| and the upper bound of |$\lambda _\ell (BH_n)$| we obtained is tight for |$\ell =4,5$|⁠. [ABSTRACT FROM AUTHOR]

In this paper, we determine the wide diameters of regular hyper-stars HS(2k, k) and folded hyper-stars FHS(2k, k). We first provide a connection between the wide diameter and the maximum height of a set of particular spanning trees, called independent spanning trees (ISTs for short), of a graph. According to this relation, we analyze the heights of ISTs constructed in the previous works to establish upper bounds of the wide diameters of HS(2k, k) and FHS(2k, k). By contrast, we take the known results of fault diameters of HS(2k, k) and FHS(2k, k) as lower bounds. Consequently, we obtain the following results: (i) Dw (HS(2k, k)) = 2k + 1 for k ≥ 2, and (ii) Dw (FHS(4, 2)) = 3 and Dw (FHS(2k, k)) = k + 2 for k ≥ 3, where Dw (G) stands for the wide diameter of a graph G. The latter gives the answer of a question arisen from a previous work [(2015) Pruning longer branches of ISTs on folded hyper-stars, Comput. J., 58, 2972-2981]. In addition, we ascertain that all ISTs of HS(2k, k) and FHS(2k, k) constructed in the previous works are optimal in the sense that their heights are minimized. [ABSTRACT FROM AUTHOR]

A set of k spanning trees rooted at the same vertex r in a graph G is called independent [and the trees are called independent spanning trees (ISTs)] if, for any vertex x ≠ r, the k paths from x to r, one path in each tree, are internally disjoint. The design of ISTs on graphs has applications to fault-tolerant broadcasting and secure message distribution in networks. It was conjectured that, for any k-connected graph, there exist k ISTs rooted at any vertex of the graph. The conjecture has been proved true for k-connected graphs with k ≤ 4, and remains open otherwise. In this paper, we deal with the problem of constructing ISTs on the Cartesian product of a sequence of hybrid graphs, including cycles and complete graphs. Consequently, this result generalizes a number of previous works. Moreover, the construction is shown to be optimal in the sense that the heights of ISTs are minimized. [ABSTRACT FROM AUTHOR]

A t-ary tree is a rooted tree such that every internal node has exactly t disjoint subtrees. Recently, a concise representation called right-distance sequences (RD-sequences) was introduced to represent t-ary trees and their generalization called non-regular trees. In particular, a loopless algorithm has been proposed by Wu et al. ((2010) Loopless generation of non-regular trees with a prescribed branching sequence. Comput. J., 53, 661–666) for generating non-regular trees (and thus of t-ary trees) encoded by RD-sequences in a Gray-code order. In this paper, based on such a Gray-code order, we present efficient ranking and unranking algorithms of t-ary trees with n internal nodes. The time complexity and space requirement in both algorithms are O(max{n2,tn}) and O(tn), respectively. As a by-product, we have an improvement on ranking and unranking t-ary trees encoded by z-sequences in a Gray-code order. [ABSTRACT FROM PUBLISHER]