# Laplacian and Energy in Graphs

If is a digraph (say, irreflexive binary relation on a set ), we then defined the incidence matrix as the matrix whose entry was iff for vertices NOTE: This definition is not the traditional one; I accidentally wrote it incorrectly in a previous post and have made the correction to that definition. The correct definition of is the matrix where the entry is iff or . That is, the entry is iff is a vertex on the edge We can then define the **Laplacian** of as

We will simply write as the Laplacian when it is clear what digraph we are discussing.

Now consider a map and the corresponding matrix whose th row is We will denote this matrix The authors ([1]) call the map a *representation* of the graph (or digraph in our case) in As the -vectors aren’t operators on it seems counterintuitive to call the map a representation, but I will discuss an matrix they mention in a bit.

**Definition 1.** Let We define the **energy with respect to** of the graph by

Furthermore we can define each edge to have a **weight** and define the **weighted energy of** **with respect to** and by

Now let be the diagonal matrix whose diagonal entry is for a chosen weight function

**Proposition 2.** Let be an antisymmetric () digraph on , and be a weight function on Then

One may call the matrix the **weighted Laplacian** of Now the matrix is an matrix which depends upon a triple with an antisymmetric digraph on and So we could define a map where

Unfortunately this map isn’t a homomorphism, and hence not technically a representation; I couldn’t find a simple structure on compatible with addition of matrices.

[1] Godsil, Chris and Gordon Royle. *Algebraic Graph Theory*. Graduate Texts in Mathematics. Vol. 207. Springer Science and Business Media. 2004.

# Matrices and Graphs

Recall in the post “Canonical Representation of Finitely Presented Coxeter Groups” we defined the Coxeter matrix of a Coxeter group by where with as the generators of the group. We can also define the **Coxeter graph** of a Coxeter group whose vertices are the generators of the group. Then since for we will define edges between two generators iff and label the edge with when

In a generic graph (recall our presentation with a set and a symmetric relation on ), we can define a matrix, called the **incidence matrix** of , denoted where

So is iff the vertex is a vertex on the edge This assumes some ordering of So if we assume irreflexivity of then every column, indexed by will have precisely two entries that are specifically in the th and th row.

In the case of the incidence matrix of a Coxeter graph, the nonzero rows thus coincide with generators such that for some

We can remove the symmetric requirement of ; so is just a subset of We can then use “binary relation” synonymously with “**digraph**“. From here on we will assume a digraph on is an irreflexive binary relation on and that a graph on is an irreflexive symmetric binary relation on

**Definition 1.** Let and be digraphs on and respectively. A map is an **-digraph homomorphism** if An –**isomorphism** of digraphs is a bijective -homomorphism of digraphs.

**Definition 2.** Let be a digraph on We define the **adjacency matrix** of , denoted as the matrix where is the number of paths from to

So an entry being means one of the entries or is in since being a vertex on an edge means there is a path to some other vertex (namely the other vertex on that edge).

**Proposition 3.** Let and be digraphs on There is an -automorphism of iff there is a permutation matrix such that

[1] Godsil, Chris and Gordon Royle. *Algebraic Graph Theory*. Graduate Texts in Mathematics. Vol. 207. Springer Science and Business Media. 2004.

# A Bit on Graphs

I was never a big fan of the presentation of graphs as sets of vertices and edges (say and ) such that elements of had the form with and I prefer to use the language of relations.

**Definition 1.** A **graph** on is a symmetric binary relation on We then call the set of **vertices** and the set of **edges**.

Recall a binary relation on is a subset of They are equivalent notions, but in the latter, one simply has a set with a relation on it–rather than these two separate sets such that the second set backtracks to the first as a relation.

**Example 2**. A** complete graph** (one in which any two vertices are adjoined by an edge) is thus simply a graph where every is **almost surjective with respect to** , by which I mean if we let

then for all In particular we hence have

When I say a vertex is surjective with respect to , I mean it has an edge with all other vertices (where almost-surjective excludes an edge with itself). Note the relation is always a surjective relation if we assume every vertex has some edge connected to it (i.e. is left-total and hence surjective since domain=codomain). But a surjective relation of course does not imply every element is surjective with respect to

**Example 3**. A **connected graph** is a graph such that for any distinct two there is a sequence (or **path**) such that for all

A **tree** is thus a connected graph such that paths between points are unique (note this definition of a tree is different from that of posets: where elements have a well-ordered set of predecessors). And so on and so on….

In fact, recall Abramenko and Brown used this algebraic approach in the construction of Coxeter complexes, although it was slightly more complicated since they were dealing with graphs whose vertices were cosets of the maximal standard subgroups of a Coxeter group Lengths of paths between vertices in the sense I have described coincide with lengths of minimal galleries between chambers containing those vertices. Also, be not confused that in that construction of Coxeter complexes, there was another implicit notion of a (di)graph where any simplex was a vertex, and a directed edge connected two simplices if one was the face of another.