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




This article is cited in 1 scientific paper (total in 1 paper)
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{d1}{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.
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. È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 375387
\mathnet{http://mi.mathnet.ru/semr682}
\crossref{https://doi.org/10.17377/semi.2016.13.033}
Linking options:
http://mi.mathnet.ru/eng/semr682 http://mi.mathnet.ru/eng/semr/v13/p375
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:

A. A. Evdokimov, T. I. Fedoryaeva, “Treelike 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 
