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
Debashish Sharma, List of dense centipedes for n=4 to n=10
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
KEYWORD
nonn
AUTHOR
Debashish Sharma and Mausumi Sen, Nov 24 2016
STATUS
approved