This is concerning the mail of Dusko in reply to my mail:
Eduardo Dubuc wrote:
what sense has the concept of unlabeled graph ?
try to put an unlabeled graph inside a computer ?
you mean unordered? i would implement it as an ordered graph, with an additional involutive map on the edges, ie
Edges <--inv-- Edges ==dom,cod==> Nodes dom.inv = cod inv.inv = id
--- which, in a way, confirms that
yours is not an answer to my question, which I shall explain now (I thought that it needed no explanations) by an unlabeled graph i mean the drawing of a graph, in paper, say, or a graph buildt in space, the skeleton of a building for example. It has vertices and edges, and everybody knows what it is. Mathematically you could say a symetric relation on its (finete) set of vertices. But not quite so ... If you have n vertices, you have n! different labeling. Each labeling gives you a different labeled graph. The minute you have a set (in the mathematical sense) of vertices, you have a labeling. Namely, the elements of that set are the labels!. So, with a symetric relation (in the mathematical sense) what you got is a labeled graph. Not an unlabeled graph !. And you become well aware of this fact when you want to put a concrete unlabeled graph (say, the skeleton of a building) inside a computer !! REMEMBER I rise the question on unlabeled graph related to the question that we were discussing: INEVITABILITY OF NAMING (IN MATHEMATICS) (naming is not the same as labeling ?)
well, unlabeled graph has to be a quotient by an equivalent relation ...
I said that. It seems possible. I explain now the ... Given two graphs R, S (symetric relations) on a finite set X (of vertices), consider the natural action of the symetric group of X on the power set of X x X. Then, R =~ S iff they are in the same orbit. The elements of the quotient set are the unlabeled graphs. e.d.