0
$\begingroup$

Consider a graph $G(V,E)$ where every vertex $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 be many good ways to approach this object, but what are they?

Furthermore, is there a method for calculating this sum via the 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?

Improve this question
$\endgroup$
1
  • 5
    $\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, 2017 at 8:10

1 Answer 1

Reset to default
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).

Improve this answer
$\endgroup$
1
  • $\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, 2017 at 2:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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