<i>δ</i>-Complement of a Graph

Abstract

Let G(V,X) be a finite and simple graph of order n and size m. The complement of G, denoted by G¯, is the graph obtained by removing the lines of G and adding the lines that are not in G. A graph is self-complementary if and only if it is isomorphic to its complement. In this paper, we define δ-complement and δ′-complement of a graph as follows. For any two points u and v of G with degu=degv remove the lines between u and v in G and add the lines between u and v which are not in G. The graph thus obtained is called δ-complement of G. For any two points u and v of G with degu≠degv remove the lines between u and v in G and add the lines between u and v that are not in G. The graph thus obtained is called δ′-complement of G. The graph G is δ(δ′)-self-complementary if G≅Gδ(G≅Gδ′). The graph G is δ(δ′)-co-self-complementary if Gδ≅G¯(Gδ′≅G¯). This paper presents different properties of δ and δ′-complement of a given graph.

Keywords

• <i>δ</i>-complement
• <i>δ</i>′-complement
• self-complementary
• degree sequence