Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

What is the term for a graph comprised of $n$ pairwise disconnected vertices?

I could call these $1$-colorable graphs or something like that, but I would rather use standard terminology if it exists.

Also is there a notation to go along with the name? For example $C_n$ generally denotes cycle graphs.

share|improve this question
2  
In England, if they are on your face they are called spots. –  Will Jagy Mar 4 '13 at 23:09
3  
I think the answers to this question should be helpful. –  Adrián Barquero Mar 4 '13 at 23:11
    
@AdriánBarquero I see, so there is no consistency in notation either. Thanks. –  Alexander Gruber Mar 4 '13 at 23:21
    
Obviously $G = (V,\varnothing)$ would be some solution, you could also try "complement of clique $K_n$". –  dtldarek Mar 4 '13 at 23:21
    
@dtldarek Yeah: I think I might go for $\overline{K_n}$. –  Alexander Gruber Mar 4 '13 at 23:48

3 Answers 3

up vote 1 down vote accepted

The standard terminology is to call it the empty graph. Let me quote from the text [Bollobas, Modern Graph Theory, p.3], where he calls it the "empty graph": ``As $E_n$ is rather close to the notation for the edge set of a graph, we frequently use $\overline{K}_n$ for the empty graph of order $n$, signifying that it is the complement of the complete graph. In general, for a graph $G=(V,E)$ the complement of $G$ is $\overline{G}=(V,V^{(2)}-E)$; thus, two vertices are adjacent in $\overline{G}$ if and only if they are not adjacent in G.''

share|improve this answer

According to Wikipedia:

If it is a graph with no edges and any number $n$ of vertices, it may be called the null graph on $n$ vertices. (There is no consistency at all in the literature.)

You didn’t ask about notation, as distinct from terminology, but if the context is simple graphs, I’d denote it by $\langle[n],\varnothing\rangle$ or, if a different vertex set was wanted, $\langle V,\varnothing\rangle$ for the appropriate $V$.

share|improve this answer
    
Ouch, I must have missed that. Thanks. –  Alexander Gruber Mar 4 '13 at 23:20
    
@Alexander: It’s pretty well buried on the page. I found it only because I did a Google search on "graph with no edges". –  Brian M. Scott Mar 4 '13 at 23:26
3  
There is not a lot of consistency I agree. But the I think the usual convention is that the null graph has no vertices; a graph with no edges is empty. (There's a paper by Harary and Schwenk "Is the null graph a pointless concept?" which goes some way to establishing the notation.) I'd be wary about accepting wikipedia as an authority on notation. –  Chris Godsil Mar 5 '13 at 3:05

In "Introduction to Graph Theory", Douglas B. West calls a graph with no edges a "trivial graph". If it has no edges and no vertices, it's a "null graph".

There is no standardized terminology in graph theory. For this reason, many authors spend a few extra words precisely defining the terminology they use.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.