On almost self-complementary graphs |
| |
Authors: | Primo? Poto?nik |
| |
Institution: | Department of Mathematics and Statistics, University of Ottawa, 585 King Edward Avenue, Ottawa, Ont., Canada K1N 6N5 |
| |
Abstract: | A graph is called almost self-complementary if it is isomorphic to one of its almost complements Xc-I, where Xc denotes the complement of X and I a perfect matching (1-factor) in Xc. 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. |
| |
Keywords: | Self-complementary graph Almost self-complementary graph Homogeneously almost self-complementary graph Non-cyclically almost self-complementary circulant graph Isomorphic factorization Homogeneous factorization |
本文献已被 ScienceDirect 等数据库收录! |
|