A278636 List of dense centipedes in increasing order of nomenclature.

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

Table of n, a(n) for n=4..106.

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

Sequence in context: A317223 A321576 A304101 * A126336 A364421 A352631

Adjacent sequences: A278633 A278634 A278635 * A278637 A278638 A278639

Keyword

nonn

Author

Debashish Sharma and Mausumi Sen, Nov 24 2016

Status

approved