Given a (connected) graph $G$ it is natural to want to rank its vertices, with the more "central" vertices ranked higher.


Two natural ways of doing it are:


1. By the degrees.
2. By the entries in a Perron eigenvector of the adjacency matrix.


These two methods coincide for regular graphs and for so-called harmonic graphs (defined as graphs in which the degree vector is an eigenvector) - which is all a tad trivial. 


What is more interesting is that for many random graphs I've checked the two orderings coincide as well and I am able to show that they coincide for threshold graphs.



> 
> Have such graphs been studied?
> 
> 
> 


I did find in the mathematical sociology literature some work on the question when the most central vertex w.r.t both rankings is the same but nothing for the whole vector.


(If such graphs haven't been named yet, I propose to call them **tranquil**, since tranquility is a lesser form of harmony). 


P.S.
Method 2 is essentially what Google does in its PageRank algorithm.



Coherence between different ranking methods of a graph's vertices
I'm not sure how common this is. It may depend on how you are determining random graphs. 


There may be ties so let me separate the issues of the equivalence relation "same rank" from those of the linear order among equivalence classes. In the case of ranking by degrees there will have to be at least one tie. In the case of the Perron ranking there might or might not be any ties. Vertices in the same orbit of the automorphism group will have the same rank in the Perron ranking (and equal degree). In the simplest graph with no automorphisms ( A seven vertex tree with leaves at distances $1,2,$ and $3$ from a central vertex) no two vertices get the same weight. It **is** true for this graph that the three lowest weights occur on the degree $1$ vertices and the highest weight on the unique degree $3$ vertex. Is this what you mean? Otherwise I'd expect "most" trees to fail.


Since vertices in the same orbit of the automorphism group will have the same rank in either system. If the automorphism group is degree transitive there is some chance that the two equivalence relations will be the same. This would partly explain [threshold graphs](https://en.wikipedia.org/wiki/Threshold_graph). I say partly because I have not shown that the linear order on equivalence classes is according to degree. Perhaps this additional condition (which holds for threshold graphs) is enough: If there is a path $u,v,w$ with $v$ having lower degree than $u$ or $w$, then there is also an edge $u,w.$ That is just a guess, but I give an example below where this condition does not hold and the linear orders are not the same.


At the end I note a weaker condition than degree transitivity which suffices for same degree vertices to have equal Perron rank. It is useful for analyzing examples such as the following one:


Here is a rather symmetric graph where the linear order fails: Consider a graph with $26$ vertices belonging to classes $A,B,C,D$ of respective sizes $9,3,12,2$ and respective degrees $1,7,2,6.$ Each vertex in $B$ is connected to $3$ vertices from $A$ and $4$ from $C$ while each vertex in $D$ is connected to $6$ vertices from $C.$ Then the largest eigenvalue is roughly $3.38$ and a Perron eigenvector assigns weights of roughly $0.267,0.904,0.563,1$ to the classes. So the two degree $6$ vertices receive higher weight than the three degree $7$ vertices. In the similar example with degrees $1,5,2,4$ the vertices of degrees $4$ and $5$ both get equal weight.


Somewhat more general than degree transitivity is degree regularity: Suppose that the existing degrees are $d\_1,d\_2,\cdots,d\_k$ and that there are $k^2$ integers $n\_{ij}$ so that each vertex of degree $d\_i$ has exactly $n\_{ij}$ neighbors of degree $d\_j$. Then the (right) Perron eigenvector of the $k \times k$ matrix with entries $n\_{ij}$ lifts in an obvious way to the graph.


