Distance degree regular graphs
Let G be a finite undirected graph without loops and multi-edges. Let d(u,v) denote the distance between two vertices u and v of G. For every vertex u and nonnegative integer i the authors define \(\Gamma_ i(u)=\{v\in V: d(u,v)=i\}.\) A graph is distance degree regular if \(| \Gamma_ i(u)| =| \Gamma_ i(v)|,\) for all u, v in G and nonnegative integers i, where \(| A|\) is the number of elements in the set A. Finally, if G is a distance degree regular graph, then let \(k_ i(G)=| \Gamma_ i(u)|\). Now let G be a connected distance degree regular graph whose diameter, d(G), is greater than or equal to 2. The authors prove that, for every integer r, \(1\leq r\leq d(G)\), \(3k_ r(G)\geq 2(k_ 1(G)+1),\) and that if \(3k_ r(G)=2(k_ 1(G)+1)\) holds for some integer r, then \(G=C_ n| K_ m|\).
scientific article; zbMATH DE number 3904616