کد مقاله | کد نشریه | سال انتشار | مقاله انگلیسی | نسخه تمام متن |
---|---|---|---|---|
4651269 | 1342529 | 2006 | 17 صفحه PDF | دانلود رایگان |

A graph is called almost self-complementary if it is isomorphic to one of its almost complements Xc-IXc-I, where XcXc denotes the complement of X and II a perfect matching (1-factor) in XcXc. Almost self-complementary circulant graphs were first studied by Dobson and Šajna [Almost self-complementary circulant graphs, Discrete Math. 278 (2004) 23–44]. In this paper we investigate some of the properties and constructions of general almost self-complementary graphs. In particular, we give necessary and sufficient conditions on the order of an almost self-complementary regular graph, and construct infinite families of almost self-complementary regular graphs, almost self-complementary vertex-transitive graphs, and non-cyclically almost self-complementary circulant graphs.
Journal: Discrete Mathematics - Volume 306, Issue 1, 28 January 2006, Pages 107–123