RUS  ENG JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB
 General information Latest issue Archive Impact factor Search papers Search references RSS Latest issue Current issues Archive issues What is RSS

 Sib. Èlektron. Mat. Izv.: Year: Volume: Issue: Page: Find

 Sib. Èlektron. Mat. Izv., 2016, Volume 13, Pages 375–387 (Mi semr682)

Discrete mathematics and mathematical cybernetics

Structure of the diversity vector of balls of a typical graph with given diameter

T. I. Fedoryaeva

Sobolev Institute of Mathematics, pr. Koptyuga, 4, 630090, Novosibirsk, Russia

Abstract: For labeled $n$-vertex graphs with fixed diameter $d\geq 1$, the diversity vectors of balls (the ith component of the vector is equal to the number of different balls of radius $i$) are studied asymptotically. An explicit description of the diversity vector of balls of a typical graph with given diameter is obtained. A set of integer vectors $\Lambda_{n,d}$ consisting of $\lfloor\frac{d-1}{2}\rfloor$ different vectors for $d\geq 5$ and a unique vector for $d<5$ is found. It is proved that almost all labeled $n$-vertex graphs of diameter $d$ have the diversity vector of balls belonging to $\Lambda_ {n,d}$. It is established that this property is not valid after removing any vector from $\Lambda_ {n,d}$. A number of properties of a typical graph of diameter $d$ is proved. In particular, it is obtained that such a graph for $d\geq 3$ does not possess the local $2$-diversity of balls and at the same time has the local $1$-diversity of balls, but has the full diversity of balls if $d=1,2$.

Keywords: graph, labeled graph, distance, metric ball, number of balls, diversity vector of balls, typical graph.

 Funding Agency Grant Number Russian Foundation for Basic Research 14-01-00507_à

DOI: https://doi.org/10.17377/semi.2016.13.033

Full text: PDF file (217 kB)
References: PDF file   HTML file

UDC: 519.1+519.173
MSC: 05C12
Received May 5, 2016, published May 18, 2016

Citation: T. I. Fedoryaeva, “Structure of the diversity vector of balls of a typical graph with given diameter”, Sib. Èlektron. Mat. Izv., 13 (2016), 375–387

Citation in format AMSBIB
\Bibitem{Fed16} \by T.~I.~Fedoryaeva \paper Structure of the diversity vector of balls of a typical graph with given diameter \jour Sib. \Elektron. Mat. Izv. \yr 2016 \vol 13 \pages 375--387 \mathnet{http://mi.mathnet.ru/semr682} \crossref{https://doi.org/10.17377/semi.2016.13.033} `

• http://mi.mathnet.ru/eng/semr682
• http://mi.mathnet.ru/eng/semr/v13/p375

 SHARE:

Citing articles on Google Scholar: Russian citations, English citations
Related articles on Google Scholar: Russian articles, English articles

This publication is cited in the following articles:
1. A. A. Evdokimov, T. I. Fedoryaeva, “Tree-like structure graphs with full diversity of balls”, J. Appl. Industr. Math., 12:1 (2018), 19–27
•  Number of views: This page: 190 Full text: 27 References: 21