The clique partition edge-fault numbers of some networks

Abstract

In a graph $G$, a clique partition of $G$ is a partition $\mathcal{P}=\{V_1,V_2,\cdots,V_q\}$ of $V(G)$ such that the induced subgraph $G[V_i]$ is a clique (called a clique of $\mathcal{P}$) for each $i\in [q]$. If a clique partition $\mathcal{P}$ also satisfies that $|G[V_i]|=t$ for each $i\in [q]$, the graph $G$ is called a $K_t$-partitionable graph. A $K_t$-partition edge-fault set of $G$ is a subset $F$ of $E(G)$ whose deletion leaves the resulting graph with no $K_t$-partitions. The $K_t$-partition edge-fault number of $G$ is the smallest size among all $K_t$-partition edge-fault sets of $G$, denoted by $f_t(G)$. The $K_t$-preclusion number of $G$, denoted by $g_t(G)$ is the minimum size of edge subset $A$ such that there exists one vertex of $G$ which is not in any clique $K_t\subseteq G-A$.
  In this paper, we prove that arrangement graphs and data center networks are clique partitionable. Furthermore, arrangement graphs are clique decomposable. The exact values of $f_t(G)$ such as $f_{n-k+1}(A_{n,k})$ and the bounds of $f_{t}(A_{n,k})$ and $f_{t}(K_n)$ for some $t$ are gotten. Furthermore, the exact values of $g_3(G)$ for the maximal planar graph $G$, $g_r(T(n,r))$ and $f_t(G)$ of arrangement graphs $A_{n,k}$ shrinking a partition for some $t$ are derived.