Nonexistence of Cubic DDI Graphs of Order 16 with Diameters 4, 5, 6.

Abstract

The eccentricity e(u) of a vertex u is the maximum distance of u to any other vertex of G. The distance degree sequence (dds) of a vertex v in a graph G = (V, E) is a list of the number of vertices at distance 1, 2, ..., e(u) in that order, where e(u) denotes the eccentricity of v in G. Thus, the sequence ( , , , ..., , ...) di0 di1 di2 di j is the distance degree sequence of the vertex vi in G, where di j denotes the number of vertices at distance j from vi. A graph is distance degree regular (DDR) graph if all the vertices have the same distance degree sequence. A graph is distance degree injective (DDI) graph if no two vertices have the same distance degree sequence. In this paper, we prove that there does not exist cubic DDI graphs of order 16 with diameters 4, 5, 6.