1
$\begingroup$

Consider a graph $G(V,E)$ where every vertice $v\in V$ has its weight $w(v)$. I want to work with $$\sum_{(u,v)\in E}w(u)w(v)$$ I think there should many good ways to approach this object, but what are they?

Furhermore, is there method for calculating this sum via incidence matrix?

An incidence matrix is a $|V|\times|V|$ $(0,1)$-matrix with entries $a(u,v)$, such that $$ a(u,v)= \begin{cases} 1 & (u,v)\in E \\ 0 & otherwise \end{cases} $$

In more details: $V=\{0,1\}^m$, a pair $(u,v)\in E$ iff $u+v$ is a Fibonacci tiling. I want to work with the "total edge weight". Is there any representations of it in terms of matrices and vectors?

$\endgroup$
  • 3
    $\begingroup$ Your matrix $A$ is usually called the adjacency matrix, with "incidence matrix" reserved for the $V \times E$ matrix with $1$s where the vertex $v$ is in the edge $e$ (the edge is incident on the vertex). Your sum is $w^tAw$, assuming $(u,v)$ and $(v,u)$ count as distinct edges; otherwise, provided your graph has no loops, you need to divide by $2$. $\endgroup$ – Ben Barber Feb 8 '17 at 8:10
1
$\begingroup$

It appears that you're interested in the concept of edge weights. A graph with weighted edges is just like a graph with weighted nodes except the edges have weights instead of the nodes. You can transform a node weighed graph into an edge weighted graph by defining $w(e)=w(u)w(v)$ where $e=(u,v)$.

One common approach to edge weighted graphs is to generalize the incidence matrix to include information about the weights. Simply replace the $1$ in your definition with $w(u)w(v)$ and you'll obtain a new matrix that has many of the same properties of the incidence matrix, but also can answer questions about the weights. For your question, that number is known as the "total edge weight" of the graph and is simply given by summing the entries of the generalized incidence matrix and dividing by $2$ (since every edge gets added twice).

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ ok, i ll explain in details: $V={0,1}^m$, pair $(u,v)\in E$ iff $u+v$ is Fibonacci tiling. and i want work with "total edge weight". Is there any representations in terms of matrices and vectors? $\endgroup$ – Radmir Feb 8 '17 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.