\documentclass[11pt,reqno]{amsart}
\usepackage[cp1251]{inputenc}
\usepackage[english,russian]{babel}
\usepackage{amsmath}
\usepackage{amssymb}
\usepackage{amsfonts}
\usepackage{graphicx}
\usepackage{xcolor}
\usepackage[colorlinks]{hyperref}
\usepackage{cite}


\usepackage{titlesec}
\titlespacing{\section}{0pt}{2.5ex}{1.5ex}
\titlespacing{\subsection}{0pt}{1.5ex}{1ex}
\titlespacing{\subsubsection}{0pt}{1.5ex}{1ex}
\titleformat{\section}{\large\bfseries\centering}{\thesection}{1em}{}
\titleformat{\subsection}[runin]{\bfseries}{\thesubsection.}{0.5em}{}[.\mbox{\ }]
\titleformat{\subsubsection}[runin]{\bfseries}{\thesubsubsection.}{0.4em}{}[.\mbox{\ }]



%%%%%---------- ORCiD
\newcommand\orcidicon[1]{\href{https://orcid.org/#1}{\includegraphics[scale=0.02]{orcid.pdf}}}

\def\udcs{519.174.2+519.175.4} %Здесь автор определяет УДК своей работы
\def\mscs{05C45+05C80} %Здесь автор определяет классификаторы AMS своей работы
\setcounter{page}{144}

%\newtheorem{lemma}{Лемма}
%\newtheorem{theorem}{Теорема}
%\newtheorem{definition}{Определение}
%\newtheorem{corollary}{Следствие}
%\newtheorem{proposition}{Предложение}

\newtheorem{lemma}{Lemma}
\newtheorem{theorem}{Theorem}
\newtheorem{definition}{Definition}
\newtheorem{corollary}{Сorollary}
\newtheorem{proposition}{Proposition}
\newtheorem{remark}{Remark}


\definecolor{myblue}{rgb}{0.03, 0.27, 0.79}

\hypersetup{linkcolor=blue,filecolor=black,urlcolor=blue, citecolor=blue}

\def\logo{\textcolor{blue}{{\bf\Huge S\raisebox{0.2ex}{\hspace{0.55ex}\raisebox{0.05ex}e\hspace{-1.65ex}$\bigcirc$}MR}}}

\def\semrtop
     {
  \vbox{
     \noindent\logo \hspace{-3mm}  \parbox{12cm}{     \begin{center}
     {\LARGE \textsf{СИБИРСКИЕ ЭЛЕКТРОННЫЕ}} \\[2mm]
     {\LARGE \textsf{МАТЕМАТИЧЕСКИЕ ИЗВЕСТИЯ}} \\[2mm]
     {\Large \textsf{Siberian Electronic Mathematical Reports}} \\[1mm]
     {\Large\tt{\textcolor{blue}{http://semr.math.nsc.ru}}}\\[1mm]
     \raisebox{1ex}{ISSN 1813-3304 }
     \vspace*{-3mm}
%     {\small Институт математики им. С.Л.Соболева СО РАН}\\[-1mm]
%     {\small Sobolev Institute of Mathematics SB RAS}
     \end{center}
}
     \vspace{-1mm}
     \noindent
      \begin{tabular}{c}
     \hphantom{aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa!} \\
     \hline\hline
     \end{tabular}

     \vspace{3mm}
     {\flushleft\it Том 21, № 2, стр. 144--145 (2024) \hspace{\fill}{\rm\small УДК \udcs \hspace{-3mm}}}
     \newline
        {\rm\small \textcolor{blue}{https://doi.org/10.33048/semi.2024.21.???}}\hphantom{aaaaaaaaaaaaaaaaa\;}{\rm\small MSC\ \ \mscs }
  }%\vbox
}



\begin{document}
\renewcommand{\refname}{References}
\renewcommand{\proofname}{Proof}
\renewcommand{\figurename}{Fig.}
\renewcommand{\thesection}{\arabic{section}.\hspace{-3mm}}

\thispagestyle{empty}

\title[\sc Are almost all graphs of given diameter Hamiltonian?]
{\large Are almost all $n$-vertex graphs\\ of given diameter Hamiltonian?}
\author[T.I. FEDORYAEVA]{{\bf \large \textsc{T.I. Fedoryaeva}}\protect\orcidicon{0000-0002-5246-0522}\\ \\
\textit{Представлено} \textsc{П.П. Петровым} %\textit{(заполняется редактором)}
}%
\address{Tatiana Ivanovna Fedoryaeva % Контактные данные всех авторов и место работы указываются только на английском языке
\newline\hphantom{iii} Sobolev Institute of Mathematics,
\newline\hphantom{iii} pr. Koptyuga, 4,
\newline\hphantom{iii} 630090, Novosibirsk, Russia}%
\email{\textcolor{blue}{fti@math.nsc.ru}}%

\thanks{\sc Fedoryaeva, T.I.,
Are almost all $n$-vertex graphs of given diameter Hamiltonian?}
\thanks{\copyright \ 2024 Fedoryaeva T.I}
\thanks{\rm The work was performed  according to the Government
research assignment for IM SB RAS, project FWNF-2022-0017}
\thanks{\it Received December, 1, 2024, published December, 1, 2024}%


\semrtop \vspace{1cm}
\maketitle {\small
\begin{quote}
\noindent{\bf Abstract:} Typical Hamiltonian properties of the class
of $n$-vertex graphs of a fixed diameter $k$ are studied. A new
class of typical $n$-vertex graphs of a given diameter is
constructed.

The question of S.V.~Avgustinovich on the Hamiltonian property of
almost all such $n$-vertex graphs has been solved.  It is proved
that almost all $n$-vertex graphs of fixed diameter $k=1,2,3$ are
Hamiltonian, while almost all $n$-vertex graph of fixed diameter
$k\geq 4$ are nonHamiltonian graphs. All found typical Hamiltonian
properties of $n$-vertex graphs of a fixed diameter $k\geq 1$ are
also typical for connected graphs of diameter at least $k$, as well
as for graphs (not necessarily connected) containing the shortest
path of length at least $k$.
\medskip

\noindent{\bf Keywords:} graph, Hamiltonian graph, Hamiltonian
cycle, diameter, typical graphs, almost all graphs.
 \end{quote}
}

\bigskip


\section*{Introduction}
\hspace*{\parindent} We study Hamiltonian property for finite
labeled ordinary n-vertex graphs of a given diameter. For a
connected graph $G=(V,E)$, {\it the distance} $\rho_G(u,v)$ between
its vertices $u,v\in V$ is defined as the length of the shortest
path connecting these vertices. In this case, $d(G)= \max_{u,v\in V}
\rho_G(u,v)$ is {\it the diameter} of graph $G$. A cycle which
passes through every vertex of the graph exactly once is called {\it
Hamiltonian}. A graph is {\it Hamiltonian} ({\it nonHamiltonian}) if
it contains (does not contain) a Hamiltonian cycle.

Hamiltonicity is one of the central concepts of Graph Theory, also
arising in various applied problems, when it is required to find out
the presence of a Hamiltonian cycle for a graph modeling the problem
under consideration. By now, a huge number of papers have been
written on this topic. Many ideas that arose here still go back to
the classical results of Dirac and Ore, who first opened this
"Pandora's box". The main course of research development and the
results obtained on the topic of Hamiltonian graphs in various
directions can be found in the surveys \cite{obzor1991} and
\cite{ush}. As it turns out, the problem of deciding whether a graph
is Hamiltonian is an $NP$-complete problem, and accordingly one
cannot expect a simple classification of graphs that have this
property.

The complexity of the problem and the diversity of Hamiltonian
graphs encountered also led to the development of an asymptotic or
probabilistic approach to the study of Hamiltonicity, in particular,
an approach conditioned by the concept of almost all. A number of
results were obtained along this path, opening up the subject of
research into Hamiltonicity in this direction. Thus, considering all
$n$-vertex graphs, Yu.D.~Perepeliza \cite{perepel} and J.W.~Moon
\cite{moon72} proved that almost all graphs are Hamiltonian. There
are also a number of papers in which the Hamiltonian property is
studied within given classes of graphs. Of particular interest here
is the classes in which sufficient conditions for the existence of a
Hamiltonian cycle are satisfied for all or almost all graphs, and
the verification and construction of such a cycle is implemented
polynomially. In particular, problems about Hamiltonicity of regular
and Cayley graphs are known. It was found that almost all Cayley
graphs \cite{jixt} and almost all $r$-regular graphs for every
$r\geq 3$ \cite{robin} are Hamiltonian.

It is well-known that almost all graphs have diameter $2$
\cite{moon66}. From this result of J.W.~Moon and L.~Moser, and
Yu.D.~Perepeliza's Theorem, it is easy to obtain that almost all
$n$-vertex graphs of diameter $2$ are Hamiltonian (see, for detail,
Section $2$). In this regard, the question naturally arises about a
Hamiltonian property of almost all $n$-vertex graphs of a fixed
diameter $k$. This problem was posed by S.V.~Avgustinovich.

In the present paper, an answer to this one is obtained. Previously,
the author investigated asymptotically the class of $n$-vertex
graphs of a fixed diameter. A number of typical properties of graphs
under consideration were found (for more information, see survey
article \cite{fti22-3}). In the present paper, for every $\Delta$,
$0<\Delta <1,$ a new class ${\mathcal H}_{n,k,\Delta}$ of typical
$n$-vertex graphs of a given diameter $k$ is constructed in Section
2 (Theorem \ref{t1b}). In Section 3, based on the found typical
properties and Theorem \ref{t1b}, we establish when almost all such
graphs are Hamiltonian. It turned out that almost all $n$-vertex
graphs of given diameter $k=1,2,3$ are Hamiltonian and are
nonHamiltonian for every fixed $k\geq 4$ (Theorem \ref{t2x}).

All obtained typical Hamiltonian properties for $n$-vertex graphs of
a fixed diameter $k\geq 1$ remain typical for connected graphs of
diameter at least $k$, as well as for graphs (not necessarily
connected) containing a shortest path of a length at least $k$
(Corollary \ref{s6x}).


\section{Preliminary information}
\hspace*{\parindent} The article uses the generally accepted
concepts and notation of graph theory \cite{emel90, xar69}, as well
as the standard concepts of combinatorial analysis \cite{grah94}. We
consider only finite ordinary (i.e.,\/ without loops and multiple
edges) graphs $G=(V, E)$ with set of vertices $V=\{1,2,\ldots,n\}$,
$n\in {\mathbb N}$. As usual, a graph $G$ is {\it $s$-connected} if
its connectivity is at least $s$, a set $S\subseteq V$ is {\it the
independence set} of graph $G$ if all vertices in $S$ are pairwise
non-adjacent in $G$, {\it the number of independence} of a graph is
the greatest cardinality of its independent sets. Let $\alpha(G)$
denote the number of independence of graph $G$, $B_i^G(v)=\{u\in
V\,|\, \rho_G(v,u)\leq i \}$ is {\it a ball of radius $i$ centered
at a vertex} $v\in V$ in the metric space of graph $G$ with the
metric $\rho_G$, $S_i^G(v)=\{u\in V\,|\, \rho_G(v,u)=i\; \}$ is {\it
a sphere of radius $i$ centered at a vertex} $v\in V$, $K_n$ ---
{\it a complete} $n$-vertex graph. For a path $P$ with endpoints
$v_0$ and $v_n$, sequentially passing through vertices $v_0,
v_1,\ldots, v_n$, the notation $P(v_0, v_1, \ldots, v_n)$ is used. A
shortest path of length $d(G)$ is {\it the diametral path} of the
graph $G$, and under by {\it a pair of diametral vertices} we mean
an unordered sample of two vertices from the set $V$, the distance
between which is equal to the diameter, a vertex of degree $1$ is
{\it pendant}.

We will write $\lfloor x \rfloor$ to denote the largest integer less
or equal to a real nonnegative number $x$ and further apply the
following well-known binomial identity
\begin{equation} \label{f1h}
\binom{n-m}{2}=\binom{n}{2}-nm+\frac{m(m+1)}{2}\,.
\end{equation}
To denote {\it the asymptotic equality} of functions $f(n)$ and
$g(n)$ as $n$ tends to infinity, we use the notation $ f(n)\sim
g(n)$, which by definition means that
$\lim_{n\rightarrow\infty}\frac{f(n)}{g(n)}=1$ or, equivalently,
$f(n) = g(n)(1+r(n))$ for all large enough n, where infinitesimal
function $r(n)$ is {\it the approximation error} of $g(n)$.

To estimate the measure of the number of graphs with a certain
property, the concept of {\it almost all} is often used; in this
approach, the studied property is considered for graphs with a large
number of vertices. Let ${\mathcal J}_n$ be the class of labeled
$n$-vertex graphs with the fixed set of vertices
$V=\{1,2,\ldots,n\}$, $n\in {\mathbb N}$. Consider some property
${\mathcal P}$, by which each graph may or may not possess. Through
${\mathcal J}^{\mathcal P}_n$ denote the set of all graphs from
${\mathcal J}_n$ that possess the property ${\mathcal P}$. {\it
Almost all graphs possess the property} ${\mathcal P}$ if
$\lim_{n\rightarrow \infty}\frac{|{\mathcal J}^{\mathcal
P}_n|}{|{\mathcal J}_n|}=1$, \/i.e.\/ $|{\mathcal J}^{\mathcal P}_n|
\sim |{\mathcal J}_n|$, and {\it there are almost no graphs with the
property} ${\mathcal P}$, if $\lim_{n\rightarrow
\infty}\frac{|{\mathcal J}^{\mathcal P}_n|}{|{\mathcal J}_n|}=0.$

In the study and selection of almost all graphs in the class of
graphs under consideration it is often useful to define not
characteristic properties themselves for the notion of almost all,
but directly select a subclass of typical graphs itself (in
\cite{fti15}, a more general concept of a class of typical
combinatorial objects for a given class of objects admitting  the
concept of dimension is formulated, further we will also use this
formal concept for graphs when the dimension of a graph is
understood as the number of its vertices). Let $\Omega $ be an
arbitrary class of graphs such that $\Omega_n\neq\varnothing$ for
all large enough $n$, where $\Omega_n=\Omega\,\cap\, {\mathcal
J}_n$. A subclass $\Omega^{\ast}\subseteq \Omega$ is {\it the class
of typical graphs of the class} $\Omega$ if $\lim_{n\rightarrow
\infty}\,|\Omega_n^{\ast}|/|\Omega_n|=1.$ A property of graphs of
the class under consideration is \/{\it typical}\/ if almost all
graphs of this class have this property.

Let ${\mathcal J}_{n,\,d=k}$, ${\mathcal J}_{n,\,d\geq k}$,
${\mathcal J}^{\ast}_{n,\,d\geq k}$ be the following classes of
labeled $n$-vertex graphs: graphs of diameter $k$; connected graphs
of diameter at least $k$; graphs (not necessarily connected) with
the shortest path of length at least $k$, respectively. In paper
\cite{fti17}, it is proved that for $k\geq 3$ all three classes of
graphs ${\mathcal J}_{n,\,d=k}$, ${\mathcal J}_{n,\,d\geq k}$,
${\mathcal J}^{\ast}_{n,\,d\geq k}$ have the same asymptotic
cardinality, and asymptotically exact value
$2^{\binom{n}{2}}\,\xi_{n,k}$ of the number of graphs in these
classes is found. Here
$$\xi_{n,k}=q_k\,\,(n)_{k-1}\,
\Bigr(\frac{3}{2^{k-1}}\Bigl)^{n-k+1},\,\,\,\,
q_k=\frac{1}{2}\,(k-2)\,2^{-\binom{k-1}{2}},
$$
$(n)_k=n(n-1)\cdots (n-k+1)$, $(n)_0=(0)_0=1$ and $(n)_k=0$ if
$n<k$.

In \cite{fti22-2}, when studying the variety of metric balls in
graphs, for every $\Delta$, $0<\Delta<1$, it is defined a constant
$\varepsilon_{\Delta}$, depending only on $\Delta$ and
$0<\varepsilon_{\Delta}<1$. Then a class ${\mathcal
F}_{n,k,\Delta}$, $k\geq 3$ (the detailed definition of this class
is given in Section 2) of typical graphs for the classes ${\mathcal
J}_{n,\,d=k}$, ${\mathcal J}_{n,\,d\geq k}$, ${\mathcal
J}_{n,\,d\geq k}^{\ast}$ is constructed.
\begin{theorem}[asymptotics of $|{\mathcal F}_{n,k,\Delta}|$ \cite{fti22-2}]\label{t1sn}
Let $k\geq 3$, $0<\Delta<1$,
$\varepsilon_{\Delta}<\varepsilon<\nobreak 1$, and $k$, $\Delta$,
$\varepsilon$ do not depend on $n$. Then there exists a constant
$c>0$ independent of $n$ such that for every $n\in {\mathbb N}$ the
following inequalities are valid
\begin{flushleft}
$ 2^{\binom{n}{2}}\xi_{n,k}\Bigr(1-c\Bigr(\frac
{5+\varepsilon}{6}\Bigl)^{n-k+1}\Bigl)\leq |{\mathcal
F}_{n,k,\Delta}|\leq |{\mathcal J}_{n,\,d=k}|$
\end{flushleft}
\begin{flushright}
$\leq |{\mathcal J}_{n,\,d\geq k}|\leq |{\mathcal J}_{n,\,d\geq
k}^{\ast}|\leq 2^{\binom{n}{2}}\xi_{n,k}\Bigr(1+c\Bigr(\frac
{5+\varepsilon}{6}\Bigl)^{n-k+1}\Bigl).$
\end{flushright}
\end{theorem}

Note that for $k=3$ the upper bound in Theorem \ref{t1sn} takes the
form $2^{\binom{n}{2}}\xi_{n,3}$ \cite{fti15}. Moreover, this upper
estimate is valid even for a class of graphs containing additionally
all disconnected graphs (which do not necessarily have a connected
component with shortest path of length $3$). Class ${\mathcal
F}_{n,3,\Delta}$ is the union of the subclasses ${\mathcal
F}_{n,3,\Delta}(x,y)$ over all different $x,y\in V$, and $x,y$ is
the unique pair of diametral vertices of every graph from ${\mathcal
F}_{n,3,\Delta}(x,y)$. Further we use the following estimate of the
number of graphs in class ${\mathcal F}_{n,3,\Delta}(x,y)$ obtained
in \cite{fti22-2}.
\begin{lemma}[lower bound \cite{fti22-2}]\label{l1h}
Let $x,y$ be different vertices in $V$, $\Delta$ is arbitrary
constant independent of $n$, and $0<\Delta<1$. Then the following
inequality holds as $n$ tends to infinity $|{\mathcal
F}_{n,3,\Delta}(x,y) \geq a_n (1- r(n)),$ where $r(n)$ is a positive
infinitesimal function and $a_n=2^{\binom{n}{2}}\,\frac{8}{9}
\,\Bigl(\frac{3}{4}\Bigr)^n$.
\end{lemma}



\section{Class of graphs ${\mathcal H}_{n,k,\Delta}$}
\hspace*{\parindent} For every integer $k\geq 3$ and $\Delta$,
$0<\Delta<1$, the class ${\mathcal F}_{n,k,\Delta}$ of typical
graphs of class ${\mathcal J}_{n,\,d=k}$ was constructed by author
in \cite{fti22-2}. In this section we define a subclass ${\mathcal
H}_{n,k,\Delta}$ of class ${\mathcal F}_{n,k,\Delta}$. To define
this class, first consider the following properties of $n$-vertex
graphs $F$ of diameter $3$ with vertex set $V$ and fixed vertexes
$x,y\in V$.

a) Non-Pendant condition: vertexes $x,y$ are not pendant in $F$;

b) Existence of a {\it pole}: $\rho_F(z,x)=\rho_F(z,y)=2$ for some
vertex $z\in V$;

c) Property of diametral vertices: $d(F)=3$ and graph $F$ has the
unique pair of diametral vertices $x,y$;

d) Nonexistence of a {\it shuttlecocks}: graph $F$ does not contain
shuttlecocks (subgraphs defined in \cite{fti95}) or, equivalently,
does not contain coinciding balls of radius $1$ with centers at
different vertices;

e) Property of spheres intersections:
$$|S_1^F(u)\cap S_1^F(v)|\geq \Bigl\lfloor\frac{n}{6}
\Delta\Bigr\rfloor+1 \;\; \forall u,v\in V\setminus
\{x,y\} \mbox{ and } u\neq v,$$
$$|S_1^F(u)\cap S_1^F(z)|\geq \Bigl\lfloor\frac{n}{6}
\Delta\Bigr\rfloor+1 \;\; \forall u\in V\setminus
\{x,y\}\;\; \forall z\in \{x,y\};$$

f) Property of cardinality of independence sets: $\alpha(F) <
\lfloor 2 \log_2 n\rfloor$.

In \cite{fti22-2}, ${\mathcal F}_{n,3,\Delta}(x,y)$ was defined for
$x,y\in V$ as the class of all graphs $F\in {\mathcal J}_{n}$ with
the properties a), b), c), d), e). Let ${\mathcal
H}_{n,3,\Delta}(x,y)$ be the class of all graphs in ${\mathcal
F}_{n,3,\Delta}(x,y)$ possessing property f) additionally. Now, for
$k\geq 3$, we define a class ${\mathcal H}_{n,k,\Delta}$ as follows.
Let $u=(u_0,u_1,\ldots,u_{k-2})$ be an arbitrary ordered sequence of
different vertices from the set $V$. Fix an arbitrary pair of
neighboring elements $u_s$ and $u_{s+1}$. On the set $V\setminus
\{u_0,\ldots,u_{s-1},u_{s+2},\ldots,u_{k-2}\}$ of $n-k+3$ vertices,
define an arbitrary graph $F$ from the class ${\mathcal
H}_{n-k+3,3,\Delta}(u_s,u_{s+1})$. Finally, join by edges the
vertices $u_i,u_{i+1}$ for $i\neq s$ and $0\leq i<k-2.$ Denote the
so-obtained graph by $G(u,s,F)$. Let ${\mathcal H}_{n,k,\Delta}$ be
the class of all graphs $G(u,s,F)$ constructed under condition
$0\leq s\leq \lfloor \frac{k-3}{2} \rfloor$. Note that if, in
defining the graphs $G(u,s,F)$, instead of class of graphs
${\mathcal H}_{n-k+3,3,\Delta}(u_s,u_{s+1})$, we use ${\mathcal
F}_{n-k+3,3,\Delta}(u_s,u_{s+1})$, then we arrive at the definition
of class ${\mathcal F}_{n,k,\Delta}$ \cite{fti22-2}. Hence, we have
\begin{eqnarray}\label{f2w}
{\mathcal H}_{n,3,\Delta}(x,y)\subseteq {\mathcal
F}_{n,3,\Delta}(x,y), \,\, {\mathcal H}_{n,3,\Delta}\subseteq
{\mathcal F}_{n,3,\Delta}.
\end{eqnarray}
Therefore, all properties of graphs $G(u,s,F)$ obtained earlier in
\cite{fti17,fti22-2} will also hold for graphs of class ${\mathcal
H}_{n,k,\Delta}$ or can be proven in a similar way. In particular,
the properties stated in Lemmas \ref{l4a} and \ref{l5a} are valid.
%(see, respectively, Lemmas 5 and 7 in \rm\cite{fti16}).
\begin{lemma}[properties of graphs $G(u,s,F)$]\label{l4a}
Let $k\geq 3$, $0 <\Delta <1$ and $G=G(u,s,F)\in {\mathcal
H}_{n,k,\Delta}.$ Then the following properties hold:

{\rm (i)} $G\in {\mathcal J}_{n,d=k};$

{\rm (ii)} $u_s,u_{s+1}$ are not pendant vertices in $F$;

{\rm (iii)} $u_0,u_{k-2}$ is the unique pair of diametral vertices
of graph $G$ and every its diametral path contains vertices
$u_0,u_1,\ldots,u_{k-2}$.
\end{lemma}
\noindent Using Lemma \ref{l4a}, as in \cite{fti17, fti22-2} one can
express the number of graphs of class ${\mathcal H}_{n,k,\Delta}$
through the number  of graphs of class ${\mathcal
H}_{n,3,\Delta}(x,y)$.
\begin{lemma}[number of graphs in ${\mathcal H}_{n,k,\Delta}$]\label{l5a}
Let $k\geq 3$, $0<\Delta<1$. Then
$$|{\mathcal H}_{n,k,\Delta}|=\frac{1}{2}(k-2)(n)_{k-1} |{\mathcal
H}_{n-k+3,3,\Delta}(x,y)|,\mbox{ where }x\neq y.$$
\end{lemma}

Estimate the number of graphs in ${\mathcal H}_{n,3,\Delta}(x,y)$.
For this we need the following classes of graphs and estimates of
the number of such graphs obtained in Lemma \ref{40l} below. Let
$x,y$ be different elements of $V$, $\alpha=\lfloor 2 \log_2
n\rfloor$,
$${\mathcal S}_n(x,y)=\{G\in {\mathcal J}_n \,|\, B_1^G(x)\cap
B_1^G(y)=\varnothing \mbox{ and } \alpha(F) \geq \lfloor 2 \log_2
n\rfloor \},$$ and ${\mathcal S}_{n}(x,y;x)$, ${\mathcal
S}_{n}(x,y;x,y)$, ${\mathcal S}_{n}(x,y;\varnothing)$ be the classes
of $n$-vertex graphs $G\in {\mathcal J}_n$ such that $B_1^G(x)\cap
B_1^G(y)=\varnothing$, there is an independent $\alpha$-element set
$S$ and the following inclusions hold: $x\in S$, $y\notin S$; $x\in
S$, $y\in S$; $x\notin S$, $y\notin S$, respectively. It is obvious
that the following inclusions of the sets hold
\begin{equation}\label{199}
{\mathcal S}_n(x,y)\subseteq {\mathcal S}_{n}(x,y;\varnothing) \cup
{\mathcal S}_{n}(x,y;x) \cup {\mathcal S}_{n}(x,y;y) \cup {\mathcal
S}_{n}(x,y;x,y).
\end{equation}
\begin{lemma}\label{20l}
Let $\lambda>0$, $\lambda$ does not depend on $n$ and
$\alpha=\lfloor 2\log_2n\rfloor$. Then the following equality is
fulfilled as $n$ tends to infinity $$\binom{n}{\alpha}
2^{-\binom{\alpha}{2}}=\frac{1}{\lambda^{\alpha}\sqrt{\alpha}}O(1).
$$
\end{lemma}
\begin{proof}
Using Stirling's formula, we obtain
\begin{equation}\label{20}
\binom{n}{\alpha}=\frac{n^{\alpha}}{\alpha!}O(1)=
\Bigl(\frac{ne}{\alpha}\Bigr)^{\alpha}\frac{1}{\sqrt{\alpha}}O(1).
\end{equation}
Using the inequality $\lfloor x\rfloor\geq x-1$, we obtain
\begin{equation}\label{21}
2^{-\binom{\alpha}{2}}=2^{-\alpha(\log_2n-1)}O(1)=\Bigl(\frac{2}{n}
\Bigr) ^{\alpha}O(1).\\[-5pt]
\end{equation}
From (\ref{20}),(\ref{21}) we conclude
$$\binom{n}{\alpha}
2^{-\binom{\alpha}{2}}=\Bigl(\frac{2e}{\alpha}\Bigr)^{\alpha}
\frac{1}{\sqrt{\alpha}}O(1)= \Bigl(\frac{1}{\lambda}\Bigr)
^{\alpha}\frac{1}{\sqrt{\alpha}}O(1).
$$
\end{proof}
\begin{lemma}\label{40l}
Let $x,y$ be different vertices of $V$, $q>1$, $q$ does not depend
on $n$, and $\alpha=\lfloor 2\log_2n\rfloor$. Then the following
equality is fulfilled as $n$ tends to infinity \\[-5pt]

{\rm (i)} ${\mathcal S}_{n}(x,y;x)= a_n
(\frac{1}{q})^{\alpha}\frac{1}{\sqrt \alpha} O(1);$\\[-5pt]

{\rm (ii)} ${\mathcal S}_{n}(x,y;x,y)= a_n
(\frac{1}{q})^{\alpha}\frac{1}{\sqrt \alpha} O(1);$\\[-5pt]

{\rm (iii)} ${\mathcal S}_{n}(x,y;\varnothing)= a_n
(\frac{1}{q})^{\alpha}\frac{1}{\sqrt \alpha} O(1);$
\end{lemma}
\begin{proof}
{\rm (i)} From the definition of class ${\mathcal S}_{n}(x,y;x)$, it
is easy to understand that all graphs of this class are contained
among graphs $G$ constructed as follows:

1) choose an $(\alpha -1)$-element subset $S\subseteq V\setminus
\{u,v\}$, there are $\binom{n-2}{\alpha -1}$ possibilities. In graph
$G$, the vertices of set $S\cup \{x\}$ will remain pairwise
non-adjacent, resulting in $S\cup \{x\}$  being an $\alpha$-element
independent set;

2) choose an $i$-element subset $V_x\subseteq V\setminus (S\cup
\{x,y\})$, $0\leq i\leq n-1-\alpha$, and join each vertex from $V_x$
by an edge with $x$, as a result we have $S_1^G(x)=V_x$;

3) choose a $j$-element subset of $V_y\subseteq V\setminus (V_x\cup
\{x,y\})$, $0\leq j\leq n-2-i$ and join each vertex from $V_y$ by an
edge with $y$, as a result we obtain $S_1^G(y)=V_y$ and $V_x\cap
V_y=\varnothing$;

4) on $(n-2)$-element set $V\setminus\{x,y\}$ define an arbitrary
graph in which there are no $\binom{\alpha-1}{2}$ edges between the
vertices of the set $S$.

Thus, using the Newton's Binomial Theorem, the binomial identity
(\ref{f1h}), Lemma \ref{20l} and the inequality $\alpha \leq
\lfloor\frac{n}{2}\rfloor$, valid for all large enough $n$, we
obtain as $n\rightarrow \infty$
\begin{eqnarray*}
|{\mathcal S}_{n}(x,y;x)| \hspace{-3mm}&=&\hspace{-4mm}
\binom{n-2}{\alpha -1}\hspace{-1mm}
\sum\limits_{i=0}^{n-1-\alpha}\hspace{-1mm}\binom{n-1-\alpha}{i}\hspace{-1mm}\sum\limits_{j=0}
^{n-2-i}\hspace{-1mm}\binom{n-2-i}{j} 2^{\binom{n-2}{2}-\binom{\alpha-1}{2}}O(1)\\
\hspace{-3mm}&=&
2^{\binom{n-2}{2}}\binom{n}{\alpha}2^{-\binom{\alpha}{2}+\alpha}\sum\limits_{i=0}^{n-1-\alpha}
\binom{n-1-\alpha}{i} 2^{n-2-i}O(1)\\
\hspace{-3mm}&=&2^{\binom{n}{2}}\Bigl(\frac{1}{4}\Bigr)^n
\,4^\alpha\binom{n}{\alpha}
2^{-\binom{\alpha}{2}}\sum\limits_{i=0}^{n-1-\alpha}
\binom{n-1-\alpha}{i} 2^{n-1-\alpha-i}O(1)\\
\hspace{-3mm}&=&2^{\binom{n}{2}}\Bigl(\frac{3}{4}\Bigr)^n
\,\Bigl(\frac{4}{3}\Bigr)^\alpha \binom{n}{\alpha}
2^{-\binom{\alpha}{2}}O(1)\\
\hspace{-3mm}&=&a_n \Bigl(\frac{1}{q}\Bigr)^{\alpha}\frac{1}{\sqrt
\alpha} O(1).
\end{eqnarray*}

{\rm (ii)} Similarly to the proof of the statement (i), we construct
graphs forming a superclass of the class ${\mathcal S}_{n}(x,y;x,y)$
and obtain the following estimates
\begin{eqnarray*}
|{\mathcal S}_{n}(x,y;x,y)| \hspace{-2mm}&=&
\hspace{-3mm}\binom{n-2}{\alpha -2}
\sum\limits_{i=0}^{n-\alpha}\binom{n-\alpha}{i}\sum\limits_{j=0}
^{n-\alpha-i}\binom{n-\alpha-i}{j} 2^{\binom{n-2}{2}-\binom{\alpha-2}{2}}O(1)\\
\hspace{-2mm}&=&
2^{\binom{n-2}{2}}3^{n-\alpha}\binom{n}{\alpha}2^{-\binom{\alpha
-2}{2}}O(1)\\
\hspace{-2mm}&=&2^{\binom{n}{2}}\Bigl(\frac{3}{4}\Bigr)^n
\,\Bigl(\frac{4}{3}\Bigr)^\alpha \binom{n}{\alpha}
2^{-\binom{\alpha}{2}}O(1)\\
\hspace{-2mm}&=&a_n \Bigl(\frac{1}{q}\Bigr)^{\alpha}\frac{1}{\sqrt
\alpha} O(1).
\end{eqnarray*}

{\rm (iii)} The estimate of the number of graphs of class ${\mathcal
S}_{n}(x,y;\varnothing)$ is proved similarly:
\begin{eqnarray*}
|{\mathcal S}_{n}(x,y;\varnothing)| &=& \binom{n-2}{\alpha}
\sum\limits_{i=0}^{n-2}\binom{n-2}{i}\sum\limits_{j=0}
^{n-2-i}\binom{n-2-i}{j} 2^{\binom{n-2}{2}-\binom{\alpha}{2}}O(1)\\
&=&2^{\binom{n}{2}}\Bigl(\frac{3}{4}\Bigr)^n \,\binom{n}{\alpha}
2^{-\binom{\alpha}{2}}O(1)= a_n
\Bigl(\frac{1}{q}\Bigr)^{\alpha}\frac{1}{\sqrt \alpha} O(1).
\end{eqnarray*}
\end{proof}
\begin{lemma}\label{l33l}
Let $x,y$ be different vertices in $V$, $0<\Delta<1$ and $\Delta$ is
arbitrary constant independent of $n$. Then $|{\mathcal
H}_{n,3,\Delta}(x,y) \geq a_n (1- r(n))$ as $n$ tends to infinity,
where $r(n)$ is a positive infinitesimal function.
\end{lemma}
\begin{proof}
Directly from the class definitions we obtain
$${\mathcal F}_{n,3,\Delta}(x,y)\setminus {\mathcal
S}_n(x,y)\subseteq {\mathcal H}_{n,3,\Delta}(x,y).$$ Hence,
$|{\mathcal H}_{n,3,\Delta}(x,y)| \geq |{\mathcal
F}_{n,3,\Delta}(x,y)|-|{\mathcal S}_n(x,y)|.$ It remains to apply
Lemmas \ref{l1h}, \ref{40l} and relation (\ref{199}).
\end{proof}
\begin{lemma}[lower bound]\label{l6a}
Let $k\geq 3$ and $0<\Delta <1$ are constants independent of $n$.
Then the following inequality holds as $n$ tends to infinity
$$|{\mathcal H}_{n,k,\Delta}|\geq 2^{\binom{n}{2}}\xi_{n,k}(1-r(n)),$$
where $r(n)$ is a positive infinitesimal function.
\end{lemma}
\begin{proof}
Using Lemmas \ref{l5a} and \ref{l33l}, the definitions of numbers
$a_n$ and $\xi_{n,k}$, and the binomial identity (\ref{f1h}), we
conclude
\begin{eqnarray*}
|{\mathcal H}_{n,k,\Delta}| & \geq & \frac{1}{2}\,(k-2)(n)_{k-1}
\,2^{\binom{n-k+3}{2}}\,\frac{8}{9}\,\Bigl(\frac{3}{4}\Bigr)^{n-k+3}
\,(1-r(n))\\
& = &
2^{\binom{n}{2}}\,q_k(n)_{k-1}\,2^{-(n-k+1)(k-3)}\Bigr(\frac{3}{4}\Bigl)^{n-k+1}
\,(1-r(n))\\
& = & 2^{\binom{n}{2}}\,\xi_{n,k}\,(1-r(n)).
\end{eqnarray*}
\end{proof}
\noindent The following theorem follows directly from Lemma
\ref{l6a}, relation (\ref{f2w}) and Theorem \ref{t1sn}.
\begin{theorem}[asymptotics of $|{\mathcal H}_{n,k,\Delta}|$]\label{t1b}
Let $k\geq 3$, $0<\Delta <1$ and $k$, $\Delta$ do not depend on $n$.
Then the following inequalities hold as $n$ tends to infinity
$$2^{\binom{n}{2}}\xi_{n,k}(1-r_1(n))\leq |{\mathcal
H}_{n,k,\Delta}|\leq|{\mathcal F}_{n,k,\Delta}|\leq|{\mathcal
J}_{n,\,d=k}|\leq 2^{\binom{n}{2}}\xi_{n,k}(1+r_2(n)).$$ Here
$r_1(n)$, $r_2(n)$ are positive infinitesimal functions.
\end{theorem}
\begin{corollary}\label{s1b}
Let $k\geq 3$ and $0<\Delta <1$ be independent of $\,n$. Then
${\mathcal H}_{n,k,\Delta}$ is the class of typical graphs of the
class of $n$-vertex graphs of diameter $k$ and the following
asymptotic equalities hold as $n\rightarrow \infty$
$$
|{\mathcal H}_{n,k,\Delta}|\sim |{\mathcal F}_{n,k,\Delta}|\sim
|{\mathcal J}_{n,\,d=k}|\sim 2^{\binom{n}{2}}\xi_{n,k}.
$$
\end{corollary}



\section{Hamiltonian property of almost all graphs of diameter $k$}
\hspace*{\parindent} Note that $K_n$ is the unique $n$-vertex graph
of diameter $k=1$. For $n\geq 3$ its Hamiltonian cycle is
constructed by graph vertex traversal and $K_2$ is nonhamiltonian.
Therefore, almost all graphs of diameter $k=1$ are Hamiltonian. A
similar fact for graphs of diameter $2$ also trivially follows from
well-known theorems.
\begin{lemma}\label{t1x}
Almost all graphs of diameter $2$ are Hamiltonian.
\end{lemma}
\begin{proof}
Through ${\mathcal K}^H$ denote the set of all Hamiltonian graphs
from class ${\mathcal K}$. It is well known that almost all graphs
are Hamiltonian \cite{perepel} and almost all graphs have diameter
$2$ \cite{moon66}. Thus,
$$|{\mathcal J}_n^H|\sim |{\mathcal J}_n|\sim |{\mathcal
J}_{n,\,d=2}|.$$
Hence, as $n\rightarrow\infty$ we infer
$$\frac{|{\mathcal J}_{n,\,d=2}^H|}{|{\mathcal J}_{n,\,d=2}|}
=1-\frac{|{\mathcal J}_{n,\,d=2}|-|{\mathcal
J}_{n,\,d=2}^H|}{|{\mathcal J}_{n,\,d=2}|} \geq \,\,1-
\frac{|{\mathcal J}_n|-|{\mathcal J}_n^H|}{|{\mathcal
J}_n|}\,\,\frac{|{\mathcal J}_n|}{|{\mathcal J}_{n,\,d=2}|}
\longrightarrow\,1.$$
\end{proof}

Now for $k=3$, let us investigate Hamiltonian property for graphs in
the classes of typical graphs ${\mathcal F}_{n,k,\Delta}$ and
${\mathcal H}_{n,k,\Delta}$. Obviously, $2$-connectivity is a
necessary condition for a graph to be Hamiltonian. Note that not
every graph of class ${\mathcal F}_{n,3,\Delta}$ is $2$-connected.
Indeed, using graph properties a), b) and c), it is easy to see that
${\mathcal F}_{n,3,\Delta}=\varnothing $ if $n<7$. Let us consider
graph $F_n^1$ shown in Fig. \ref{fig1}. Given the equality
$|S_1^{F_n^1}(x)\cap S_1^{F_n^1}(x_1)|=1$, it is not difficult
\begin{center}
\begin{figure}[h]
\vspace{-1.5cm}
\includegraphics[scale=1.8]{1-2024} %scale - это коэффициент маштабирования
\vspace{-1.7cm} \caption{Graph $F_n^1$}\label{fig1} \vspace{-5mm}
\end{figure}
\end{center}
to understand that $F_n^1\in {\mathcal F}_{n,3,\Delta}$ if and only
if $7\leq n < 6/\Delta.$ At the same time, for all admissible values
of $n$ and $\Delta$, $F_n^1\in {\mathcal F}_{n,3,\Delta}$ and graph
$F_n^1$ is not $2$-connected, since there are no two vertex-disjoint
pathes connecting its diametral vertices $x$ and $y$.
\begin{lemma}\label{l7x}
For $n\geq 6/\Delta$ and $0<\Delta <1$, all graphs in class
${\mathcal F}_{n,3,\Delta}$ are 2-connected.
\end{lemma}
\begin{proof}
Let $G\in {\mathcal F}_{n,3,\Delta}$ and $n\geq 6/\Delta$. Then
$|S_1^G(u)\cap S_1^G(v)|\geq 2$ if $\{u,v\}\neq\{x,y\}$ due to the
property of spheres intersections. By Whitney's Theorem (see, for
example, \cite{xar69}), it sufficient to connect every two vertices
$u$, $v$ by two vertex-disjoint pathes.

Let $P(x,x_1,y_1,y)$ is a diametral path of graph $G$. If $u,v$ are
not a pair of diametral vertices then there are exist different
vertices $w_1,w_2\in S_1^G(u)\cap S_1^G(v)$. Hence, $P(u,w_i,v),$
$i=1,2,$ are two vertex-disjoint pathes. Therefore, we further
assume that $\{u,v\}=\{x,y\}$. Vertex $x$ is not pendant. Hence,
there is exist a vertex $x_2\in V\setminus \{x_1\}$ adjacent to $x$.
Note that $x_2\not\in\{ x,x_1,y_1,y \}$, otherwise $\rho_G(x,y)\leq
2$. Further, there is exist a vertex $y_2\in (S_1^G(x_2)\cap
S_1^G(y))\setminus\{y_1\}$. Similarly, we have $y_2\not\in\{ x,x_2,
x_1,y_1,y \}$. Thus, $P(x,x_1,y_1,y)$, $P(x,x_2,y_2,y)$ are required
two vertex-disjoint pathes.
\end{proof}

Note that not every $2$-connected graph in class ${\mathcal
F}_{n,3,\Delta}$ is Hamiltonian. Indeed, using the properties of
graphs of class ${\mathcal F}_{n,3,\Delta}$, it is easy to prove
that ${\mathcal F}_{n,3,\Delta}=\varnothing$ if $6/\Delta \leq n<9$
(see also \cite{fti21-1}, page 350). Let us consider graph $F_n^2$
shown in Fig. \ref{fig2} for $n\geq 9$. Obviously, $F_n^2$ is a
$2$-connected graph. Moreover,
\begin{center}
\begin{figure}[h]
\vspace{-1.3cm}
\includegraphics[scale=1.4]{2-2024} %scale - это коэффициент маштабирования
\vspace{-1.7cm} \caption{Graph $F_n^2$}\label{fig2} \vspace{-7mm}
\end{figure}
\end{center}
$|S_1^{F_n^2}(x)\cap S_1^{F_n^2}(x_2)|=2$. Now, it is not difficult
to prove that $F_n^2\in {\mathcal F}_{n,3,\Delta}$ if and only if
$9\leq n < 12/\Delta.$ Note that graph $F_n^2$ is Hamiltonian for
$n=9,10,11$ (as example, the Hamiltonian cycle of graph $F_{11}^2$
is shown in Fig. \ref{fig3})
\begin{center}
\begin{figure}[hb]
\vspace{-1cm}
\includegraphics[scale=1.4]{3-2024} %scale - это коэффициент маштабирования
\vspace{-1.7cm} \caption{Hamiltonian cycle of graph $F_{11}^2 \in
{\mathcal F}_{11,3,\Delta}$}\label{fig3} \vspace{-7mm}
\end{figure}
\end{center}
and it is nonHamiltonian if $n=12$. Besides, in all these cases
$F_n^2\in {\mathcal F}_{n,3,\Delta}$ for any $\Delta$, $0<\Delta
<1$. In addition, $F_n^2\in {\mathcal F}_{n,3,\Delta}$ and $F_n^2$
is nonHamiltonian, for example, if $n=13,14,\ldots,18$ and $\Delta <
12/n$. The verification of the Hamiltonian property for the above
graphs was performed on a computer, you can also use the online
service \cite{online} or similar.

Now we will show that all graphs of class ${\mathcal
F}_{n,3,\Delta}$ have sufficiently high connectivity.
\begin{lemma}\label{30nn}
Let $\Delta$ does not depend on $n$ and $0<\Delta<1$. Then all
graphs in class ${\mathcal F}_{n,3,\Delta}$ are
$\varkappa$-connected, where $\varkappa=\lfloor
n\,\Delta/18\rfloor$.
\end{lemma}
\begin{proof}
Without loss of generality, we assume $\varkappa\geq 1$. Let $G\in
{\mathcal F}_{n,3,\Delta}$ and $x,y$ is the unique pair of diametral
vertices of graph $G$. By Whitney's Theorem, it is sufficient to
connect every two vertices $u,v$ by $\varkappa$ vertex-disjoint
pathes.

Let $\rho_G(u,v)<3.$ Then $|S_1^G(u)\cap S_1^G(v)|\geq \frac{n}{6}
\Delta>\varkappa$ by the property of sphere intersections. So
further we assume $\{u,v\}=\{x,y\}$. Using the property of sphere
intersections we obtain the following relations
\begin{eqnarray}\label{30}
&\nonumber B_1^G(x)\cap B_1^G(y)=\varnothing,&\\
&|S_1^G(x)|\geq \frac{n}{6}\Delta,\, |S_1^G(y)|\geq
\frac{n}{6}\Delta,&\\
&\nonumber |S_1^G(x')\cap S_1^G(y')|\geq \frac{n}{6}\Delta, \mbox{
if } x'\in S_1^G(x) \mbox{ and } y'\in S_1^G(y).&
\end{eqnarray}
We will construct step by step a sequence of pairwise disjoint
$3$-element sets $V_i=\{x_i, y_i, z_i\}$ such that
$P_i(x,x_i,y_i,y)$ is a simple path of graph $G$.

Step 1. Consider arbitrary vertices $x_1\in S_1^G(x)$ and $y_1\in
S_1^G(y)$. By virtue of (\ref{30}) there is a vertex $z_1\in
S_1^G(x_1)\cap S_1^G(y_1)$. Using (\ref{30}) and property c) for
graph $G$, it is also easy to see that graph $G$ contains a simple
path $P_1(x,x_1,z_1,y_1,y)$. We define $V_1=\{x_1,y_1,z_1\}$.

Step $i+1$. Let the sets $V_1,\ldots,V_i$ be constructed and
$i<\varkappa$. Then \\[-12pt]
\begin{eqnarray}\label{31}
|\bigcup\limits_{s=1}^i V_s|=3i<3\varkappa\leq \frac{n}{6}\Delta.
\end{eqnarray}
By virtue of (\ref{30}) and (\ref{31}) the following vertices exist:
$$x_{i+1}\in S_1^G(x)\setminus \cup_{s=1}^iV_s,$$
$$y_{i+1}\in S_1^G(y)\setminus \cup_{s=1}^iV_s,$$
$$z_{i+1}\in S_1^G(x_{i+1})\cap S_1^G(y_{i+1})\setminus \cup_{s=1}^iV_s.$$
We define $V_{i+1}=\{x_{i+1},y_{i+1},z_{i+1}\}$. Using property c)
for graph $G$, we obtain $P_{i+1}(x,x_{i+1},z_{i+1},y_{i+1},y)$ is a
simple path of graph $G$.

Thus, at step $\varkappa$, the vertex-disjoint simple paths $P_i,
i=1,\ldots,\varkappa$ with endpoints $x,y$ will be constructed.
\end{proof}

Let us turn to graphs of class ${\mathcal H}_{n,k,\Delta}$. We apply
the following sufficient condition of V.Chv$\acute{a}$tal and
P.Erd$\ddot{o}$s for a graph to be Hamiltonian.
\begin{theorem}[V.Chv$\acute{a}$tal and P.Erd$\ddot{o}s$ \cite{erdos}]\label{erd}
Let $G$ be a graph
with at least three vertices. If for some $s$, graph $G$ is
$s$-connected and $\alpha(G)\leq s$, then $G$ has a Hamiltonian
cycle.
\end{theorem}
\begin{lemma}\label{l1x}
Let $k\geq 3$. Then all graphs of class ${\mathcal
H}_{n,k=3,\Delta}$ are Hamiltonian for all large enough $n$ and
every graph in ${\mathcal H}_{n,k,\Delta}$ is nonHamiltonian if
$k\geq 4$.
\end{lemma}
\begin{proof}
There is an integer $N>0$ such that for all $n \geq N$ the following
inequality holds $\lfloor 2 \log_2 n\rfloor - 1 \leq \lfloor
n\,\Delta/18\rfloor$. Let $n\geq N$, $G\in {\mathcal
H}_{n,3,\Delta}$ and $s=\lfloor 2 \log_2 n\rfloor - 1$. By the
property of cardinality of independence sets, $\alpha(G)\leq s$. In
addition, $G$ is $s$-connected due to (\ref{f2w}) and Lemma
\ref{30nn}. Therefore, graph $G$ is Hamiltonian by Theorem
\ref{erd}.

It remains to note that for $k\geq 4$ every graph in class
${\mathcal H}_{n,k,\Delta}$ contains a pendant vertex due to the
definition of graph $G(u,s,F)$.
\end{proof}

Lemma \ref{t1x}, Corollary \ref{s1b} and Lemma \ref{l1x} imply the
following theorem.
\begin{theorem}\label{t2x}
Almost all $n$-vertex graphs of fixed diameter $k=1,2,3$ are
Hamiltonian, while almost all $n$-vertex graph of fixed diameter
$k\geq 4$ are nonHamiltonian graphs.
\end{theorem}

By Theorem \ref{t1sn}, for $k\geq 3$ all three classes of graphs
${\mathcal J}_{n,\,d=k}$, ${\mathcal J}_{n,\,d\geq k}$, ${\mathcal
J}^{\ast}_{n,\,d\geq k}$ have the same asymptotic cardinality.
Therefore, we obtain the following corollary.
\begin{corollary}\label{s6x}
For every fixed $k=1,2,3$, almost all $n$-vertex graphs of each of
the following classes ${\mathcal J}_{n,\,d\geq k},\,{\mathcal
J}_{n,\,d\geq k}^{\ast}$ are Hamiltonian, while almost all
$n$-vertex graphs of these classes are nonHamiltonian for every
fixed $k\geq 4$.
\end{corollary}


\section{Conclusion}
\hspace*{\parindent} Note that the existence of a Hamiltonian cycle
in Theorem \ref{erd} is based on Dirac's generalization of Theorem
of Menger on $s$-connected graphs. This requires considering a large
variety of paths to construct $s$ vertex-disjoint paths starting at
a given vertex $x$ and terminating in a given cycle $C$ if $x\notin
V(C)$. This makes this method of constructing a Hamiltonian cycle
algorithmically complex. In this connection, a fairly effective
method for constructing a Hamiltonian cycle for almost all
$n$-vertex graphs of diameter $3$ is of further interest.

\bigskip
\begin{thebibliography}{18} % Ссылки на литературу приводятся только
%на английском языке (даже если у источника нет англоязычной версии).
\bibitem{erdos}
V.~Chv$\acute{a}$tal, P.~Erd$\ddot{o}$s,
\href{https://doi.org/10.1016/0012-365X(72)90079-9}{\it A note on
Hamiltonian circutis}, Discrete Mathematics, {\bf 2} (1972), pp.
111--113.
\bibitem{emel90}
V.A.~Emelichev, O.I.~Melnikov, V.I.~Sarvanov, and R.I.~Tyshkevich,
{\it Lectures on Graph Theory}, B.I.Wissenschaftsverlag, Mannheim,
1994. Zbl 0865.05001
\bibitem{fti95}
T.I.~Fedoryaeva,
\href{https://doi.org/10.1007/978-94-011-5678-3\_5}{\it Operations
and isometric embeddings of graphs related to the metric
prolongation property}, Oper. Research and Discrete Anal., {\bf 2}:3
(1997), 31--49, translated from Diskretn. Anal. Issled. Oper., {\bf
2}:3 (1995), 49--67. Zbl 0860.05032
\bibitem{fti15}
T.I.~Fedoryaeva,
\href{https://doi.org/10.17377/daio.2015.22.512}{\it The diversity
vector of balls of a typical graph of small diameter}, Diskretn.
Anal. Issled. Oper., {\bf 22}:6 (2015), 43--54. Zbl 1349.05085
\bibitem{fti17}
T.I.~Fedoryaeva,
\href{https://doi.org/10.1134/S1990478917020065}{\it Asymptotic
approximation for the number of n-vertex graphs of given diameter},
J.Appl.Ind.Math., {\bf 11}:2 (2017), 204--214, translated from
Diskretn. Anal. Issled. Oper., {\bf 24}:2 (2017), 68--86. Zbl
1399.05108
\bibitem{fti21-1}
T.I.~Fedoryaeva,
\href{https://doi.org/10.33048/semi.2021.18.024}{\it On radius and
typical properties of $n$-vertex graphs of given diameter}, Siber.
Electr. Math. Reports, {\bf 18} (2021), 345--357. Zbl 1458.05053
\bibitem{fti22-2}
T.I.~Fedoryaeva,
\href{https://doi.org/10.33048/semi.2022.19.062}{\it Logarithmic
asymptotics of the number of central vertices of almost all
$n$-vertex graphs of diameter $k$}, Siber. Electr. Math. Reports,
{\bf 19}:2 (2022), 747--761. Zbl 7948696
\bibitem{fti22-3}
T.I.~Fedoryaeva,
\href{https://doi.org/10.20948/dms-2022-3}{\it
Typical metric properties of $n$-vertex graphs of given diameter},
Discrete mathematics and its applications, XIV International
Scientific Seminar named after Academician O.B. Lupanov, 21--33
(2022)
\bibitem{obzor1991}
Ronald J.~Gould, \href{https://doi.org/10.1002/jgt.3190150204}{\it
Updating the Hamiltonian Problem --- A Survey}, Journal of Graph
Theory, Vol. {\bf 15}, No. 2, 121-157 (1991)
\bibitem{grah94}
Ronald~L.~Graham, Donald~E.~Knuth, and Oren Patashnik, {\it Concrete
Mathematics}, Addison-Wesley, 1994. Zbl 0836.00001
\bibitem{online}
{\it Graph online}, https://graphonline.ru
\bibitem{xar69}
F.~Harary, {\it Graph Theory}, Addison--Wesley, London, 1969. Zbl
0182.57702
\bibitem{jixt}
M.~Jixiang, H.~Qiongxiang,
\href{https://doi.org/10.1007/BF02108156}{\it Almost all Cayley
graphs are hamiltonian}, Acta Mathematica Sinica, {\bf 12} (1996),
pp. 151--–155. Zbl 0858.05068
\bibitem{ush}
V.P.~Kozyrev, S.V.~Yushmanov,
\href{https://doi.org/10.1007/BF01086177}{\it Graph Theory
(algorithmic, algebraic, and metric problems)}, Itogi Nauki i
Tekhniki. Ser. Teor. Veroyatn., Mat. Stat., Teor. Kibern., {\bf 23},
VINITI, Moscow, 1985, 68–117.  Zbl 0606.05057; J. Soviet Math., {\bf
39}:1 (1987), 2476–2508. Zbl 0627.05043
\bibitem{moon72}
J.W.~Moon,
\href{https://doi.org/10.4153/CMB-1972-008-3}{\it Almost
all graphs have spanning cycle}, Canad. Math. Bull., Vol. 15 {\bf 1}
(1972), 39--41. Zbl 0229.05128
\bibitem{moon66}
J.W.~Moon, L.~Moser,
{\it Almost all {\rm (0,1)} matrices are
primitive}, Stud. Sci. Math. Hung., {\bf 1} (1966), 153--156. Zbl
0142.27102
\bibitem{perepel}
Yu.D.~Perepeliza,
{\it New sufficient conditions for cycles in
graphs}, Dokl. Akad. Nauk SSSR, {\bf 194:6} (1970), pp. 1269--–1272.
\bibitem{robin}
R.W.~Robinson, N.C.~Wormald,
\href{https://doi.org/10.1002/rsa.3240050209}{\it Almost all regular
graphs are hamiltonian}, Random Struct. Alg., {\bf 5} (1994), pp.
363--–374. Zbl 0795.05088
\end{thebibliography}
\end{document}
