3
$\begingroup$

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

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I'd call it a discrete set, or a discrete space, or a graph without edges. $\endgroup$
    – Ryan Budney
    Commented 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$
    – Yuval Filmus
    Commented Aug 27, 2010 at 4:54

7 Answers 7

Reset to default
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.

Improve this answer
$\endgroup$
6
  • $\begingroup$ should that be $E \in V \times V$ ? $\endgroup$
    – sleepless in beantown
    Commented 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
    Commented 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$
    – sleepless in beantown
    Commented Aug 27, 2010 at 6:53
  • $\begingroup$ And for simple graphs with no loops, $V_1 \ne V_2$ $\endgroup$
    – sleepless in beantown
    Commented 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
    Commented 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.

Improve this answer
$\endgroup$
4
$\begingroup$

Some people call it the empty graph on n vertices.

Improve this answer
$\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$
    – Yuval Filmus
    Commented 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.

Improve this answer
$\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.

Improve this answer
$\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$
    – Theo Johnson-Freyd
    Commented 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$
    – Theo Johnson-Freyd
    Commented 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$
    – Aaron Meyerowitz
    Commented 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$
    – Niel de Beaudrap
    Commented 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
    Commented Aug 26, 2010 at 11:56
3
$\begingroup$

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

Improve this answer
$\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.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .