Welcome to MathOverflow

Question

2

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

flag	asked Aug 26 2010 at 3:48 Yuval Filmus 698●6●11

2

I'd call it a discrete set, or a discrete space, or a graph without edges. – Ryan Budney Aug 26 2010 at 4:02

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. – Yuval Filmus Aug 27 2010 at 4:54

Tony Huynh · Accepted Answer · 2010-08-26 08:34:17Z UTC

4

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.

answered Aug 26 2010 at 8:34

Tony Huynh
8,963●1●22●62

	should that be $E \in V \times V$ ? – sleepless in beantown Aug 26 2010 at 14:55
	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. – Tony Huynh Aug 26 2010 at 15:21
	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. – sleepless in beantown Aug 27 2010 at 6:53
	And for simple graphs with no loops, $V_1 \ne V_2$ – sleepless in beantown Aug 27 2010 at 6:55
	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. – Tony Huynh Aug 27 2010 at 9:13

Patrik · Answer 2 · 2010-08-26 04:52:05Z UTC

4

Some people call it the empty graph on n vertices.

answered Aug 26 2010 at 4:52

Patrik
256●1●1●5

That's also what I call it, but I want some notation, like the ones they have for the empty string. – Yuval Filmus Aug 27 2010 at 4:52

Louigi Addario-Berry · Answer 3 · 2010-08-26 04:06:11Z UTC

2

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.

answered Aug 26 2010 at 4:06

Louigi Addario-Berry
3,392●1●11●24

Aaron Meyerowitz · Answer 4 · 2010-08-26 04:26:47Z UTC

2

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.

answered Aug 26 2010 at 4:26

Aaron Meyerowitz
11.5k●1●10●31

1

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. – Theo Johnson-Freyd Aug 26 2010 at 5:49

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. – Theo Johnson-Freyd Aug 26 2010 at 5:52

Mainly I just couldn't pass up an opportunity to work in the title of that article. – Aaron Meyerowitz Aug 26 2010 at 6:11

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. – Niel de Beaudrap Aug 26 2010 at 11:41

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. – Tony Huynh Aug 26 2010 at 11:56

show 2 more comments

Tom Smith · Answer 5 · 2010-08-26 08:26:07Z UTC

1

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

answered Aug 26 2010 at 8:26

Tom Smith
838●1●8●15

Tsuyoshi Ito · Answer 6 · 2010-08-26 11:32:55Z UTC

1

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

answered Aug 26 2010 at 11:32

Tsuyoshi Ito
1,349●6●15

David Roberts · Answer 7 · 2010-08-26 04:37:38Z UTC

0

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

answered Aug 26 2010 at 4:37

David Roberts
11.7k●2●18●55

Notation for a graph without any edges?

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

7 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.