Minimal Eccentric Sequences
by
P. Hrnčiar
Banská Bystrica
Coauthors: A. Haviar (Banská Bystrica), G. Monoszová (Banská Bystrica)

A sequence of positive integers is called eccentric if there is a graph which realizes the considered sequence as the sequence of its eccentricities. An eccentric sequence is called minimal if it has no proper eccentric subsequence with the same number of distinct eccentricities.

All minimal eccentric sequences with least eccentricity at most two were found by R. Nandakumar. The following result holds if least eccentricity is three.

Theorem 1 There are exactly 13 minimal eccentric sequences with least eccentricity three, namely     3⁶;    3⁵, 4²;    3⁴, 4⁴;    3³, 4⁶;    3², 4⁸;    3, 4¹⁰;    3, 4², 5¹²;    3, 4³, 5⁹;    3, 4⁴, 5⁷;    3, 4⁵, 5⁴;    3, 4⁷, 5²;    3², 4², 5²;    3, 4², 5², 6².

We have also investigated minimal eccentric sequences with two distinct eccentricities.

Theorem 2 All minimal eccentric sequences of type

r\alpha, (r+1)\beta for r >= 3 and \alpha+\beta <= min { 3r-2, (8r+5)/3 }

are r^2r-1, (r+1)²,
r^2r-2, (r+1)⁴,
r^2r-2i+1, (r+1)³ⁱ i=2, 3, ..., [(2r+1)/3],
r^2r-2i, (r+1)³ⁱ⁺² i=2, 3, ..., [(2r-1)/3].

Date received: May 26, 2000

Copyright © 2000 by the author(s). The author(s) of this document and the organizers of the conference have granted their consent to include this abstract in Atlas Conferences Inc. Document # cafd-09.