Talk:Complement graph

The first and the second bullet in the examples are saying the same thing using different words. We should remove the one or the other. Leaving them like they are now would be confusing. Vitalij zad (talk) 09:54, 1 September 2012 (UTC)[reply]

I think they're different enough to stay. One is about what happens when the whole graph is edgeless or complete; the other is about what happens to subgraphs within the graph. —David Eppstein (talk) 15:50, 1 September 2012 (UTC)[reply]

Simple graphs only?

Is it the case that the concept of a complement graph makes sense for simple graphs only?

It's clear that the complement is a simple graph, because the complement never connects a vertex to itself, nor does it feature two or more edges between the same pair of vertices.

Must the input graph to the complement operation also be simple?

In terms of an adjacency matrix representation, must the input matrix just have 1's and 0's, with an all zero diagonal?

If so, we can also describe the complement in terms of the adjacency matrix representation:

the diagonal zeros stay zero
all other entries flip from 0 to 1 and vice versa

216.31.219.19 (talk) 19:42, 18 December 2013 (UTC)[reply]

I think in order to have some other nice properties (in particular that the complement of a complement is the original graph) it's necessary to assume that the input graph is simple. —David Eppstein (talk) 19:50, 18 December 2013 (UTC)[reply]