login
A278636
List of dense centipedes in increasing order of nomenclature.
1
2, 2, 2, 3, 2, 4, 3, 3, 2, 2, 2, 2, 5, 3, 4, 2, 2, 3, 2, 3, 2, 2, 6, 3, 5, 4, 4, 2, 2, 4, 2, 3, 3, 3, 2, 3, 2, 2, 2, 2, 2, 7, 3, 6, 4, 5, 2, 2, 5, 2, 3, 4, 2, 4, 3, 2, 5, 2, 3, 2, 4, 2, 2, 2, 3, 2, 2, 3, 2, 2, 8, 3, 7, 4, 6, 5, 5, 2, 2, 6, 2, 3, 5, 2, 4, 4, 2, 5, 3, 2, 6, 2, 3, 2, 5, 3, 3, 4, 3, 4, 3, 4, 2
OFFSET
4,1
COMMENTS
This sequence gives a list of all dense centipedes in increasing order of diameter and of nomenclature. In graph theory, a centipede is a tree which consists of a diametrical path P whose deletion leaves only isolated vertices (as defined by Nair and Shader). A non-terminal vertex of the diametrical path P which has at least one pendant vertex adjacent to it is called a joint. A centipede in which every non-terminal vertex is a joint is called a dense centipede. The induced subgraph of a dense centipede formed with a joint and all the pendant vertices attached to it is called a cluster. A dense centipede is completely described if the number of clusters and the number of vertices in each cluster is known. If d(T) is the diameter of the dense centipede, then the number of clusters is r=d(T)-1. So if N_1,N_2,N_3,...,N_r are the numbers of vertices in the r clusters, then the dense centipede is named as (N_1,N_2,...,N_r) provided the number 10^(r-1)N_1 + 10^(r-2)N_2 + ... + N_r is smaller than the number with the "digits" reversed, i.e., 10^(r-1)N_r + 10^(r-2)N_(r-1) + ... + N_1, otherwise it is named as (N_r,N_(r-1),...,N_2,N_1). The only centipede on 4 vertices is (2,2) and so 2,2 form the first two terms of the sequence. The dense centipede on 5 vertices is (2,3). Dense centipedes on 6 vertices are (2,4), (3,3) and (2,2,2). This sequence is a flattening of this process of nomenclature of dense centipedes. Hence the sequence goes 2,2,2,3,2,4,3,3,2,2,2 and so on.
LINKS
Reshmi Nair and Bryan L. Shader, Acyclic matrices with a small number of distinct eigenvalues, Linear Algebra and its Applications 438, 4075-4089, 2013.
Debashish Sharma, Mausumi Sen, Description of dense centipedes
Debashish Sharma, Mausumi Sen, Inverse eigenvalue problems for acyclic matrices whose graph is a dense centipede, Special Matrices 6.1 (2018): 77-92. Special Issue on Linear Algebra and its Applications (ICLAA 2017).
EXAMPLE
Let n be the number of vertices of a dense centipede.
For n=4, the dense centipede is (2,2).
For n=5, the dense centipede is (2,3).
For n=6, the dense centipedes are (2,4), (3,3) and (2,2,2).
For n=7, the dense centipedes are (2,5), (3,4), (2,2,3) and (2,3,2).
CROSSREFS
Sequence in context: A317223 A321576 A304101 * A376497 A126336 A364421
KEYWORD
nonn
AUTHOR
Debashish Sharma and Mausumi Sen, Nov 24 2016
STATUS
approved