Bipartite Graphs $K_{n,n r}-A~(|A|\leq 3)$ Determined by Their Cycle Length Distributions

Abstract:

      The cycle length distribution of a graph $G$ of order $n$ is a sequence $(c_1(G), \dots, c_n(G))$, where $c_i(G)$ is the number of cycles of length $i$ in $G$. In general, the graphs with cycle length distribution $(c_1(G), \dots, c_n(G))$ are not unique. A graph $G$ is determined by its cycle length distribution if the graph with cycle length distribution $(c_1(G), \dots, c_n(G))$ is unique. Let $K_{n,n r}$ be a complete bipartite graph and $A\subseteq E(K_{n,n r})$. In this paper, we obtain: Let $s>1$ be an integer. (1) If $r=2s, n>s(s-1) 2|A|$, then $K_{n,n r}-A\ (A\subseteq E(K_{n,n r}),|A|\leq 3)$ is determined by its cycle length distribution; (2) If $r=2s 1, n>s^2 2|A|$, $K_{n,n r}-A\ (A\subseteq E(K_{n,n r}),|A|\leq 3)$ is determined by its cycle length distribution.