Periodic Vertices | Laplacian

Laplacian Matrix

We now consider the Laplacian matrix $L$ of a connected graph $X$ on at least two vertices. Since $0$ is an eigenvalue of $L$ with $\one$ as an eigenvector, it is in the eigenvalue support of every vertex. Consequently, the second case of Theorem 1 will never occur for a periodic vertex. Hence we have

(Characterizing Laplacian periodicity): For a connected graph with at least two vertices, the vertex $v$ is periodic with respect to the Laplacian matrix if and only if the eigenvalues in $S(v)$ are all integers.

Likewise, Theorem 2 reduces to the following

(Determining the Laplacian period): Let $v$ be a periodic vertex with respect to the Laplacian matrix of a connected graph with at least two vertices. Let \[ g = \gcd\{\theta_r: \theta_r\in S(v)\}. \] Then the minimum period of $v$ is $\tau = 2\pi/g$.

We applied the above theorems to Laplacian matrices of connected graphs with up to eight vertices. The proportion of graphs with periodic vertices is strictly decreasing, as shown in the table below.

# vertices	# connected graphs	# with periodic vertices	proportion
1	1	1	1
2	1	1	1
3	2	2	1
4	6	5	0.833
5	21	13	0.619
6	112	50	0.446
7	853	191	0.224
8	11117	1265	0.114

Let us consider the trees. All the vertices of a star are periodic, since its Laplacian eigenvalues are integers. If a tree $T_n$ on $n$ vertices is periodic at some vertex, then the product of the non-zero integer eigenvalues of $T_n$ must be $n$. Thus if $n$ is a prime, then $T_n = K_{1,n-1}$. Here are the trees on up to 16 vertices that have a periodic vertex.

We also found all the graph with periodic vertices on up to eight vertices, with the drawings in .pdf format and the full data in .sobj format. For each graph, we divided the vertices into orbits of the automorphism group, and only tested the representative of each orbit. The data is saved in a dictionary with items of the form:

(graph6_string: [orbit representative, minimum period, orbit, dual degree, $\Delta$]).

We added the last entry to keep the format consistent with the adjacency case. Here $\Delta = 1$.