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$}.
|