اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدAn upper bound on the Wiener Index of a k-connected graph
128
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
The Wiener index of a connected graph is the summation of all distances between unordered pairs of vertices of the graph. In this paper, we give an upper bound on the Wiener index of a $k$-connected graph $G$ of order $n$ for integers $n-1>k ge 1$: [W(G) le frac{1}{4} n lfloor frac{n+k-2}{k} rfloor (2n+k-2-klfloor frac{n+k-2}{k} rfloor).] Moreover, we show that this upper bound is sharp when $k ge 2$ is even, and can be obtained by the Wiener index of Harary graph $H_{k,n}$.
قيم البحث
اقرأ أيضاً
An adjacent vertex distinguishing coloring of a graph G is a proper edge coloring of G such that any pair of adjacent vertices are incident with distinct sets of colors. The minimum number of colors needed for an adjacent vertex distinguishing colori
ng of G is denoted by $chi_a(G)$. In this paper, we prove that $chi_a(G)$ <= 5($Delta+2$)/2 for any graph G having maximum degree $Delta$ and no isolated edges. This improves a result in [S. Akbari, H. Bidkhori, N. Nosrati, r-Strong edge colorings of graphs, Discrete Math. 306 (2006), 3005-3010], which states that $chi_a(G)$ <= 3$Delta$ for any graph G without isolated edges.
Let $r(k)$ denote the maximum number of edges in a $k$-uniform intersecting family with covering number $k$. ErdH{o}s and Lovasz proved that $ lfloor k! (e-1) rfloor leq r(k) leq k^k.$ Frankl, Ota, and Tokushige improved the lower bound to $r(k) geq
left( k/2 right)^{k-1}$, and Tuza improved the upper bound to $r(k) leq (1-e^{-1}+o(1))k^k$. We establish that $ r(k) leq (1 + o(1)) k^{k-1}$.
The Wiener index of a graph $G$, denoted $W(G)$, is the sum of the distances between all pairs of vertices in $G$. E. Czabarka, et al. conjectured that for an $n$-vertex, $ngeq 4$, simple quadrangulation graph $G$, begin{equation*}W(G)leq begin{cas
es} frac{1}{12}n^3+frac{7}{6}n-2, &text{ $nequiv 0~(mod 2)$,} frac{1}{12}n^3+frac{11}{12}n-1, &text{ $nequiv 1~(mod 2)$}. end{cases} end{equation*} In this paper, we confirm this conjecture.
Let $Sz(G),Sz^*(G)$ and $W(G)$ be the Szeged index, revised Szeged index and Wiener index of a graph $G.$ In this paper, the graphs with the fourth, fifth, sixth and seventh largest Wiener indices among all unicyclic graphs of order $ngeqslant 10$ ar
e characterized; as well the graphs with the first, second, third, and fourth largest Wiener indices among all bicyclic graphs are identified. Based on these results, further relation on the quotients between the (revised) Szeged index and the Wiener index are studied. Sharp lower bound on $Sz(G)/W(G)$ is determined for all connected graphs each of which contains at least one non-complete block. As well the connected graph with the second smallest value on $Sz^*(G)/W(G)$ is identified for $G$ containing at least one cycle.
A game starts with the empty graph on $n$ vertices, and two player alternate adding edges to the graph. Only moves which do not create a triangle are valid. The game ends when a maximal triangle-free graph is reached. The goal of one player is to end
the game as soon as possible, while the other player is trying to prolong the game. With optimal play, the length of the game (number of edges played) is called the $K_3$ game saturation number. In this paper we prove an upper bound for this number.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
