categories: Re: Unlabeled graphs

[Eduardo Dubuc <edubuc@math.uqam.ca>]

this is in reply to Charles Wells, I quote in between  ' " '

" Major point:  Any way you store an unlabeled graph in a computer will
involve a memory location for each node, and so introduces a labeling,
indeed a total ordering, on the nodes.  However, a high level language
with pointers such as C can be used to describe the structure without any
names being given explicitly.  The structure head will point to a node,
which will have a pointer
to another node, etc, and the program text will not mention all the nodes
directly.  For the purpose of computing with the graph, you can have the
program traverse the nodes without naming them.  This is a commonly used
technique.  (There will have to be pointer structures for the edges with
pointers to the two nodes each is incident on.)  When the program is
compiled, the nodes are made to correspond to memory locations but the
locations are hidden from the user.  It seems to me that this preserves
the psychology of a drawing with no labels on the nodes. "

quite wright, i agree that the technique you describe "preserves the
psychology of a drawing with no labels on the nodes. ".

 i had no thought about the pointer technique  !!!

but then, try to put an unlabeled graph in a computer using assembler
languge  !

is what i should have said !

" You can respond that each node has an implicit label, essentially an
integer, which is the number of pointers you have to dereference to get to
the node. But that is just like saying that in the drawing of the graph on
a piece of paper, each node has an implicit label, namely its location on
the paper. If you allow implicit labels like this the drawing has them and
so does the graph in the computer.  If you don't allow them then neither
has labels.

Let me forestall someone bringing up a red herring:  The coordinates of
the node on the paper depend on an arbitrary choice of coordinate system,
unlike the number of pointers you need to get to the stored node in the
computer. This argument, if someone makes it, is based on a misreading of
what I said.  I said each node is labeled by its location on the paper.  I
didn't say the coordinates of the location.  The location itself is the
label. "

the final conclusion of your arguing : " The location itself is the label" 
means that there is no such a thing as an unlabeled graph.

interesting . . . 

but what about permutation of the labels ? 

en fin !  we should perhaps leave this problem to the philosophers, if
they would be able to understand it 

e.d.