User:Profmduffy/sandbox

-Sources

 -Graph Theory by Harary (1969)
 -The Square of a Tree (1959)
 -MacTutor - Frank Harary
 -Discrete Applied Mathematics 2 - Esser and Harary (1980)

-Expand biography and homelife -Shifting interests in mathematics ( physics -> boolean-like rings -> Knot theory -> Graph theory) -Work and research history (universities, co-authors and travels)

 -Why he did what he did
 -Encouraging more research through his writing style in his texts
 -Difficulty with his first publication
 -First book in Graph Theory (1969)

-What others thought of him

 -Personal life and 1960's issues
 -Students reactions to his work
 -book reviews

-Post retirement work

Key Theorem in Graph Theory

Much of Harary's work was done to further research in the field of graph theory and then almost immediately apply the tools provided by graph theory to other mathematical subjects. One such example of Harary's efforts to create this connected network between the mathematical subjects of graph theory and linear algebra was his wok on The Square of a Tree. In order to outline the connection here Harary observed the adjacency matrix for many different types of connected graph and noticed a connection between the square root of an adjacency matrix and the graph of some tree. For example given a complete graph where all entries of the adjacency matrix are 1's, it is possible to find a unique tree with which you can square it's adjacency matrix to obtain the adjacency matrix for the initial complete graph. Here we will provide a basic breakdown of this theorem, and the method used by Harary to find the unique "tree square root" of particular connected graphs.
$*$ Observe the (square) adjacency matrix A, of a graph G where A = (a_ij) where a_ij = 1 if points b_i and b_j are adjacent and a_ij=0 otherwise, except that we take the diagonal of A to contain only 1's.
$*$ If a graph G is the square of a tree, then it has a unique tree square root
$*$ Some vocabulary necessary to understand this proof and the methods used here are provided in Harary's The Square of a Tree
(Complete graph, clique, cliqual, unicliqual, multicliqual, cocliqual, neighborhood, neighborly, cut point, block)

-How to determine if some graph G is the square of a tree.

-Iff a graph G is complete or satisfies the following 5 properties then G = T2
i) Every point of G is neighborly and G is connected.
ii) If two cliques meet at only one point b, then there is a third clique with which they share b and exactly one other point.
iii) There is a 1-1 correspondence between the cliques and the multicliqual points b of G such that clique C(b) corresponding to b 
contains exactly as many multicliqual points as the number of cliques which include b.
iv) No two cliques intersect in more than two points.
v) The number of pairs of cliques that meet in two points is one less than the number of cliques.

-Algorithm for finding the tree square root of a graph G.

-Step 1: Find all the cliques of G.
-Step 2: Let the cliques of G be C1,...,Cn, and consider a collection of multicliqual points  
b1,...,bn corresponding to these cliques in accordance with condition iii.  The elements of this collection are 
the nonendpoints of T.  Find all of the pairwise intersections of the n cliques and form the graph S by joining the points          
bi and bj by a line if and only if the corresponding cliques Ci and Cj intersect in 
two points.  S is then a tree by condition v.
-Step 3: For each clique Ci of G, let ni be the number of unicliqual points.  To the tree S obtained in step 2,
attach ni endpoints to bi, obtaining the tree T which we sought.

Once we have have the tree in question we can create an adjacency matrix for the tree T and check that it is indeed to correct tree which we sought. Squaring the adjacency matrix of T should yield an adjacency matrix for a graph which is isomorphic to the graph G which we started with. Probably the simplest way to observe this theorem in action is to observe the case which Harary mentions in The Square of a Tree. in which Harary observes this theorem in action with connected graphs. Specifically the example in question describes the tree corresponding the the graph of K₅
"Consider the tree consisting of one point joined with all the others. When the tree is squared, the result is the complete graph. We wish to illustrate... T²$=$K₅"
Upon squaring of the adjacency matrix of the previously mentioned tree, we can observe that this theorem does in fact hold true. We can also observe that this pattern of setting up a tree where "one point joined with all the others" will always indeed yield the correct tree for all complete graphs.