Tree-Like Structure Graphs with Full Diversity of Balls

Research output: Contribution to journalArticlepeer-review

Abstract

Under study is the diversity of metric balls in connected finite ordinary graphs considered as a metric space with the usual shortest-path metric. We investigate the structure of graphs in which all balls of fixed radius i are distinct for each i less than the diameter of the graph. Let us refer to such graphs as graphs with full diversity of balls. For these graphs, we establish some properties connected with the existence of bottlenecks and find out the configuration of blocks in the graph. Using the obtained properties, we describe the tree-like structure graphs with full diversity of balls.

Original languageEnglish
Pages (from-to)19-27
Number of pages9
JournalJournal of Applied and Industrial Mathematics
Volume12
Issue number1
DOIs
Publication statusPublished - 1 Jan 2018

Keywords

  • diversity vector of balls
  • full diversity of balls
  • graph
  • metric ball
  • number of balls
  • radius of a ball
  • tree-like structure graph

Fingerprint Dive into the research topics of 'Tree-Like Structure Graphs with Full Diversity of Balls'. Together they form a unique fingerprint.

Cite this