Completion Number of a Graph

In this paper a new concept of partial complement of a graph G is introduced and using the same a new graph parameter, called completion number of a graph G, denoted by c(G) is defined. Some basic properties of graph parameter, completion number, are studied and upperbounds for completion number of classes of graphs are obtained , the paper includes the characterization also.

• Sudhakar G

• Completion Number
• Maximum Independent subset
• Partial complements
• Partial self complementary

[1] R.A Gibbs, Self-complimentary graphs.,J. Combi.Theory(B)16,(1974)106-
123 MR 50:188.
[2] M.J Colbourn and C.J Colbourn, Graph isomorphism and self-
complimentary graphs.,SIGACT,News 10(1978)25-29.
[3] S.B Rao, On Regular and strongly regular self-complimentary
graphs.,Discrete Mathematics 54(1985) 73-82.
[4] S.B Rao Habbari γ -partite self-complimentary graphs technical report
no ., 15/77, ISI ,Calcutta(1977).
[5] F. Harary., Graph Theory,Addison wiley series in mathematics, Adison-
Wiley Publishing company,(1969)