اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe size of graphs with restricted rainbow $2$-connection number
176
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Let $k$ be a positive integer, and $G$ be a $k$-connected graph. An edge-coloured path is emph{rainbow} if all of its edges have distinct colours. The emph{rainbow $k$-connection number} of $G$, denoted by $rc_k(G)$, is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by $k$ internally vertex-disjoint rainbow paths. The function $rc_k(G)$ was introduced by Chartrand, Johns, McKeon and Zhang in 2009, and has since attracted significant interest. Let $t_k(n,r)$ denote the minimum number of edges in a $k$-connected graph $G$ on $n$ vertices with $rc_k(G)le r$. Let $s_k(n,r)$ denote the maximum number of edges in a $k$-connected graph $G$ on $n$ vertices with $rc_k(G)ge r$. The functions $t_1(n,r)$ and $s_1(n,r)$ have previously been studied by various authors. In this paper, we study the functions $t_2(n,r)$ and $s_2(n,r)$. We determine bounds for $t_2(n,r)$ which imply that $t_2(n,2)=(1+o(1))nlog_2 n$, and $t_2(n,r)$ is linear in $n$ for $rge 3$. We also provide some remarks about the function $s_2(n,r)$.
قيم البحث
اقرأ أيضاً
Let $G$ be a finite group, the enhanced power graph of $G$, denoted by $Gamma_G^e$, is the graph with vertex set $G$ and two vertices $x,y$ are edge connected in $Gamma_{G}^e$ if there exist $zin G$ such that $x,yinlangle zrangle$. Let $zeta$ be a ed
ge-coloring of $Gamma_G^e$. In this article, we calculate the rainbow connection number of the enhanced power graph $Gamma_G^e$.
An edge-coloured graph $G$ is called $properly$ $connected$ if every two vertices are connected by a proper path. The $proper$ $connection$ $number$ of a connected graph $G$, denoted by $pc(G)$, is the smallest number of colours that are needed in or
der to make $G$ properly connected. Susan A. van Aardt et al. gave a sufficient condition for the proper connection number to be at most $k$ in terms of the size of graphs. In this note, %optimizes the boundary of the number of edges %we study the $proper$ $connection$ $number$ is under the conditions of adding the minimum degree and optimizing the number of edges. our main result is the following, by adding a minimum degree condition: Let $G$ be a connected graph of order $n$, $kgeq3$. If $|E(G)|geq binom{n-m-(k+1-m)(delta+1)}{2} +(k+1-m)binom{delta+1}{2}+k+2$, then $pc(G)leq k$, where $m$ takes the value $t$ if $delta=1$ and $lfloor frac{k}{delta-1} rfloor$ if $deltageq2$. Furthermore, if $k=2$ and $delta=2$, %(i.e., $|E(G)|geq binom{n-5}{2} +7$) $pc(G)leq 2$, except $Gin {G_{1}, G_{n}}$ ($ngeq8$), where $G_{1}=K_{1}vee 3K_{2}$ and $G_{n}$ is obtained by taking a complete graph $K_{n-5}$ and $K_{1}vee (2K_{2}$) with an arbitrary vertex of $K_{n-5}$ and a vertex with $d(v)=4$ in $K_{1}vee (2K_{2}$) being joined. If $k=2$, $delta geq 3$, we conjecture $pc(G)leq 2$, where $m$ takes the value $1$ if $delta=3$ and $0$ if $deltageq4$ in the assumption.
An edge-cut $R$ of an edge-colored connected graph is called a rainbow-cut if no two edges in the edge-cut are colored the same. An edge-colored graph is rainbow disconnected if for any two distinct vertices $u$ and $v$ of the graph, there exists a $
u$-$v$-rainbow-cut separating them. For a connected graph $G$, the rainbow disconnection number of $G$, denoted by rd$(G)$, is defined as the smallest number of colors that are needed in order to make $G$ rainbow disconnected. In this paper, we first give some tight upper bounds for rd$(G)$, and moreover, we completely characterize the graphs which meet the upper bound of the Nordhaus-Gaddum type results obtained early by us. Secondly, we propose a conjecture that $lambda^+(G)leq textnormal{rd}(G)leq lambda^+(G)+1$, where $lambda^+(G)$ is the upper edge-connectivity, and prove the conjecture for many classes of graphs, to support it. Finally, we give the relationship between rd$(G)$ of a graph $G$ and the rainbow vertex-disconnection number rvd$(L(G))$ of the line graph $L(G)$ of $G$.
An edge-coloured path is emph{rainbow} if all the edges have distinct colours. For a connected graph $G$, the emph{rainbow connection number} $rc(G)$ is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connect
ed by a rainbow path. Similarly, the emph{strong rainbow connection number} $src(G)$ is the minimum number of colours in an edge-colouring of $G$ such that, any two vertices are connected by a rainbow geodesic (i.e., a path of shortest length). These two concepts of connectivity in graphs were introduced by Chartrand et al.~in 2008. Subsequently, vertex-colour
The size-Ramsey number of a graph $F$ is the smallest number of edges in a graph $G$ with the Ramsey property for $F$, that is, with the property that any 2-colouring of the edges of $G$ contains a monochromatic copy of $F$. We prove that the size-Ra
msey number of the grid graph on $ntimes n$ vertices is bounded from above by $n^{3+o(1)}$.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
