اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدThe maximum size of a nonhamiltonian graph with given order and connectivity
168
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
Motivated by work of ErdH{o}s, Ota determined the maximum size $g(n,k)$ of a $k$-connected nonhamiltonian graph of order $n$ in 1995. But for some pairs $n,k,$ the maximum size is not attained by a graph of connectivity $k.$ For example, $g(15,3)=77$ is attained by a unique graph of connectivity $7,$ not $3.$ In this paper we obtain more precise information by determining the maximum size of a nonhamiltonian graph of order $n$ and connectivity $k,$ and determining the extremal graphs. Consequently we solve the corresponding problem for nontraceable graphs.
قيم البحث
اقرأ أيضاً
We study the maximum number $ex(n,e,H)$ of copies of a graph $H$ in graphs with given number of vertices and edges. We show that for any fixed graph $H$, $ex(n,e,H)$ is asymptotically realized by the quasi-clique provided that the edge density is suf
ficiently large. We also investigate a variant of this problem, when the host graph is bipartite.
ErdH{o}s determined the maximum size of a nonhamiltonian graph of order $n$ and minimum degree at least $k$ in 1962. Recently, Ning and Peng generalized. ErdH{o}s work and gave the maximum size $h(n,c,k)$ of graphs with prescribed order $n$, circumfe
rence $c$ and minimum degree at least $k.$ But for some triples $n,c,k,$ the maximum size is not attained by a graph of minimum degree $k.$ For example, $h(15,14,3)=77$ is attained by a unique graph of minimum degree $7,$ not $3.$ In this paper we obtain more precise information by determining the maximum size of a graph with prescribed order, circumference and minimum degree. Consequently we solve the corresponding problem for longest paths. All these results on the size of graphs have cliq
The rank of a graph is defined to be the rank of its adjacency matrix. A graph is called reduced if it has no isolated vertices and no two vertices with the same set of neighbors. We determine the maximum order of reduced triangle-free graphs with a
given rank and characterize all such graphs achieving the maximum order.
The degree set of a finite simple graph $G$ is the set of distinct degrees of vertices of $G$. A theorem of Kapoor, Polimeni & Wall asserts that the least order of a graph with a given degree set $mathscr D$ is $1+max mathscr D$. Tripathi & Vijay con
sidered the analogous problem concerning the least size of graphs with degree set $mathscr D$. We expand on their results, and determine the least size of graphs with degree set $mathscr D$ when (i) $min mathscr D mid d$ for each $d in mathscr D$; (ii) $min mathscr D=2$; (iii) $mathscr D={m,m+1,ldots,n}$. In addition, given any $mathscr D$, we produce a graph $G$ whose size is within $min mathscr D$ of the optimal size, giving a $big(1+frac{2}{d_1+1})$-approximation, where $d_1=max mathscr D$.
Let k_r(n,m) denote the minimum number of r-cliques in graphs with n vertices and m edges. For r=3,4 we give a lower bound on k_r(n,m) that approximates k_r(n,m) with an error smaller than n^r/(n^2-2m). The solution is based on a constraint minimizat
ion of certain multilinear forms. In our proof, a combinatorial strategy is coupled with extensive analytical arguments.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
