3
$\begingroup$

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

$\endgroup$
2
  • 2
    $\begingroup$ I'd call it a discrete set, or a discrete space, or a graph without edges. $\endgroup$ Aug 26, 2010 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$ Aug 27, 2010 at 4:54

7 Answers 7

6
$\begingroup$

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.

$\endgroup$
6
  • $\begingroup$ should that be $E \in V \times V$ ? $\endgroup$ Aug 26, 2010 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$
    – Tony Huynh
    Aug 26, 2010 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, 2010 at 6:53
  • $\begingroup$ And for simple graphs with no loops, $V_1 \ne V_2$ $\endgroup$ Aug 27, 2010 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 2-element subsets of $V$. It's not completely standard, but I like it. $\endgroup$
    – Tony Huynh
    Aug 27, 2010 at 9:13
4
$\begingroup$

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.

$\endgroup$
4
$\begingroup$

Some people call it the empty graph on n vertices.

$\endgroup$
1
  • $\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, 2010 at 4:52
4
$\begingroup$

I have seen $\bar{K}_n$ for the graph with n vertices and no edges, but I do not remember where.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
7
  • 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, 2010 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, 2010 at 5:52
  • $\begingroup$ Mainly I just couldn't pass up an opportunity to work in the title of that article. $\endgroup$ Aug 26, 2010 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, 2010 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$
    – Tony Huynh
    Aug 26, 2010 at 11:56
3
$\begingroup$

I have seen it written as $E_n$, where E stands for empty.

$\endgroup$
1
$\begingroup$

Standard notation in graph theory? In category theory the analogous thing can be denoted $disc(V)$ where $V$ is the set of vertices.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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