Talk:Dense graph

Definition of "sparse graph"

I removed the following from the article:

"Bruno Preiss' definition of sparse and dense graphs has problems, but may help. First, for one graph, one can always choose a k. Second a class of graphs might be considered sparse if |E| = O(|V|k) and 2 > k > 1. |E| is the number of edges, and |V| is the number of vertices."

Firstly, it is not clear what Bruno Preiss' definition is. Secondly, the definition is probably wrong; I guess that |E| = O(|V|k) should be |E| = O(|V|^k), but I'm not sure. -- Jitse Niesen (talk) 16:27, 29 September 2005 (UTC)

A simple web search answered my question: the article was copied from the NIST website. The article really should include a reference to the original source to avoid charges of plagiarism, even when there are no copyright issues. -- Jitse Niesen (talk) 16:49, 29 September 2005 (UTC)

Sparse Matrix

One possible definition of a sparse graph is one which can be represented by a sparse matrix. The definition of a sparse graph is often application dependent. A rather simple one is that it has O(|V|) edges. Let's look again at the first example graph:

An edge is a self-loop if it is of the form (u,u). The sample graph contains no self-loops.

A graph is simple if it neither contains self-loops nor contains an edge that is repeated in E. A graph is called a multigraph if it contains a given edge more than once or contain self-loops. For our discussions, graphs are assumed to be simple. The example graph is a simple graph.

An edge (u,v) is incident to both vertex u and vertex v. For example, the edge (1,3) is incident to vertex 3.

The degree of a vertex is the number of edges which are incident to it. For example, vertex 3 has degree 3, while vertex 4 has degree 1.

Vertex u is adjacent to vertex v if there is some edge to which both are incident (that is, there is an edge between them). For example, vertex 2 is adjacent to vertex 5.

A graph is said to be sparse if the total number of edges is small compared to the total number possible ((N x (N-1))/2) and dense otherwise. For a given graph, whether it is dense or sparse is not well-defined by garin

definition correct?

Is the definition really correct? Applying the current definition means that it is impossible to have a graph density of 1. For full graphs, the limit of the density is 1 as the order approaches infinity, but that's a little different Citrus538 09:44, 20 July 2007 (UTC)

I'm going to change the definition in a few days if nobody objects. Citrus538 04:06, 27 July 2007 (UTC)

It's a good point you raise. The first paper I found which defines graph density has another definition which meets your concern, so I replace the unreferenced definition in the article with their definition. If you have a better references, for instance, a text book, then please put it in. -- Jitse Niesen (talk) 14:09, 28 July 2007 (UTC)

Great! I was just gonna wing it without any references : ) Anyway, I added that the definition applies only for undirected graphs. 68.221.99.78 03:38, 4 August 2007 (UTC)

Ooops, forgot to log in. That last comment is mine. Citrus538 03:39, 4 August 2007 (UTC)

Preiss definition of sparse graph

I removed the sentence:

"One possibility is to choose a number k with 1 < k < 2 and to define a sparse graph to be a graph with |E| = O(|V|^k), where |E| denotes the number of edges, |V| the number of vertices, and the letter O refers to the Big O notation (Preiss 1998, p. 534)."

This definition does not make any sense at all. The big-O notation is defined on functions. However, for a single graph, the number of nodes and the number of edges are constants (costant functions). That means that, according to the definition, any graph is sparse for any choice of k (because any constant is bigger than any other constant by only a constant factor). The source where the definition seems to directly originate, the NIST site, talks about classes of graphs, which makes more sense, but still the notation is awkward and non-standard. The NIST site refers to a web version of a book by Preiss. Both the NIST site and Preiss' book are not about graph theory. Hoopje (talk) 15:44, 29 April 2011 (UTC)