Three multiply connected Kn-residual graphs. Issue 1 (1st January 2020) - Xu, Kai; Duan, Huiming; Yang, Shihui
ABSTRACT: The K n - residual graph was proposed by P. Erdös, F. Harary and M. Klaw. They also proposed conclusions and conjectures regarding connected m − K n - residual graphs. When m = 1, n ≠ 1, 2, 3, 4, the authors proved that K n + 1 × K 2 is the only connected residual graph with a minimum order. In this paper, we proved that there are three different connected 3 − K 5 - residual graphs with a minimum order of 32, a unique connected 3 − K 6 - residual graph with a minimum order of 33, and a unique connected 3 − K 8 - residual graph with a minimum order of 44, which is not isomorphic to K 11 × K 4 . At the same time, when n ≥ 5, n ≠ 6, we proved that the minimum order of a connected 3 − K n - residual graph is 4 n + 12, and when n ≥ 7, n ≠ 8, K n + 3 × K 4 is the unique smallest connected 3 − K n - residual graph. Therefore, we verified the conjecture about connected 3 − K n - residual graphs. When n ≥ 5, we could obtain the minimum order and specify the corresponding extremal graph of the connected 3 − K n - residual graphs.