Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
4  
The condition is equivalent to saying that the convex hull of the rows of the adjacency matrix contains a multiple of the all-1s vector. –  Douglas Zare Jan 26 '10 at 8:18
    
How is an edge modified by the two vertex weights at its endpoints? They both multiply together to form the edge weight, add together, what? And if an edge is a self-loop, is it treated as having only one endpoint, or two endpoints that happen to be both the same? –  David Eppstein Jan 26 '10 at 16:57
    
when you consider a vertex v youtake sum w(u) for all edge {v,u} so the weight of v does not matter except when you have a loop (so when u=v) –  Gil Kalai Jan 26 '10 at 17:03
    
If the weight have to be positive, then the star with loops is not weighted-regular unless $k=1$. If not, then putting weights $0$ everywhere makes any graph weighted-regular. Or one can restricts to weights that can vanish but must not be all zero, but I guess a great many graphs are weighted-regular with this definition, if not all. –  Benoît Kloeckner May 2 '10 at 16:29

3 Answers 3

up vote 3 down vote accepted

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.

share|improve this answer

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.

share|improve this answer

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).

share|improve this answer
    
The same holds between regular graphs with some loops (loops contribute 1 to degree) and their weighted counterparts: going <=, when you clone a node v with a loop, connect each clone of v to each clone of v (including one loop per clone). The => quotient operation: given a regular graph G with loops, define u ~ v if neighbours(u)=neighbours(v) [a loop at u implies u in neighbours(u)]. ~ is an equivalence relation. Then, if R is any equivalence relation refining ~, the graph G/R (identify classes of R, delete || edges) is weighted-regular graph with loops; all can be obtained in this way. –  Dave Pritchard May 6 '10 at 13:17

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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