اشترك بالحزمة الذهبية واحصل على وصول غير محدود شمرا أكاديميا
تسجيل مستخدم جديدOn the least size of a graph with a given degree set -- II
174
0
0.0
(
0
)
اسأل ChatGPT حول البحث
ﻻ يوجد ملخص باللغة العربية
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 considered 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$.
قيم البحث
اقرأ أيضاً
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 $F$-decomposition threshold $delta_F$ for a given graph $F$. Here an $F$-decomposition of a graph $G$ is a collection of edge-disjoint copies of $F$ in $G$ which together cover every edge of $G$. (Such an $F$-decomposition can only exist
if $G$ is $F$-divisible, i.e. if $e(F)mid e(G)$ and each vertex degree of $G$ can be expressed as a linear combination of the vertex degrees of $F$.) The $F$-decomposition threshold $delta_F$ is the smallest value ensuring that an $F$-divisible graph $G$ on $n$ vertices with $delta(G)ge(delta_F+o(1))n$ has an $F$-decomposition. Our main results imply the following for a given graph $F$, where $delta_F^ast$ is the fractional version of $delta_F$ and $chi:=chi(F)$: (i) $delta_Fle max{delta_F^ast,1-1/(chi+1)}$; (ii) if $chige 5$, then $delta_Fin{delta_F^{ast},1-1/chi,1-1/(chi+1)}$; (iii) we determine $delta_F$ if $F$ is bipartite. In particular, (i) implies that $delta_{K_r}=delta^ast_{K_r}$. Our proof involves further developments of the recent `iterative absorbing approach.
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
A signed graph is a pair $(G,Sigma)$, where $G=(V,E)$ is a graph (in which parallel edges and loops are permitted) with $V={1,ldots,n}$ and $Sigmasubseteq E$. The edges in $Sigma$ are called odd edges and the other edges of $E$ even. By $S(G,Sigma)$
we denote the set of all symmetric $ntimes n$ real matrices $A=[a_{i,j}]$ such that if $a_{i,j} < 0$, then there must be an even edge connecting $i$ and $j$; if $a_{i,j} > 0$, then there must be an odd edge connecting $i$ and $j$; and if $a_{i,j} = 0$, then either there must be an odd edge and an even edge connecting $i$ and $j$, or there are no edges connecting $i$ and $j$. (Here we allow $i=j$.) For a symmetric real matrix $A$, the partial inertia of $A$ is the pair $(p,q)$, where $p$ and $q$ are the number of positive and negative eigenvalues of $A$, respectively. If $(G,Sigma)$ is a signed graph, we define the emph{inertia set} of $(G,Sigma)$ as the set of the partial inertias of all matrices $A in S(G,Sigma)$. In this paper, we present a formula that allows us to obtain the minimal elements of the inertia set of $(G,Sigma)$ in case $(G,Sigma)$ has a $1$-separation using the inertia sets of certain signed graphs associated to the $1$-separation.
Let $G$ be a simple graph with $ngeq4$ vertices and $d(x)+d(y)geq n+k$ for each edge $xyin E(G)$. In this work we prove that $G$ either contains a spanning closed trail containing any given edge set $X$ if $|X|leq k$, or $G$ is a well characterized g
raph. As a corollary, we show that line graphs of such graphs are $k$-hamiltonian.
سجل دخول لتتمكن من نشر تعليقات
التعليقات
جاري جلب التعليقات
سجل دخول لتتمكن من متابعة معايير البحث التي قمت باختيارها
