Complement graph: Difference between revisions

Revision as of 09:33, 5 July 2009

Revision as of 10:41, 5 July 2009

Line 10:

* for a [[clique (graph theory)|clique]] <math>K^n(V_K, E_K)</math> of <math>n = |V_G|</math> vertices, <math>E_H = E_K \setminus E_G</math>.

==Applications==

The '''complement graph''' is used in several graph theories and demonstrations, such as the [[Ramsey theory]], and different reductions for proofs of [[NP complete|NP-Completeness]].

==References==

* {{citation

| last1=Bondy | first1=John Adrian | authorlink1=John Adrian Bondy

| last2=Murthy | first2=U. S. R. | authorlink2=U. S. R. Murthy

| title=Graph Theory with Applications

| year=1976

| publisher=North-Holland

| isbn=0-444-19451-7

| url=http://www.ecp6.jussieu.fr/pageperso/bondy/books/gtwa/gtwa.html

}}, pages 6 and 29.

*{{Citation

| last=Diestel | first=Reinhard

| title=Graph Theory

| publisher=[[Springer Science+Business Media|Springer]]

| year=2005

| edition=3rd

| isbn=3-540-26182-6

}}. [http://www.math.uni-hamburg.de/home/diestel/books/graph.theory/ Electronic edition], page 4.

[[Category:Graph operations]]