Is there a standard notation for a graph (on a given set of vertices) without any edges?

2$\begingroup$ I'd call it a discrete set, or a discrete space, or a graph without edges. $\endgroup$– Ryan BudneyAug 26 '10 at 4:02

$\begingroup$ Looking at the answers, I conclude that there is no standard notation. E_n is as close as one gets, but it's too "verbal" for my taste. $\endgroup$– Yuval FilmusAug 27 '10 at 4:54
There are many ways to define a graph, but a pretty standard one is a pair $(V,E)$ where $V$ is a finite set of points and $E \subset \binom{V}{2}$. So, what you are looking for is $(V, \emptyset)$; which would be pretty widely understood.

$\begingroup$ should that be $E \in V \times V$ ? $\endgroup$ Aug 26 '10 at 14:55

$\begingroup$ For directed graphs, $E \subset V \times V$. By graph, I mean a finite simple undirected graph (no loops or multiple edges), although the finiteness condition is not necessary. $\endgroup$ Aug 26 '10 at 15:21

$\begingroup$ Sorry, I'm just not familiar with using the "choose" or "binomial" operator to literally mean "choose" in that way. For an undirected graph, wouldn't an edge consist of an element of the set defined by {$V_1, V_2$} such that $V_1 \in V$ and $V_2 \in V$? I just want to make sure that I understand the notation correctly, because I did not realize that $A \times B$ for sets $A$ and $B$ implied an ordered pair $(a_1, b_1) s.t. a_1 \in A, b_1 \in B$. Thanks for the clarification. $\endgroup$ Aug 27 '10 at 6:53

$\begingroup$ And for simple graphs with no loops, $V_1 \ne V_2$ $\endgroup$ Aug 27 '10 at 6:55

$\begingroup$ Yes, for an undirected graph an edge is just an unordered pair of vertices. So the notation $\binom{V}{2}$ simply means the collection of all 2element subsets of $V$. It's not completely standard, but I like it. $\endgroup$ Aug 27 '10 at 9:13
Some people call it the empty graph on n vertices.

$\begingroup$ That's also what I call it, but I want some notation, like the ones they have for the empty string. $\endgroup$ Aug 27 '10 at 4:52
I don't think there is standard notation for this. If you've already fixed a notation for complement (say a superscript c) then you could use $K_n^c$. But I don't think standard notation exists for this.
I have seen $\bar{K}_n$ for the graph with n vertices and no edges, but I do not remember where.
I suppose $n\cdot K_1$ assuming of course that $n \ge 1$. In the event that there are also no vertices it is sometimes called the Null Graph although F. Harary, F. and R. Read in "Is the Null Graph a Pointless Concept?" suggest that it may be more trouble than it is worth in that it has too many edges to be a tree, no automorphism group etc.

1$\begingroup$ Huh? The totally empty graph definitely is not a tree, as it has too many edges, but the automorphism group is trivial, not nonexistent. There's one way to do nothing to nothing. $\endgroup$ Aug 26 '10 at 5:49

$\begingroup$ Well, let me qualify that. One nice way to count automorphisms is whenever you have a disjoint union of isomorphic things, and each component has automorphism group $G$, then you expect the union to have automorphisms the wreath product $G \wr S_n$. But this is a wrong expectation: it undercounts, for example, when $G$ is itself a disjoint union. So it's not surprising that it overcounts here. The totally empty graph has zero components, and is not itself connected. $\endgroup$ Aug 26 '10 at 5:52

$\begingroup$ Mainly I just couldn't pass up an opportunity to work in the title of that article. $\endgroup$ Aug 26 '10 at 6:11

$\begingroup$ Hm. I would define a tree to be a connected graph lacking cycles; the null graph certainly qualifies, although the connected part is more vacuous than the absence of cycles. Equivalently, between any two distinct vertices you may care to choose in the null graph, there is exactly one path between them. $\endgroup$ Aug 26 '10 at 11:41

1$\begingroup$ Actually, as Theo says there is good reason to consider the null graph as not connected. To see why, check out the article above by Harary and Read; it's quite funny. $\endgroup$ Aug 26 '10 at 11:56
I have seen it written as $E_n$, where E stands for empty.
Standard notation in graph theory? In category theory the analogous thing can be denoted $disc(V)$ where $V$ is the set of vertices.