Akademska digitalna zbirka SLovenije - logo
VSE knjižnice (vzajemna bibliografsko-kataložna baza podatkov COBIB.SI)
  • More on almost self-complementary graphs
    Francetić, Nevena ; Šajna, Mateja
    A graph ▫$X$▫ is called almost self-complementary if it is isomorphic to one of its almost complements ▫$X^C - \mathcal{I}$▫, where ▫$X^C$▫ denotes the complement of ▫$X$▫ and ▫$\mathcal{I}$▫ a ... perfect matching (1-factor) in ▫$X^C$▫. If ▫$\mathcal{I}$▫ is a perfect matching in ▫$X^C$▫ and ▫$\varphi : X \to X^C - \mathcal{I}$▫ is an isomorphism, then the graph ▫$X$▫ is said to be fairly almost self-complementary if ▫$\varphi$▫ preserves ▫$\mathcal{I}$▫ setwise, and unfairly almost self-complementary if it does not. In this paper we construct connected graphs of all possible orders that are fairly and unfairly almost self-complementary, fairly but not unfairly almost self-complementary, and unfairly but not fairly almost self-complementary, respectively, as well as regular graphs of all possible orders that are fairly and unfairly almost self-complementary. Two perfect matchings ▫$\mathcal{I}$▫ and ▫$\mathcal{J}$▫ in ▫$X^C$▫ are said to be ▫$X$▫-non-isomorphic if no isomorphism from ▫$X + \mathcal{I}$▫ to ▫$X + \mathcal{J}$▫ induces an automorphism of ▫$X$▫. We give a constructive proof to show that there exists a graph ▫$X$▫ that is almost self-complementary with respect to two ▫$X$▫-non-isomorphic perfect matchings for every even order greater than or equal to four.
    Vir: Discrete mathematics. - ISSN 0012-365X (Vol. 309, iss. 10, 2009, str. 3106-3112)
    Vrsta gradiva - članek, sestavni del
    Leto - 2009
    Jezik - angleški
    COBISS.SI-ID - 15166809

    Povezava(-e):

    http://dx.doi.org/10.1016/j.disc.2008.08.013

vir: Discrete mathematics. - ISSN 0012-365X (Vol. 309, iss. 10, 2009, str. 3106-3112)
loading ...
loading ...
loading ...

Vnos na polico