Three multiply connected Kn-residual graphs. Issue 1 (1st January 2020)

• Record Type: Journal Article
• Authors: Xu, Kai; Duan, Huiming; Yang, Shihui
• Is Part Of: Journal of Taibah University for science. Volume 14:Issue 1(2020)
• Page Start: 1686
• Page End: 1699
• Publication Date: 2020-01-01
• Subjects: Residual graph -- minimum order -- isomorphic -- extremal graph; Science -- Periodicals; Science; Periodicals; 505
• DOI: 10.1080/16583655.2020.1858603
• Languages: English
• ISSNs: 1658-3655

Abstract

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.