Algebraic Structures on Graphs Joined by Edges
Daniel Pinzon Daniel Pragel Joshua Roberts





arrows.meta










   







theoremTheorem[section]
proposition[theorem]Proposition
definition[theorem]Definition
corollary[theorem]Corollary
lemma[theorem]Lemma
example[theorem]Example
remark[theorem]Remark
conjecture[theorem]Conjecture
*theorem*Theorem






























 
 
 
 
 


 
thmTheorem[section]
lem[thm]Lemma
cor[thm]Corollary
prop[thm]Proposition
rem[thm]Remark
ex[thm]Example
de[thm]Definition

tight_enumerate

  
  


equationsection 

























footer
  
  
  [L] Acknowledgements: We are grateful for the work of undergraduate students Shahriyar Roshan Zamir & Hope Doherty who assisted with example calculations.



Algebraic Structures on Graphs Joined by Edges
    Daniel Pinzon, Daniel Pragel, & Joshua Roberts 
    
===================================================

footer

§ ABSTRACT 
Let G_1 G_2, the j join of two graphs, be the union of two disjoint graphs connected by j edges in a one-to-one manner. In previous work by Gyurov and Pinzon <cit.>, which generalized the work of Badura <cit.> and Rara <cit.>, the determinant of the two joined graphs was decomposed to sums of determinants of these graphs with vertex deletions or directed graph handles. In this paper, we define a homomorphism from a quotient of graphs with the join operation to the monoid of integer matrices. We find the necessary and sufficient properties of a graph so that  joining to any another graph will not change its determinant. We also demonstrate through examples that this decomposition allows us to more easily calculate determinants of chains of joined graphs. This paper begins the process of finding the algebraic structure of the monoid.







§ INTRODUCTION



Let 𝔾_j be the set of labeled finite simple directed graphs with at least 2j vertices such that, for G ∈𝔾_j, the set of vertices is  V(G)={1, 2, …, m}, where m is the number of vertices of G. The set of edges is E(G) ⊆{(v,w) | v,w ∈ V, v≠ w}. We will at times refer to the “last" vertices of G using the convention -1,-2,-3,… for |V(G)|,|V(G)|-1,|V(G)|-2,…. Throughout this paper we will use the term graph in general to be a directed graph.

Let G, H ∈𝔾_j where V(G)=1,…,m and V(H)=1,…,n.   Following <cit.>, we define the j-join of  G and H with j edges as the graph formed by joining each of the “last" distinct j vertices of G with each of the corresponding “first" j distinct vertices of H in both directions. See <Ref> below.



There is a choice as to whether to put the instructions of the joining operation on the graph elements or on the operation. The labeling contains the information on where to join one graph with another so that we have one well-defined operation rather than many operations. This motivates the use of labeled graphs. It will be clear from the definition below that this operation is associative.

 
 Let G, H ∈𝔾_j. The j-join of G and H, denoted G H, has the vertex and edge sets below where |V(G)|=m and each i∈ V(H) is relabeled as m+i in V(G H).


    V(G j≍ H) = V(G) ∪{m+i| i∈ V(H)}, and


    E(G j≍ H) = E(G)    ∪{(m+1 -i, m+i),(m+i, m+1 -i) | 1 ≤ i ≤ j}
       ∪(m+i,m+j)| (i,j)∈ E(H).
 
 


From <cit.>, we can write the determinant of the adjacency matrix of the j-join of two graphs G and H as a sum of determinants of the adjacency matrices of modifications of G and H.  The two modifications are vertex deletions and directed graph handles.  We describe them below.
  

(Vertex deletion) For a graph G and a vertex v∈ V(G) we denote by G{v} the subgraph of G
obtained by removing the vertex v from V(G) and all edges that are incident with v from E(G).

Further, if R is a subset of vertices of G, we denote by G R the subgraph of G
obtained by deleting all vertices in R from G.



The operation of attaching a directed graph handle is attaching a copy of a directed path on 3 vertices, P_3, as described below.


(Directed Graph Handle)
For a graph G and vertices u,v∈ V(G), we denote G_[u,v] to be the graph where a new vertex
w=|V(G)|+1 is added to V(G) and a directed edge from vertex u to vertex w and a directed edge from vertex w to vertex v are added to E(G).
Vertex w is called the directed graph handle vertex of the directed graph handle [u,v].

Further, if B is a set of ordered pairs of elements of V(G), we denote G_B to be the graph
where for each [u,v]∈ B a new directed graph handle is attached to G.
 

We denote |R| as the number of elements of R and |B| as the number of handles in B. In this paper, we will regularly attach handles on graphs where a set of vertices R have been removed. If B is the set of handles, then we denote this graph as (G R)_B. 

We will be using the main result from <cit.> given below which describes how to express the determinant of G H as a sum of the determinants of modifications of graphs. We sum over all possible vertex removals R from a set J={i| 1≤ i≤ j} which are the “first" j vertices of H. We also modify G in a similar, conjugated way. That is, if i∈ R is removed from H, then the conjugated vertex -i∈ R^*={-i| i∈ R} is removed from G. 

Given B, the set of appended directed graph handles on H, the conjugate set is defined as
B^*={[-r,-c] | -r,-c ∈ V(G),[c,r]∈ B}.

Note that the direction of the conjugated handles are reversed. Below we give an example of a term in the sum.

 Let G, H ∈𝔾_10 and m=|V(G)|. Then, J={1,…,10}. Let R={4} and let B={[1,3],[2,5]} be handles made from J R. Then, the conjugate removal set and handle set for G are R^*={-4}={m-3} and B^*={[-3,-1],[-5,-2]}={[m-2,m],[m-4,m-1]}. The figure below shows (G R^*)_B^* and (H R)_B. Note that the open circle at m-3∈ V(G) and 4∈ V(H) correspond to vertex deletions at those vertices. Also, notice that the handles on G are in the opposite direction of those on H.


[scale=2,dot/.style 2 args=circle,inner sep=1pt,fill,label=#2:#1,name=#1]

    (-4,0) circle (.75cm);
    (0,0) circle (.75cm);
every node=[circle,fill=white,inner sep=0.5mm]
    (G) at  (-4,0) 5050;
every node=[circle,fill=white,inner sep=0.5mm]
    (H) at  (0,0) 5050;

every node=[circle,fill=black,inner sep=2pt,xshift=-8cm]
at  (35:0.75)      ;
every node=[circle,fill=white,inner sep=1.5pt,xshift=-8cm]
[label=[xshift=8cm ]left:m-3](3) at  (35:0.75)      ;
every node=[circle,fill=black,inner sep=2pt,xshift=-8cm]
[label=[xshift=8cm ]left:m-4](3) at  (60:0.75)      ;
[label=[xshift=8cm ]left:m-2](2) at  (15:0.75) ;
(v1) at (15:1.5) ;
(v2) at (-15:1.5) ;
[label=[xshift=8cm ]left:m-1](1) at (-15:0.75);
[label=[xshift=8cm ]left:m](0) at  (-45:0.75) ;
[-Latex[length=3mm]] (3)–(v1);
[-Latex[length=3mm]] (v1)–(1);
[-Latex[length=3mm]] (2)–(v2);
[-Latex[length=3mm]] (v2)–(0);

every node=[circle,fill=black,inner sep=2pt,xshift=0cm]
[label=[xshift=0cm ]right:4] (h3) at  (150:0.75)     ;
every node=[circle,fill=white,inner sep=1.5pt,xshift=0cm]
at  (150:0.75)     ;
every node=[circle,fill=black,inner sep=2pt,xshift=0cm]
[label=[xshift=0cm ]right:5] (h4) at  (120:0.75)     ;
[label=[xshift=0cm ]right:3](h2) at  (165:0.75) ;
(hv1) at (165:1.5) ;
(hv2) at (195:1.5) ;
[label=[xshift=0cm ]right:2](h1) at (195:0.75);
[label=[xshift=0cm ]right:1](h0) at  (225:0.75) ;
[-Latex[length=3mm]] (h1)–(hv1);
[-Latex[length=3mm]] (hv1)–(h4);
[-Latex[length=3mm]] (h0)–(hv2);
[-Latex[length=3mm]] (hv2)–(h2);



    

 
The determinant of the disjoint union of the two graphs above represents (up to sign) one of the terms in the summation below. The summation does not sum over all possible handles, but rather a subset of them. An allowable handle set is a set of handles B such that a vertex appears only once in the set and, for any two handles [a,b], [c,d], either [a,b]<[c,d] or [a,b]>[c,d], where the inequality is component-wise. 


The theorem below is a full generalization of ideas first introduced by Rara <cit.> (j=1) and continued in <cit.> and <cit.> (j=2). We adopt the notation |G| to mean the determinant of the adjacency matrix of G.

<cit.>
Let G and H be graphs of order m and n respectively where. Let J be the set of vertices of H that are joined to G. Then

    |G  H|  = ∑_R ⊂ J∑_B (-1)^|R|+|B||(G  R^*)_B^*|  |(H  R)_B|

where the summation is over all allowable handle sets B.



The following corollary, which is equivalent to Theorem 1 in <cit.>, is immediate by the preceding theorem. 



    |G 1≍ H| = |G||H| - |G ∖{-1}| · |H ∖{1}|.




The next corollary and proceeding figure below illustrate how to express the 2-join of two graphs using the Theorem <ref>.



    |G 2≍ H| =    |G||H| - |G ∖{-1}| · |H ∖{1}| - |G ∖{-2}| · |H ∖{2}| 
       + |G ∖{-1,-2}| · |H ∖{1,2}| 
       - |G_[-1,-2]| · |H_[2,1] - |G_[-2,-1]| · |H_[1,2]|







§ AN EQUIVALENCE RELATION




For a given positive integer j, we can define an equivalence relation . We use the terms of the summation in Theorem <ref> as a motivation for this definition.


For G, H ∈𝔾_j and for any vertex deletion sets R_1,R_2 and corresponding allowable handle sets B_1, B_2, G  H  if and only if

    |(G ∖ R_1∪ R_2^*)_B_1∪ B_2^*| = |(H ∖ R_1∪ R_2^*)_B_1∪ B_2^*|.



Clearly this is an equivalence relation on 𝔾_j. We define the quotient 𝒢_j = 𝔾_j/. The following theorem shows that the j-join is a well-defined operation on the quotient set. As a consequence of the following theorem, we can define an induced j-join product on the equivalence classes, 


    [G] [H]=[G H].



For a fixed integer j>0, the j-join is a well-defined binary operation over the equivalence relation .


Let G_1, G_2, H_1, H_2 ∈𝔾_j where we recall that their orders are greater than 2j. Assume that 
G_1  G_2 and H_1  H_2. We need to show that 
(G_1 H_1)  (G_2  H_2).

Using <Ref>, we consider
|((G_1 H_1) ∖ R_1∪ R_2^*)_B_1∪ B_2^*|. We note that since since G_1 has at least 2j vertices and R_1, B_1 act on the first j vertices of G_i  H_i, which are  not the  vertices involved in the j-join. Similarly, the conjugate sets only act on H_i. Using this fact and <Ref>, we have

    |((G_1 H_1) ∖ R_1∪ R_2^*)_B_1∪ B_2^*|
       =   
    |(G_1∖ R_1)_B_1) (H_1 ∖ R_2^*)_B_2^*|
       =   ∑_R ⊂ J∑_B (-1)^|R|+|B||(G_1 ∖ R_1∪ R^* )_ B_1∪ B^*| |(H_1 ∖   R ∪ R_2^*)_ B∪ B_2^*)|
       =   ∑_R ⊂ J∑_B (-1)^|R|+|B||(G_2 ∖  R_1∪ R^*)_B_1∪ B^* | |(H_2 ∖   R∪ R_2^*)_ B∪ B_2^*)|
       =   |((G_2 H_2) ∖ R_1∪ R_2^*)_B_1∪ B_2^*|,

where the third equality follows from the fact that G_1  G_2 and H_1  H_2.




 §.§ Equivalence Classes

In this section, we will explore the necessary conditions for the existence of an identity element, a zero, and other equivalence classes. For simplicity, we shall use [G] instead of [G]_j when the j is clear from the context.


  §.§.§ The Identity Class

  We say that I∈𝔾_j is an identity graph if and only if for any G∈𝔾_j, [I G] =[G I] = [G]. That is, that joining any graph by an identity graph does not change its equivalence class and thus, in particular, preserves its determinant. 


Let j∈ and I∈𝔾_j. If for any vertex deletion sets R_1,R_2 and corresponding handle sets B_1, B_2, 

    |(IR_1∪ R_2^*)_B_1∪ B_2^*|=
                 
                  (-1)^|R_1|+|B_1|   if  R_1=R_2, B_1=B_2 
    
                  0    otherwise,

then I is an identity graph.



Let j ∈, G ∈𝔾_j, and I be as above. Then using a similar argument as in the proof of Theorem <ref>,

    |(I G)  (R_1∪ R_2^*))_B_1∪ B_2^*|
    =|(I R_1)_B_1 (G R_2^*)_B_2^*|
       =∑_B∑_R ⊂ J (-1)^|R|+|B||(I  (R_1∪ R^*)_(B_1∪ B^* )| |(G  ( R∪ R_2^*))_B∪ B_2^*|
       =(-1)^|R_1|+|B_1||(I  (R_1∪ R_1^*)_(B_1∪ B_1^*)| |(G  (R_1∪ R_2^*))_B_1∪ B_2^*|
       = |(G  (R_1∪ R_2^*))_B_1∪ B_2^*|.


The third equality results from the properties of I causing all terms of the summation to vanish except where R=R_1and B = B_1. Thus we have shown that if I satisfies the conditions of the theorem, then [I G] = [G]. Similarly, [G] = [G  I]. 


For the 1-join, any path graph of order 4k is a member of the identity class. 

The following figure demonstrates the existence of representatives of the identity classes for the j-join operation for j≥1. The graph G has m vertices labeled j+1 through m+j.
j-Join Identity


[scale=1]
(0,0) circle (1.5cm);
(C) at (0:0) |G|=(-1)^j;

every node=[circle,fill=black,inner sep=0.5mm,yshift=0,xshift=0]


[label=[xshift=0cm ]left:1] (1) at  (4,1)  ;
[label=[xshift=0cm ]right:m+2j] (m) at (6,1) ;
[label=[xshift=0cm ]left:j] (2) at  (4,-1)  ;
[label=[xshift=0cm ]right:m+j+1] (m-1) at (6,-1) ;
every node=[circle,fill=black,inner sep=0.25mm,yshift=0,xshift=0]
() at (5,.8) ;
() at (5,.6) ;
() at (5,.4) ;
() at (5,-.8) ;
() at (5,-.6) ;
() at (5,-.4) ;
every node=[circle,fill=white,inner sep=0.25mm,yshift=0,xshift=0]
[label=[xshift=0cm,yshift=-1cm ]above:j copies of P_2] () at (5,-.25) ;




(1)–(m);
(2)–(m-1);



figureDirected edges from the copies of P_2 to G are not necessary unless connectivity is desired.



    The graph in <Ref> is a representative of the identity class for any j.



Consider any graph G, with |G|=(-1)^j and order m. Let I_j be a disjoint union of G with j copies of P_2. We label the vertices of I_j as shown in <Ref>. Since |P_2|=-1, then it is clear that |I_j|=1.

Next, note that in (I_j∖ R_1 ∪ R_2^*)_B_1 ∪ B_2^*, if R_1 ≠ R_2, then either there exists at least one copy of P_2 where one vertex is removed and the other is isolated or the single vertex is part of a handle. In the former case, we have that the determinant is zero. In the latter case, we use Harary's definition from <cit.> of the determinant of a graph  and note that there are no spanning directed cycle decompositions of I_j. Thus in order for (I_j∖ R_1 ∪ R_2^*)_B_1 ∪ B_2^* to be nonzero it must be the case that R_1 = R_2.

Now, assume R_1 = R_2. Then, each vertex in R_1 results in the deletion of a copy of P_2 which results in a change in the determinant by a factor of -1. Thus there will be a total change of (-1)^|R_1| to the determinant.

Suppose that we have (I_j∖ R_1 ∪ R_1^*)_B_1 ∪ B_2^* with B_1 ≠ B_2 and ((I_j∖ R_1 ∪ R_1^*)_B_1 ∪ B_2^*) ≠ 0. Then, there exists at least one handle [a,b] in B_1 or B_2 that is not in the other handle set. Since |(I_j∖ R_1 ∪ R_1^*)_B_1 ∪ B_2^*| ≠ 0, then the vertex of that handle must be part of a directed cycle C that is a subgraph of (I_j∖ R_1 ∪ R_1^*)_B_1 ∪ B_2^*. This implies that C contains at least 4 copies of P_2 from I_j. Let n be the least positive integer such that n ∈ V(C). We observe that vertex n must be contained in one of the copies of P_2. So, either (n, -n) or (-n, n) ∈ E(C). Suppose (n, -n) ∈ E(C). 

We observe that, beginning with vertex n, to travel along the directed cycle C, we move through a copy of P_2, then a handle, then followed by another copy of P_2 (in the opposite direction), and so on until arriving back at n. Formally, let a_1, a_2, …, a_k ∈{1, 2, …, j} be the positive vertices in P=I_j∩ C of the directed cycle starting and ending at n, in the order that they appear in C, so that a_1 = a_k = n. It follows  that, for odd i ∈{1, …, k-1}, (a_i, -a_i) ∈ E(C) and the handle on P from -a_i to -a_i+1 is traversed in C. Additionally, for even i ∈{1, …, k-1}, (-a_i, a_i) ∈ E(C) and the handle on P from a_i to a_i+1 is traversed in C. Note that k≥ 4.

 Furthermore, since n is the minimum of {a_1, a_2, …, a_k-1}, a_1 < a_3 and a_k-2 > a_k. This implies that there must be some i ∈{ 1, …, k-3} with a_i < a_i+2 and a_i+1 > a_i+3. But then the handles [a_i, a_i+1] and [a_i+2, a_i+3] must both be in B_1 or B_2. But this implies that B_1 or B_2 is not an allowable handle set.

The case when (-n,n) ∈ E(C) is handled analogously. Thus, we see that, if B_1 and B_2 are allowable handle sets and ((I_j∖ R_1 ∪ R_2^*)_B_1 ∪ B_1^*) ≠ 0, it must be the case that B_1 = B_2.


Thus, we see that (𝒢_j,) is a monoid with identity as given above.



§ ALGEBRAIC STRUCTURE OF THE JOIN OPERATION



 
  Let S be a semigroup and x,y∈ S. A sandwich operation ∙ on S is defined as x∙ y=xay, where a is an element of S.


Hickey showed that S under this sandwich operation is also a semigroup denoted (S,a) which we will call the sandwich semigroup on a.

Let G be a representative of any equivalence class of graphs [G]∈𝒢_j=𝔾_j/ for some j∈. From the above, the equivalence class under the j-join is defined by all the modifications of G given by (G R_1∪ R_2^*)_B_1∪ B_2^* where R_i⊆  J = 1,...,j and B_i are handle sets on the vertices J R_i where the handles satisfy the conditions discussed in <Ref>. This also defines the conjugate sets R_2^*, B_2^*.  

Now, consider the set of all allowable removal set and handle set pairs (R,B)| R⊆ J, B⊆𝒫(J-R2), B  allowable. From <cit.>, looking at the Laplacian expansion,  we see that there are k= 2j j elements. Let us enumerate these pairs as (R_1,B_1)=(∅,∅), (R_2,B_2)), ..., (R_k,B_k). The choice of how these are numbered is arbitrary, but we need to fix a convention here for the rest of the paper. Now, define the functions r_i:𝒢_j → as r_i([G])=((G R_i)_B_i), where for 1≤ i≤ k. We see that this function is well defined since any representative of the class will have the same determinant. Equivalently, we can define the conjugate modifications as c_l:𝒢_j → as c_l([G])=((G R_l^*)_B_l^*), 1≤ l≤ k.


Now, we can define an operation from any graph equivalence class to a k × k integer matrix ϕ:𝒢_j→ M(k,) as 

    ϕ([G])=[m_il]=[((r_i∘ c_l) (G))].





We can now prove the main results of our paper that the algebraic structure of the j-join under the j-join equivalence class is a sub-semigroup of the sandwich semigroup isomorphic to the k × k integer matrices under matrix multiplication. We begin with the following theorem that shows that our function is a homomorphism.

Let [G],[H]∈𝒢_j and ϕ as in the discussion above. Then, 

    ϕ([G] [H])=ϕ([G H])=ϕ([G]) E_j ϕ([H])

where E_j=[e_il=

    (-1)^|R|+|B|    i=l

    0   otherwise].


Let [m_il] = ϕ([G H]) = [((r_i∘ c_l) (G H))] as defined above. Then, since |V(G)|, |V(H)|≥ 2j, then r_i(G H)=r_i(G) H and c_l(G H) = G c_l(H) and so (r_i∘ c_l) (G H) = r_i(G) c_l(H) = (G R_i)_B_i (H R_l^*)_B_l^* for some vertex removal sets R_i, R_l and handle sets B_i, B_l.  

Then, calculating the determinant using <Ref>, we have 

    m_il=((r_i∘ c_l) (G H))  = ((G R_i)_B_i (H R_l^*)_B_l^*)=
    ∑_B∑_R ⊂ J (-1)^|R|+|B||(G  R_i∪ R^*)_B_i∪ B^*| |(H  R∪ R_l^*)_B∪ B_l^*)|

Note that the vertices of R_i^*, B_i^* are never the same as those of R,B since the number of vertices of G is at least 2j. We see this is the same for H as well.

Notice that the |(G  R_i∪ R^*)_B_i∪ B^*| are the elements of the i^th row of ϕ([G]) and, equivalently, the |(H   R∪ R_l^*)_B∪ B_l^*)| are the elements of the l^th column of ϕ([H]). 

Then, we see that 

    m_il=∑_p ϕ([G])_ipE_j_ppϕ([H])_pl

which shows that ϕ is a homomorphism of monoids from the j-equivalent graphs under the j-join operation to the k× k matrices under the sandwich operation with sandwich element E_j. Therefore we can define 
    ϕ([G])∙ϕ([H])=ϕ([G]) E_j ϕ([H]) =ϕ([G] [H])=ϕ([G H]).




The homomorphism ϕ:(𝒢_j,)→ (M(k,),E) is one-to-one where (M(k,),E) is the sandwich monoid with sandwich element E as described above. 

   
  This proof follows straight from definitions. If [G_1], [G_2]∈𝒢_j such that [G_1]≠ [G_2], then there exists i,j such that ((r_i∘ c_l) (G_1))≠((r_i∘ c_l) (G_2)). But then, this implies that ϕ(G_1)≠ϕ(G_2) as matrices. 


The following lemma gives us a matrix representation for this monoid.

[Hickey]
Let S be a semigroup and let a∈ S. If the semigroup (S, a) has identity element 1 then 

    
  * S has identity element 
    
  * the elements a, 1 lie in the unit group of S and are inverse to each other,
    
  * (S,a)≅ S



Let γ:(M(k,),E)→ (M(k,)) be the isomorphism from part iii from the lemma above. Then, define Φ = γ∘ϕ. <Ref> above implies that (Φ(𝒢_j), ·) is a submonoid of (M(k,),·). 

    The monoid (𝒢_j,) is isomorphic to a submonoid of (M(k,),·)


It remains an open question what the structure of this submonoid is. The next two sections will begin to explore the structure.



 §.§ The [0] and [n] classes

We generalize the identity class by defining the [n]_j, n∈{0,1,2,...} to have the properties such that if we join it to any graph on the left or right, then it multiplies the determinant of the graph by n. That is, for any N∈ [n]_j and any G, H∈𝔾_j, ϕ([G N H])=nϕ([G H])=nϕ([G])E_jϕ([H]). Hence, N must have the property that ϕ([N])=nE_j. Which gives us the following necessary and sufficient conditions on the graph N:


Let j∈,  n∈∪{0} and N∈𝔾_j. Then, N∈ [n]_j if and only if N satisfies the condition that for any vertex deletion sets R_1,R_2 and corresponding allowable handle sets B_1, B_2 and their conjugate sets, 
    |(NR_1∪ R_2^*)_B_1∪ B_2^*|=
                 
                  n(-1)^|R_1|+|B_1|   if  R_1=R_2, B_1=B_2 
    
                  0    otherwise.



We observe that this implies that 

    
  * |N|=n
    
  * For any vertex deletion set R and handle set B and their conjugate sets R^*, B^* where at least one set is nonempty,
    
    |(N R)_B|=|(N R^*)_B^*|=0



An example of a graph with the properties above is similar to the example of the identity graph given in <Ref>. We use the fact that the determinant of the complete graph is |K_n+1| =  (-1)^n(n). We need to include an extra copy of P_2 if n+j is odd so that the resulting determinant is n. 

    N=
     
          K_n+1(∐_i=1^j P_2 )     if n+j is even
    
          K_n+1(∐_i=1^j+1 P_2 )    if n+j is odd


The fact that these are the only graphs is proven in the same way that the uniqueness of the identity was proven.



 §.§ Group Structure in the Semigroup

Consider [G]∈𝒢j such that there exists [G^-1] ∈𝒢_j so that [G G^-1]=Id_j. Then ϕ([G G^-1])=ϕ([G])E_jϕ([G^-1])=E_j. If we take the determinant of both sides, this gives us 


    (ϕ([G]))(ϕ([G^-1]))=1


Which means that all of these graphs map to invertible matrices with determinants ±1. So, if L is the set of all classes of graphs in 𝒢_j that have inverses, that is, the largest group in the semigroup 𝒢_j. Then  Φ(L)⊂ GL ( 2j j,).  We know that GL(n,) is finitely generated, so if we can find graphs that map to the generators then we will have a complete representation of this group. 


§ APPLICATIONS

In this section we will show how we can use the homomorphism to easily calculate the n-fold join of various graphs.


 §.§ Complete Graphs




  §.§.§ 1-join

By work in <cit.>, the following theorem holds.




Let m and n be positive integers and K_m the complete graph on m vertices. Then


    |K_m j K_n| = {[ (-1)^m+n(m+n-3),          for j=1;               0,       for j ≥ 2. ].




We will denote the the n-fold j-join of a graph G by nj G. That is,


    nj G= G  G ⋯ G_n -joins.

For example, the 0-fold j-join of a graph G is just the graph itself, the 1-fold j-join of G is G j G, and the 2-fold j-join is G j G j G.


For integers n,m where n ≥0 and m≥3, 


    ϕ(n1 K_m) = (-1)^mn+m+n[ -[ (m-2)n+(m-1) ]        (n+1)(m-2);        (n+1)(m-2)   -[(m-2)n+(m-3)] ]




Note that this will immediately imply the following result by taking
the (1,1) element of the matrix given by ϕ( n1 K_m).



For integers n,m where n ≥0 and m≥3, the determinant of the n-fold join of the the complete graph on m vertices, with any labeling, is given by 

    | n1 K_m | = (-1)^(m+1)n[ (m-2)n+m-1 ].






The proof is by induction on n. 
For n=0 we have, 


    ϕ( 01 K_m) = ϕ( K_m )    =
        [      |K_m|  |K_m {m}|;   |K_m {1} |K_m {1,m} ]
       = (-1)^m-1[    m-1 -(m-2); -(m-2)    m-3 ].


Assuming the result for n, we now examine n+1, noting that for the 1-join, E_1 from Theorem <ref> is the matrix [  1  0;  0 -1 ]. Then 

    ϕ( n+11 K_m) = ϕ( (n1 K_m) 1 K_m ) = ϕ( (n1 K_m) )·  E_1 ·ϕ(K_m)
 
can be expressed as

99[ -[ (m-2)n+(m-1) ]        (n+1)(m-2);        (n+1)(m-2)   -[(m-2)n+(m-3)] ]·[  1  0;  0 -1 ]·[    m-1 -(m-2); -(m-2)    m-3 ]
1111

scaled by (-1)^mn+n+1. A straightforward calculation gives the result.





  §.§.§ 2-join



For integers n,m where n ≥1 and m≥3, 

    | n2 K_m | = 0.




Note that ϕ(K_m) and E_2 are, respectively the matrices



    (-1)^m[ - (-1+m)   (-2+m)   (-2+m) - (-3+m)        1        1;   (-2+m)  -(-3+m) - (-3+m)   (-4+m)       -1       -1;   (-2+m) - (-3+m)  -(-3+m)   (-4+m)       -1       -1;  -(-3+m)   (-4+m)   (-4+m)  -(-5+m)        1        1;        1       -1       -1        1        0        0;        1       -1       -1        1        0        0;          ],
 and

E_2=[  1  0  0  0  0  0;  0 -1  0  0  0  0;  0  0 -1  0  0  0;  0  0  0  1  0  0;  0  0  0  0 -1  0;  0  0  0  0  0 -1;    ]


Then by direct calculation we see that

    ϕ( K_m 2 K_m ) = ϕ(K_m) · E_2 ·ϕ(K_m)
 is the zero matrix, which implies the result.


We note that the above theorem has significance despite the previously known result that |K_m j K_m| = 0. It can be the case that |G|=0 with |G j H|  0, as can be seen by taking G = P_3, H=P_5, with the canonical labeling and j = 1.

As we have discussed in this paper, the labeling of the graph contains the information on where to join the graph. 
 
Let P_4 be a path graph on 4 vertices where we label them starting at one end as 1,3,2,4. 





For integer n ≥0, 


    |n2P_4| = 1



    Using Harary, we calculate

    ϕ(P_4)=
    [  1  0  0  0  0  0;  0 -1 -1  0 -1 -1;  0 -1  0  0  0  0;  0  0  0  1  0  0;  0 -1  0  0  0 -1;  0 -1  0  0 -1  0;    ]

Then, since the first row and column of both ϕ(P_4) and E_2 is a 1 at (1,1) element and zero elsewhere then the (1,1) element of the product will always be 1.




§ FUTURE WORK

Much work remains to be done in this area. The structure of the the semigroup is unknown as it depends on the surjectivity of ϕ. That is, will any integer matrix be the image of a graph under ϕ? A possible first step is to explore the generators and relators of the relevant submonoids. 

Parallel work can be done using a different matrix other than the adjacency such as the Laplacian, Hermitian, etc. The main obstacle here is to recreate a similar sum decomposition for the determinant of join of graphs as done in <cit.>. The authors have preliminary work done in this direction for the Laplacian matrix.

From the point of view of calculations, the techniques shown above can be applied to find generating functions for the determinant of any chain of graphs with joined in various ways as done in <Ref>. 



20

Bar Bar-Noy, A. and Naor J., Sorting, Minimal Feedback Sets and Hamilton Paths in Tournaments, SIAM Journal of Discrete Mathematics, 3(1) (1990), 7 - 20, url: <https://epubs.siam.org/doi/10.1137/0403002>.

Bad Badura, L., Two graphs with a common edge, Discussiones Mathematicae. Graph Theory, 34 (2014) no. 3, 497-507, University of Zielona Góra Press, url: <https://doi.org/10.7151/dmgt.1745>.

Lap Goldberg, L., Matrix Theory with Applications, McGraw-Hill International Editions, Mathematics and Statistics Series, 1991.

BP Gyurov B. and Pinzon, D., Determinant of Graphs Joined by j Edges, Thai Journal of Mathematics, 14 (2016) no. 2: 353-367, url: <https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/602>.

H Harary, F., The Determinant of the adjacency matrix of a graph, SIAM Rev., 4 (1961), 202 - 210, url: <https://www.jstor.org/stable/2027712>.

JBH Hickey, J.B., Semigroups Under A Sandwich Operation, Proceedings of The Edinburgh Mathematical Society, 26(3) (1983) 371-382.

R Rara, H.M., Reduction procedures for calculating the determinant of the adjacency matrix of some graphs and the singularity of square planar grids, Discrete Mathematics, 151 (1996), 213-219, url: <https://core.ac.uk/download/pdf/81194617.pdf>.

BG Sookyang, S., Arworn, S., and Gyurov, B., Determinant of Graphs joined by two edges, Thai Journal of Mathematics, 10 (2012) no. 1: 101-111, url: <https://thaijmath2.in.cmu.ac.th/index.php/thaijmath/article/view/304>.

