|
| |
|
|
A347018
|
|
The number of unlabeled trees T on n vertices for which maximum multiplicity attained by any matrix whose graph is T implies the simplicity of its other eigenvalues.
|
|
0
|
|
|
|
1, 1, 1, 2, 3, 5, 8, 14, 24, 43, 74, 134, 238, 433, 778, 1416, 2564, 4676, 8498, 15507, 28246, 51568, 94049, 171734, 313417, 572377, 1044986, 1908527, 3485092, 6365294, 11624741, 21232255, 38778177, 70828006, 129363233, 236282260, 431563697, 788254745, 1439742242
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
1,4
|
|
|
COMMENTS
|
The trees counted by a(n) are called NIM trees on n vertices (No Intermediate Multiplicities). Equivalently, a(n) counts the trees on n vertices such that every vertex v of degree >= 3 satisfies two conditions:
(i) at most two branches at v have more than one vertex, and
(ii) at v has at least three adjacent vertices with degrees <= 3.
This is from the monograph "Eigenvalues, multiplicities and graphs" (see references).
Notice that they are restricted caterpillars: NIM trees are caterpillars on n vertices such that the following two conditions hold:
(i) Any degree sequence (...,a,b,c,...) for a>=4, b=4, c>=4 cannot be found in the degree sequence of the central path.
(ii) Any degree sequence (...,a,b,...) for a=3, b>=3, cannot be found in the degree sequence of the central path.
|
|
|
REFERENCES
|
Charles R. Johnson and Carlos M. Saiago, Eigenvalues, multiplicities and graphs, Cambridge University Press, 2018.
|
|
|
LINKS
|
|
|
|
FORMULA
|
Conjecture: For n>15, a(n) = 2*a(n-1) + a(n-2) - 3*a(n-3) + 2*a(n-4) - a(n-5) - 2*a(n-6) + a(n-7) + 3*a(n-8) - 4*a(n-9) - a(n-10) + 2*a(n-11) - 2*a(n-12) + 2*a(n-13) + a(n-14) - a(n-15), with initial terms a(1) through a(15) as given.
If the above conjecture holds, then a(n) has o.g.f. (x - x^2 - 2*x^3 + 2*x^4 - x^5 - x^6 + 2*x^7 - 3*x^9 + 2*x^10 + x^11 - x^12 + 2*x^13 - x^15)/(1 - 2*x - x^2 + 3*x^3 - 2*x^4 + x^5 + 2*x^6 - x^7 - 3*x^8 + 4*x^9 + x^10 - 2*x^11 + 2*x^12 - 2*x^13 - x^14 + x^15).
If the above conjecture holds, then a(n) has an explicit Binet-like formula that can be obtained in terms of the roots of a fifth-degree polynomial.
|
|
|
EXAMPLE
|
By degree sequence of the central path:
a(1): (0)
a(2): (1,1)
a(3): (1,2,1)
a(4): (1,2,2,1),(1,3,1)
a(5): (1,2,2,2,1),(1,2,3,1),(1,4,1)
a(6): (1,2,2,2,2,1),(1,2,3,2,1),(1,2,2,3,1),(1,2,4,1),(1,5,1)
a(7): (1,2,2,2,2,2,1),(1,2,4,2,1),(1,2,2,4,1),(1,2,2,3,2,1),(1,2,2,2,3,1),
(1,2,5,1),(1,3,2,3,1),(1,6,1)
a(8): (1,2,2,2,2,2,2,1),(1,3,2,2,2,2,1),(1,2,3,2,2,2,1),(1,2,2,3,2,2,1),
(1,4,2,2,2,1),(1,2,4,2,2,1),(1,5,2,2,1),(1,2,5,2,1),
(1,6,2,1),(1,3,2,3,2,1),(1,3,2,2,3,1),(1,7,1),
(1,4,2,3,1), (1,4,4,1)
|
|
|
MATHEMATICA
|
A[z_, u_, r_]:=r z^4 (1+u z+(u^2 z^4)/(1-u z^4));
Nsk[z_, u_, r_]:=r z(1/2 (1/(1-1/z A[z, u, r])+(1+1/z A[z, u, r])/(1-1/z^2 A[z^2, u^2, r^2]))-1)
alpha[z_, u_, r_]:=r A[z, u, r]+(2Nsk[z^2, u^2, r^2])/(z r) (1+A[z, u, r]/z);
beta[z_, u_, r_]:=-1/(r z) (1+A[z, u, r]/z);
Nsksym[z_, u_, r_]:=Sum[Product[beta[z^2^i, u^2^i, r^2^i], {i, 0, k-1}] alpha[z^2^k, u^2^k, r^2^k], {k, 0, 6}];
Nskasym[z_, u_, r_]:=Nsk[z, u, r]-Nsksym[z, u, r];
Nsksymodu[z_, u_, r_]:=(Nsksym[z, u, r]-Nsksym[z, -u, r])/2;
Nsksymodr[z_, u_, r_]:=(Nsksym[z, u, r]-Nsksym[z, u, -r])/2;
Nsksymevuevr[z_, u_, r_]:=(Nsksym[z, u, r]+Nsksym[z, -u, r]+Nsksym[z, u, -r]+Nsksym[z, -u, -r])/4;
Nsym[z_]:=Nsksymevuevr[z, 1/Sqrt[1-z^2], 1/Sqrt[1-z^2]]+(Sqrt[1-z^2]/(1-z))(Nsksymodr[z, 1/Sqrt[1-z^2], 1/Sqrt[1-z^2]])+(Sqrt[1-z^2]/(1-z))(Nsksymodu[z, 1/Sqrt[1-z^2], 1/Sqrt[1-z^2]]);
Nim[z_]:=(z/(1-z)+Nsym[z])+(Nskasym[z, 1/(1-z), 1/(1-z)]+1/2(Nsksymevuevr[z, 1/(1-z), 1/(1-z)]-Nsksymevuevr[z, 1/Sqrt[1-z^2], 1/Sqrt[1-z^2]])+1/2 (Nsksymodr[z, 1/(1-z), 1/(1-z)]-Sqrt[1-z^2]/(1-z) Nsksymodr[z, 1/Sqrt[1-z^2], 1/Sqrt[1-z^2]])+1/2 (Nsksymodu[z, 1/(1-z), 1/(1-z)]-Sqrt[1-z^2]/(1-z) Nsksymodu[z, 1/Sqrt[1-z^2], 1/Sqrt[1-z^2]]));
TableForm[Table[{i, Coefficient[Series[Nim[z]/.{u -> 1, r -> 1}, {z, 0, 50}], z^i]}, {i, 1, 50}]]
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
