DynkinDiagram

2662 days ago by chlin

latex.add_package_to_preamble_if_available("tikz") 
       
n=6; def An(n): #n >= 2 return graphs.PathGraph(n); def Anh(n): return graphs.CycleGraph(n+1); def Dn(n): #n>=4 Dn=graphs.PathGraph(n-1); Dn.add_vertex(n-1); Dn.add_edge(n-1,1); return Dn; def Dnh(n): Dnh=graphs.PathGraph(n-1); Dnh.add_vertex(n-1); Dnh.add_edge(n-1,1); Dnh.add_vertex(n); Dnh.add_edge(n-3,n); return Dnh; E6 = Graph({0:[1,2],1:[0],2:[0,3,5],3:[2,4],4:[3],5:[2]}); E6h = Graph({0:[1,2],1:[0],2:[0,3,5],3:[2,4],4:[3],5:[2,6],6:[5]}); E7 = Graph({0:[1],1:[0,2],2:[1,3],3:[2,4,6],4:[3,5],5:[4],6:[3]}); E7h = Graph({0:[1],1:[0,2],2:[1,3],3:[2,4,7],4:[3,5],5:[4,6],6:[5],7:[3]}); E8 = Graph({0:[1],1:[0,2],2:[1,3,7],3:[2,4],4:[3,5],5:[4,6],6:[5],7:[2]}); E8h = Graph({0:[1],1:[0,2],2:[1,3,8],3:[2,4],4:[3,5],5:[4,6],6:[5,7],7:[6],8:[2]}); EE=[E6,E7,E8]; EEh=[E6h,E7h,E8h]; def spectral_radius(g): A=g.adjacency_matrix(); return max(A.eigenvalues()); 
       
for g in EEh: print g.order(),spectral_radius(g); print "E6h,E7h,E8h has spectral radius 2." 
       
7 2
8 2
9 2
E6h,E7h,E8h has spectral radius 2.
7 2
8 2
9 2
E6h,E7h,E8h has spectral radius 2.
for n in range(3,11): A=Anh(n).adjacency_matrix(); print n, max(A.eigenvalues()); print "Cycles is 2-regular, so they have spectral radius 2." 
       
3 2
4 2
5 2
6 2
7 2
8 2
9 2
10 2
Cycles is 2-regular, so they have spectral radius 2.
3 2
4 2
5 2
6 2
7 2
8 2
9 2
10 2
Cycles is 2-regular, so they have spectral radius 2.
for n in range(4,11): A=Dnh(n).adjacency_matrix(); print n, max(A.eigenvalues()); print "There is a positive labelling to vertices such that the label of each vertex is half of the sum of its neighbors' labellings." 
       
4 2
5 2
6 2
7 2
8 2
9 2
10 2
There is a positive labelling to vertices such that the label of each
vertex is half of the sum of its neighbors' labellings.
4 2
5 2
6 2
7 2
8 2
9 2
10 2
There is a positive labelling to vertices such that the label of each vertex is half of the sum of its neighbors' labellings.
%latex \textbf{Claim:} If the spectral radius of $G$ is at most $2$, then it must be a subgraph of the one of $\hat{A}_n (n\geq 2)$, $\hat{D}_n (n\geq 4)$, $\hat{E}_6$, $\hat{E}_7$, $\hat{E}_8$. \textbf{Proof:} Suppose $G$ has radius at most $2$. By Perron-Frobenius Theorem, $G$ is a graph without a subgraph of $\hat{A}_n (n\geq 2)$, $\hat{D}_n (n\geq 5)$, $\hat{E}_6$, $\hat{E}_7$, $\hat{E}_8$. Then $G$ must be a tree, since $G$ has no subgraph as a cycle, $\hat{A}_n$. If $G$ has two high-degree vertices, then $G$ must contain a $\hat{D}_n$, so we may assume $G$ is a generalized star. Let $G=S(a_1,a_2,\ldots, a_k)$, the graph obtained by using a vertex and $k$ edges to link several paths $P_{a_1},P_{a_2},\ldots P_{a_k}$. Say $a_1\geq a_2\geq \cdots \geq a_k$. If $k\geq 4$, then $\hat{D}_4$ is a subgraph, so $k\leq 3$. If $k\leq 2$, then $G$ is a {\color{red}path, which is a subgraph} of $\hat{A}_n$, so we may assume $k=3$. We know $a_3=1$, for otherwise $\hat{E}_6$ is a subgraph. We know $a_2$ is $1$ or $2$, for otherwise $\hat{E}_7$ is a subgraph of $G$. If $a_2=1$, then {\color{red} $S(a_1,1,1)$ is a subgraph of $\hat{D}_n$}. If $a_2=2$, then $a_1\leq 4$, for otherwise $\hat{E}_8$ is a subgraph. However, now {\color{red}$S(a_1,2,1)$ with $a_1\leq 3$ is also a subgraph of $\hat{E}_7$}.