There is no standard definition of de Bruijn graphs (dbgs) in the bioinformatics literature. Multiple papers define it multiple ways. However, there is always an implicit set of equal length strings as input (denote this length by p). For example, if your input is a set of reads of length greater than p, then the implicit input is the set of all p-mers in the reads.

I think the definitions of dbgs in bioinformatics boil down to one of two versions: 1) The edge-centric de Bruijn graph of order p: The nodes are (p-1)-mers in the input, and the edges are all the p-mers in the input. In other words: if we take any two nodes x and y that overlap by p-2, we can merge them together to obtain a p-mer. If that p-mer is in the input, then there is an edge in the graph. Note in this case, there might be nodes that overlap by p - 2 but do not have an edge between them.

2) The node-centric de Bruijn graph of order p: The nodes are the p-mers in the input, and there is an edge between two nodes (i.e. p-mers) if and only if they overlap by p-1.

I am not sure if the terms node-centric and edge-centric are standard, but we've been using them in our papers because they make explicit the distinction between the two graphs.

There can also be confusion in the way people use the value k. For example, sometimes, the authors define a dbg with nodes as k-1 mers and edges for any k-2 overlap between nodes. This is really defining a node centric dbg with p=k-1. Or, people will define a dbg with nodes as k-mers and an edge between two nodes if they overlap by k-1 and their merging leads to a (k+1)-mer in the input. This is really the edge-centric dbg with p=k+1.

To distinguish which type of graph is being used, check if the definition of the edge-set relies strictly on the vertex labels (then, this is a node centric dbg) or if it is using information that is not contained in the node labels (then it is an edge-centric graph). Then, figure out how their value of k relates to the value of p above.

Finally, it should be noted that there is a third definition of dbgs that is not used in bioinformatics but comes from mathematics and predates the definitions above. In this definition, the dbg of order p is the node centric dbg of order p, defined on the universe of all p-mers. That is, all possible strings of length p are in the graph. For this third definition of a dbg, there is no input sequence.

Most typically, the de Bruijn graph is considered to be built with the k-mers as edges [clarification: As Heng Points out below, the k-mers actually represent an "edge" and both endpoints. Technically, the graph is on (k-1)-mers (nodes), which share an edge (k-2)-mer, where a length (k-2) suffix of one is a length (k-2) prefix of the other]. Then, each (k-2)-mer edge links two vertices which represent the "left" and "right" (k-1)-mers of this k-mer. This representation has a number of benefits. For example, the set of k-mers in the input can act as a representation of the dBG (since it is, essentially, the edge list of the graph). This, in turn, leads to efficient representations in terms of things like cascading Bloom filters. The edge list becomes a sufficient representation of the the graph. To navigate in this structure (given some initial (k-1)-mer), you can query to see which edges are present by extending this (k-1)-mer to the left or right by a single nucleotide. This produces a k-mer which you can then use to query the edge set. It's worth noting that I have seen implementations of the dBG in terms of the node set (i.e. the "node-centric" representation), but the edge-based representation is what I've seen occur most frequently in exposition and implementation.

On the other bioinfo Q&A, one of the best questions is about the difference between mathematical and bioinformatics de Bruijn graphs. That question made me think a lot. Here are some of my reflections.

According to wiki, in a k-order "mathematical" de Bruijn graph over alphabet {A,C,G,T}, each vertex is a k-mer; there is an edge between two k-mers if and only if they have a (k-1)-bp overlap. Each edge can be uniquely identified by a (k+1)-mer and vice versa. As such, this graph always has 4^k vertices and 4^{k+1} edges. In the following, I will call this a full de Bruijn graph.

In the context of sequence assembly, we have a set of reads as input. The k-order assembly de Buijn graph derived from the reads is strictly a subgraph of the full graph. It is either edge-induced from (k+1)-mers present in the input, or vertex-induced from k-mers. Vertex-induced and edge-induced graphs are different, though: vertex-induction requires at least (k-1)-bp overlap between reads while edge-induction requires at least k-bp overlap – edge-induced graph is smaller.

Here is an example. Say we have two 3-bp reads {ACC,CCG} and want to construct a 3-order assembly graph. If we use edge-induction, the graph is empty because there are no 4-mers in reads. If we use vertex-induction, the graph is "ACC=>CCG" because inducing the two vertices automatically induces the edge between them.

Back to the original question. Mathematically, a k-order assembly de Buijn graph is a subgraph of the full k-order de Bruijn graph. As such, in the assembly graph, vertices are k-mers. What vertices and edges are present in this subgraph depends on how the graph is constructed: by edge-induction or by vertex-induction. In implementation, we keep a list of (k+1)-mers as a succinct representation of an edge-induced graph; we keep a list of k-mers for a vertex-induced graph. Both ways work if we just want to derive unitigs. I haven't implemented a de Bruijn graph assembler myself. I don't know which way is more convenient in practice. However, if we want to apply a Euler traversal, probably the edge-induced graph makes more sense. The extra edges in the vertex-induced graph might fail the traversal (not so sure!).

PS: my reflections are broadly in line with Paul's answer, except that the definition of "order" is different. I am defining "order" as in the original de Bruijn graph; Paul is essentially taking "order" as the length of k-mers used to succinctly store the graph.

EDIT: according to wiki, a k-order full de Bruijn graph is the line graph of a (k-1)-order de Bruijn graph. I think this property still holds for assembly de Bruijn graphs. We note that a list of k-mers is a succinct representation of a vertex-induced k-order graph AND of an edge-induced (k-1)-order graph. It actually doesn't matter how we induce graph. The final assembly will be the same either way. This duality is also interesting in that if there is a Euler path in an edge-induced (k-1)-order graph, there will be a Hamilton path in the vertex-induced k-order graph.

Each node is a k-mer. Adjacent k-mers overlap over a length of k-1. This means that navigating along each path, you'll move one base at a time with your reading frame size remaining at k.

I was mistaken. Please check out Rob's answer.