Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userCycles of given lengths in unicyclic components in sparse random graphs
202
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $L$ be subset of ${3,4,dots}$ and let $X_{n,M}^{(L)}$ be the number of cycles belonging to unicyclic components whose length is in $L$ in the random graph $G(n,M)$. We find the limiting distribution of $X_{n,M}^{(L)}$ in the subcritical regime $M=cn$ with $c<1/2$ and the critical regime $M=frac{n}{2}left(1+mu n^{-1/3}right)$ with $mu=O(1)$. Depending on the regime and a condition involving the series $sum_{l in L} frac{z^l}{2l}$, we obtain in the limit either a Poisson or a normal distribution as $ntoinfty$.
rate research
Read More
Sombor index is a novel topological index introduced by Gutman, defined as $SO(G)=sumlimits_{uvin E(G)}sqrt{d_{u}^{2}+d_{v}^{2}}$, where $d_{u}$ denotes the degree of vertex $u$. Recently, Chen et al. [H. Chen, W. Li, J. Wang, Extremal values on the Sombor index of trees, MATCH Commun. Math. Comput. Chem. 87 (2022), in press] considered the Sombor indices of trees with given diameter. For the continue, we determine the maximum Sombor indices for unicyclic graphs with given diameter.
We prove that the number of Hamilton cycles in the random graph G(n,p) is n!p^n(1+o(1))^n a.a.s., provided that pgeq (ln n+ln ln n+omega(1))/n. Furthermore, we prove the hitting-time version of this statement, showing that in the random graph process, the edge that creates a graph of minimum degree 2 creates (ln n/e)^n(1+o(1))^n Hamilton cycles a.a.s.
Gutman and Wagner proposed the concept of matching energy (ME) and pointed out that the chemical applications of ME go back to the 1970s. Let $G$ be a simple graph of order $n$ and $mu_1,mu_2,ldots,mu_n$ be the roots of its matching polynomial. The matching energy of $G$ is defined to be the sum of the absolute values of $mu_{i} (i=1,2,ldots,n)$. In this paper, we characterize the graphs with minimal matching energy among all unicyclic and bicyclic graphs with a given diameter $d$.
Given an $n$ vertex graph whose edges have colored from one of $r$ colors $C={c_1,c_2,ldots,c_r}$, we define the Hamilton cycle color profile $hcp(G)$ to be the set of vectors $(m_1,m_2,ldots,m_r)in [0,n]^r$ such that there exists a Hamilton cycle that is the concatenation of $r$ paths $P_1,P_2,ldots,P_r$, where $P_i$ contains $m_i$ edges. We study $hcp(G_{n,p})$ when the edges are randomly colored. We discuss the profile close to the threshold for the existence of a Hamilton cycle and the threshold for when $hcp(G_{n,p})={(m_1,m_2,ldots,m_r)in [0,n]^r:m_1+m_2+cdots+m_r=n}$.
We show that, in almost every $n$-vertex random directed graph process, a copy of every possible $n$-vertex oriented cycle will appear strictly before a directed Hamilton cycle does, except of course for the directed cycle itself. Furthermore, given an arbitrary $n$-vertex oriented cycle, we determine the sharp threshold for its appearance in the binomial random directed graph. These results confirm, in a strong form, a conjecture of Ferber and Long.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
