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






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


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{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. È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}


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

    SHARE: VKontakte.ru FaceBook Twitter Mail.ru Livejournal Memori.ru


    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  mathnet  crossref  crossref  elib
  • Number of views:
    This page:190
    Full text:27
    References:21

     
    Contact us:
     Terms of Use  Registration  Logotypes © Steklov Mathematical Institute RAS, 2020