# Tie-set graph theory

I have a project in maths which consists in the establishment of a model of a « smart grid » (a sort of smart information network) that requires some knowledge in graph theory – that I do not have.

Well first of all, since I haven’t studied it in class, I’m having some trouble with the whole graph theory. In fact I do not really get what is the approach, it seems at the same time very instinctive and obvious, but I understand the various applications or exercises I have found. So if you had any piece of advice, names of useful books or whatever, or even better if you could really just sum up the main ideas, the main theorems I must know and look for, this would be really nice. I do not know what to begin with.

The main problem though isn’t the graph theory itself since I still manage to somewhat follow, despite the difficulties I’m having. The one true problem is that I have encountered several times in an article about the subject I’m studying the notion of “tie-set graph” and “tie-set graph theory” that I do not understand. I do not find any piece of information about it to help me – apart from two lines in a Wikipedia article, and the definition that I read in the article and that is very vague to me. It is apparently linked with the notion of “cotrees” – another definition I’m not sure to have gotten right.

So if you could just please help me with this “tie-set graph theory” thing, keeping in mind that I’m a neophyte, that would be really nice… I'm aware that this is not a very precise request, but I truly need help here.. Thank you very much

PS= the article I'm talking about: http://www.ics.uci.edu/~knakayam/Wiley.pdf

-
Never heard of it, but that paper refers to another one, [16], that may tell you more about the concept. – Gerry Myerson May 8 '14 at 13:14
First of all there's a lot of vocabulary that I don't get, like cotree (that seems to be the actual meaning of a "tie-set graph"), ultrant, rank & nullity, a biconnected graph (I really don't understand what could possibly be the difference between a uni and biconnected graph...)... Therefore I really do not understand what is explained there :/ – smgr May 8 '14 at 13:47
In a biconnected graph, you can delete any one vertex without disconnecting the graph. In a graph with connectivity 1 there is a vertex whose deletion disconnects the graph. In that paper a cotree is the complement of a tree in the graph, so the graph consisting of all edges in the underlying graph not in the tree. I have never heard of an ultranet set before, and google hasn't either, but from context it seems to mean a spanning set - in other words, they are only dealing with spanning trees (trees that include all vertices of the graph). – Perry Elliott-Iverson May 8 '14 at 15:20
Thank you very much this is very clear :) Especially since I'm not a native English speaker. So in fact I had the idea of cotree right... What they are calling "tie-set graph theory" would then consist in the regular graph theory regarding only cotrees?... – smgr May 8 '14 at 15:56
They define a tie-set as the set of edges of a cycle in a graph. For any tree, if you add an edge to it from the corresponding cotree, you will create a single cycle - the tie-set corresponding to that cycle is what they define as a fundamental circuit. The set of fundamental circuits corresponding to a tree is what they call a fundamental system of tie-sets. They go on to define tie-set graphs as graphs related to the intersections of the tie-sets in a fundamental set. Their definitions are not very clear, so it's understandable that you are having difficulty. – Perry Elliott-Iverson May 8 '14 at 16:10