# Are there other interpretations of |G| than |V|, that is |V(G)|?

This may be a basic question, but I'm hoping someone can settle this nagging doubt I'm having. I'm reading up on FPT complexity using a book by Downey and Fellows. It has some introductory examples which detail complexity in terms of $|G|$, which seems to denote $|V|$ as mentioned here.

The sections containing those examples explicitly refer to $|V(G)|$ however, so I wonder if there might be other interpretations of $|G|$ that convey some nuance in terms of complexity I'm missing, or can I safely assume that it does in fact mean $|V|$?

• In general, you can define every size measure you want. Whether it's interesting is another question. If the number is irrelevant for the performance of your algorithms, use |V|; if it's not, you better use |V| + |E| or, outside of complexity theory, express your costs in both quantities. – Raphael Jul 31 '15 at 11:26
• In some obscure cases, it might refer to bit complexity also. In that case, $|G| \approx n \log n + m \log m$. – HdM Jul 31 '15 at 12:19
• Usually $|G|$ denotes the order of the graph, namely the number of vertices. See for instance Diestel. – Pål GD Jul 31 '15 at 12:47

I don't have the book, so I looked through the pages available on Google Scholar. It seems that they use $|G|$ to denote the size of a graph description that is $|V(G)| + |E(G)|$.
For example on page 24 they say that Vertex Cover is solvable in $2^k|G|$ time using bounded search tree method. In fact this method gives $2^kk|V|$ time for graphs with at most $k(|V| - 1)$ edges (it's easy to show that otherwise graph doesn't have Vertex Cover of size $k$). According to this "reverse engineering" $|G|$ corresponds to $k|V|$ that is essentially $|V| + |E|$.