Completion Number of a Graph

Authors: Sudhakar G

Abstract:

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.

Keywords: Completion Number, Maximum Independent subset, Partial complements, Partial self complementary

Digital Object Identifier (DOI): doi.org/10.5281/zenodo.1071290

References:

[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)