Weighted Regular Graphs

Question

The following graph theoretic notion appeared in an economics paper entitled: "Prize competition under limited comparability, by Michele Piccione and Ran Spiegler which studies models of economics were the firms are rational but the consumers are not.

A graph is weighted-regular if vertices (nodes) can be assigned positive weights, such that each node has the same total weighted-expected-number of edges (links). Every regular graph is, of course, weighted regular (give all vertices weight 1). A star, tree with center vertex connected to k leaves is weighted-regular: Give the center weight 1 and every leaf weight 1/k.

(In the paper, every vertex is also contained in a loop. Therefore its weight also counts when we compute its weighted-expected-number of edges. The star is still weighted-regular: give weight 1 to the center and weight 0 to the leafs.)

Is there a characterization of weighted-regular graphs? Is this notion known? Does it have known applications or connections?

Answer 1

The examples you gave can be extended. If a graph has a transitive group then it is weighted regular. Also if the graph such that one point is connected to all other points and if that point is removed the graph remaining has a transitive group then it is weighted regular.

Also there exists graphs that are not weighted regular Look at the graph on 5 points and look at the following graph 1 is connected to all other points for $n$ equal to 2 through 4 $n$ is connected to $n+1$. Then the sum of the weights on 3 and 4 is equal to the sum of the weights on all points of the graph plus the sum of weight one. The sum of the weights on 2 and 5 is the sum the weights on 3 and 4 plus twice the weight of 1. Combining these two results forces the weight on 2 and 5 to be zero and hence not positive so not all graphs are weighted regular.

Also for any graph if a point $x$ connects only to a point $y$ then if $z$ connects to point $y$ it cannot connect to any other point t if it does since the weights of $z$ and $x$ are the same the value assigned to $y$ must equal the sum of the values assigned to $y + t$ and hence $t$ is forced to be zero. This means that the only tree which can be weighted regular is a star and the only forest one with each component a star and if any graph has a component with a vertex connected to only one point it must be a star.

The join of any two weighted regular graphs is weighted regular. Let the graphs be $G$ and $H$ with $m$ and $n$ points respectively. Let there weights assigned to each graph so that each node in each graph has the same weight. Let the weight of each node in $G$ be $w_1$ and the weight of each node in $H$ be $w_2$. Let the sum of the weights of $G$ be $w_3$ and the sum of the weights of $H$ be $w_4$. multiply the weights of $G$ by $a$ and $H$ by $b$. Then the weight of any node of $G$ in the join is $aw_1 + bw_4$ and of any node of H in the join is $aw_2 + bw_3$ so for the join to be a weighted regular graph $aw_1 + bw_4 = bw_2 + aw_3$ or $a(w_1-w_3)= b (w_2-w_4)$ or $a/b =(w_1-w_3)/(w_2-w_4)$ we can find such $a$ and $b$ iff $w_1$ is not equal to $w_3$ and $w_2$ is not equal to $w_4$.But the sum of the weights on all points is not equal to the sum of the weights on all points on graph so that condition is satisfied.

Now using the comment by Douglas Zare that the convex hull of the rows of the adjacency matrix contains a multiple of the all-1s vector we can find whether any graph is weighted regular in polynomial time. We can convert it to a linear programming problem and there algorithms such as the ellipsoid method that solve linear programming problems in a polynomial amount of time.

In this paper: "On quantum perfect state transfer in weighted join graph" available at the URL: http://arxiv.org/abs/0909.0431 the concept of a weighted regular graph is applied to perfect state transfer on quantum networks.

Answer 2

Denoting by $A$ the $n\times n$ adjaceny matrix (with loops contributing $1$ on the diagonal) of a finite graph $\Gamma$ with $n$ vertices, a necessary condition for $A$ to be weighted-regular is the fact that the all $1$ vector $I_n=(1,1,\dots,1)$ of dimension $n$ is in the image of $A$. This is the case if and only if $I_n$ is orthogonal to the kernel $\ker(A)$ of $A$.

If this necessary condition holds, the vector $I_n$ can be written uniquely as $$I_n=\sum_{\lambda\in{\mathrm Spec}(A)\setminus\{0\}}v_\lambda$$ where the sum is over all distinct non-zero eigenvalues of $A$ with $v_\lambda$ denoting the orthogonal projection of $I_n$ onto the eigenspace of eigenvalue $\lambda$. The graph $\Gamma$ is now weighted-regular if and only if the affine subspace $\sum_{\lambda}\frac{1}{\lambda}v_\lambda+\ker(A)$ (corresponding to the set of preimages of $I_n$) intersects the open cone $({\mathbb R}_{>0})^n$ of vectors having only strictly positive coordinates. This last condition can be checked by linear programming by optimizing an arbitrary linear functional (eg. the coordinate sum) on $\ker(A)$ subject to the condition that all coefficients of the solution are strictly greater than the corresponding coefficients of $I_n-\sum_{\lambda}\frac{1}{\lambda}v_\lambda$.

In particular, a graph $\Gamma$ with invertible adjacency matrix $A$ is weighted-regular if and only if all coordinates of the vector $\sum_\lambda \frac{1}{\lambda}v_\lambda$ are strictly positive and these coordinates give the unique set of weights (up to multiplication by a positive constant) turning $\Gamma$ into a weighted-regular graph.

This is of course nothing else than Kristall Cantwell's remark, fleshed out.

Answer 3

Here's an observation about a relation between regular and weighted-regular graphs, when loops are disallowed.

From any weighted-regular graph with (wolog by the polyhedral characterization) integral weights, replace each vertex v with weight(v) clones. The new graph has |V| equal to the original weight sum. For each edge uv in the old graph, connect every clone of u to every clone of v in the new graph (so there is a complete bipartite $K_{weight(u), weight(v)}$ between the clones of u and v). Then this is a regular graph.

Conversely, you can reverse this, so you should be able to define a one-to-many type of "quotient" (to reverse the above construction) which takes any regular graph to a weighted-regular graph, and is surjective (generates all loopless weighted-regular graphs).