ﻻ يوجد ملخص باللغة العربية
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.
Let $G$ be a graph and $tau$ be an assignment of nonnegative integer thresholds to the vertices of $G$. A subset of vertices $D$ is said to be a $tau$-dynamic monopoly, if $V(G)$ can be partitioned into subsets $D_0, D_1, ldots, D_k$ such that $D_0=D
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
An edge-colored connected graph $G$ is properly connected if between every pair of distinct vertices, there exists a path that no two adjacent edges have a same color. Fujita (2019) introduced the optimal proper connection number ${mathrm{pc}_{mathrm
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$
We introduce a graph decomposition which exists for all simple, connected graphs $G=(V,E)$. The decomposition $V = A cup B cup C$ is such that each vertex in $A$ has more neighbors in $B$ than in $A$ and vice versa. $C$ is `balanced: each $v in C$ ha