Search

Let $S\subseteq V(G)$ and $\pi_{G}(S)$ denote the maximum number $t$ of edge-disjoint paths $P_{1},P_{2},\ldots,P_{t}$ in a graph $G$ such that $V(P_{i})\cap V(P_{j})=S$ for any $i,j\in\{1,2,\ldots,t\}$ and $i\neq j$. If $S=V(G)$, then $\pi_{G}(S)$ is the maximum number of edge-disjoint spanning paths in $G$. It is proved [Graphs Combin., 37 (2021) 2521-2533] that deciding whether $\pi_G(S)\geq r$ is NP-complete for a given $S\subseteq V(G)$. For an integer $r$ with $2\leq r\leq n$, the $r$-path connectivity of a graph $G$ is defined as $\pi_{r}(G)=$min$\{\pi_{G}(S)|S\subseteq V(G)$ and $|S|=r\}$, which is a generalization of tree connectivity. In this paper, we study the $3$-path connectivity of the $k$-dimensional data center network with $n$-port switches $D_{k,n}$ which has significate role in the cloud computing, and prove that $\pi_{3}(D_{k,n})=\lfloor\frac{2n+3k}{4}\rfloor$ with $k\geq 1$ and $n\geq 6$.

The recently proposed RCube network is a cube-based server-centric data center network (DCN), including two types of heterogeneous servers, called core and edge servers. Remarkably, it takes the latter as backup servers to deal with server failures and thus achieve high availability. This paper first points out that RCube is suitable as a candidate topology of DCNs for edge computing. Three transmission types are among core and edge servers based on the demand for applications' computation and instant response. We then employ protection routing to analyze the transmission failure of RCube DCNs. Unlike traditional protection routing, which only tolerates a single link or node failure, we use the multi-protection routing scheme to improve fault-tolerance capability. To configure a protection routing in a network, according to Tapolcai's suggestion, we need to construct two completely independent spanning trees (CISTs). A logic graph of RCube, denoted by $L$-$RCube(n,m,k)$, is a network with a recursive structure. Each basic building element consists of $n$ core servers and $m$ edge servers, where the order $k$ is the number of recursions applied in the structure. In this paper, we provide algorithms to construct $\min\{n,\lfloor(n+m)/2\rfloor\}$ CISTs in $L$-$RCube(n,m,k)$ for $n+m\geqslant 4$ and $n>1$. From a combination of the multiple CISTs, we can configure the desired multi-protection routing. In our simulation, we configure up to 10 protection routings for RCube DCNs. As far as we know, in past research, there were at most three protection routings developed in other network structures. Finally, we summarize some crucial analysis viewpoints about the transmission efficiency of DCNs with heterogeneous edge-core servers from the simulation results., Comment: 22 pages, 12 figures

Bubble-sort star graphs are a combination of star graphs and bubble sort graphs. They are bipartite graphs and also form a family of Cayley graphs. The decycling number of a graph is the minimum number of vertices whose removal from the graph results in an acyclic subgraph. In this paper, we prove the decycling number D(n) of an n-dimensional bubble-sort star graph for n <= 5. We also show D(n) satisfies the inequalities for n >= 6., Comment: 6 pages, 2 figures, conference paper published in 2017

A connected graph $G$ is called strongly Menger (edge) connected if for any two distinct vertices $x,y$ of $G$, there are $\min \{{\rm deg}_G(x), {\rm deg}_G(y)\}$ vertex(edge)-disjoint paths between $x$ and $y$. 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}$ for $n\geq 4$ (resp.\ $AQ_{n,k}$ for $n\geq 2$ and $k\geq 4$) is still strongly Menger connected even when there are $4n-9$ (resp.\ $4n-8$) faulty vertices and $AQ_{n,k}$ is still strongly Menger edge connected even when there are $4n-4$ faulty edges for $n\geq 2$ and $k\geq 3$. Moreover, under the restricted condition that each vertex has at least two fault-free edges, we show that $AQ_{n,k}$ is still strongly Menger edge connected even when there are $8n-10$ faulty edges 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., Comment: 18 pages, 4 figures

For an integer $\ell\geqslant 2$, the $\ell$-component connectivity of a graph $G$, denoted by $\kappa_{\ell}(G)$, is the minimum number of vertices whose removal from $G$ results in a disconnected graph with at least $\ell$ components or a graph with fewer than $\ell$ vertices. This is a natural generalization of the classical connectivity of graphs defined in term of the minimum vertex-cut and is a good measure of robustness for the graph corresponding to a network. So far, the exact values of $\ell$-connectivity are known only for a few classes of networks and small $\ell$'s. It has been pointed out in~[Component connectivity of the hypercubes, Int. J. Comput. Math. 89 (2012) 137--145] that determining $\ell$-connectivity is still unsolved for most interconnection networks, such as alternating group graphs and star graphs. In this paper, by exploring the combinatorial properties and fault-tolerance of the alternating group graphs $AG_n$ and a variation of the star graphs called split-stars $S_n^2$, we study their $\ell$-component connectivities. We obtain the following results: (i) $\kappa_3(AG_n)=4n-10$ and $\kappa_4(AG_n)=6n-16$ for $n\geqslant 4$, and $\kappa_5(AG_n)=8n-24$ for $n\geqslant 5$; (ii) $\kappa_3(S_n^2)=4n-8$, $\kappa_4(S_n^2)=6n-14$, and $\kappa_5(S_n^2)=8n-20$ for $n\geqslant 4$.

The $\ell$-component connectivity (or $\ell$-connectivity for short) of a graph $G$, denoted by $\kappa_\ell(G)$, is the minimum number of vertices whose removal from $G$ results in a disconnected graph with at least $\ell$ components or a graph with fewer than $\ell$ vertices. This generalization is a natural extension of the classical connectivity defined in term of minimum vertex-cut. As an application, the $\ell$-connectivity can be used to assess the vulnerability of a graph corresponding to the underlying topology of an interconnection network, and thus is an important issue for reliability and fault tolerance of the network. So far, only a little knowledge of results have been known on $\ell$-connectivity for particular classes of graphs and small $\ell$'s. In a previous work, we studied the $\ell$-connectivity on $n$-dimensional alternating group networks $AN_n$ and obtained the result $\kappa_3(AN_n)=2n-3$ for $n\geqslant 4$. In this sequel, we continue the work and show that $\kappa_4(AN_n)=3n-6$ for $n\geqslant 4$.

AT-free graphs are characterized by vertex elimination orders. We show that these AT-free orders of a graph can be generated in constant amortized time., Comment: 9 pages, 1 figures. A preliminary version appeared in the Proceedings of the International Workshop on Combinatorial Algorithms (IWOCA 2015) pp. 77-87