Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userEdge-decompositions of graphs with high minimum degree
250
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
A fundamental theorem of Wilson states that, for every graph $F$, every sufficiently large $F$-divisible clique has an $F$-decomposition. Here a graph $G$ is $F$-divisible if $e(F)$ divides $e(G)$ and the greatest common divisor of the degrees of $F$ divides the greatest common divisor of the degrees of $G$, and $G$ has an $F$-decomposition if the edges of $G$ can be covered by edge-disjoint copies of $F$. We extend this result to graphs $G$ which are allowed to be far from complete. In particular, together with a result of Dross, our results imply that every sufficiently large $K_3$-divisible graph of minimum degree at least $9n/10+o(n)$ has a $K_3$-decomposition. This significantly improves previous results towards the long-standing conjecture of Nash-Williams that every sufficiently large $K_3$-divisible graph with minimum degree at least $3n/4$ has a $K_3$-decomposition. We also obtain the asymptotically correct minimum degree thresholds of $2n/3 +o(n)$ for the existence of a $C_4$-decomposition, and of $n/2+o(n)$ for the existence of a $C_{2ell}$-decomposition, where $ellge 3$. Our main contribution is a general `iterative absorption method which turns an approximate or fractional decomposition into an exact one. In particular, our results imply that in order to prove an asymptotic version of Nash-Williams conjecture, it suffices to show that every $K_3$-divisible graph with minimum degree at least $3n/4+o(n)$ has an approximate $K_3$-decomposition,
rate research
Read More
Let $G$ be a simple graph with maximum degree $Delta(G)$. A subgraph $H$ of $G$ is overfull if $|E(H)|>Delta(G)lfloor |V(H)|/2 rfloor$. Chetwynd and Hilton in 1985 conjectured that a graph $G$ with $Delta(G)>|V(G)|/3$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph. The 1-factorization conjecture is a special case of this overfull conjecture, which states that for even $n$, every regular $n$-vertex graph with degree at least about $n/2$ has a 1-factorization and was confirmed for large graphs in 2014. Supporting the overfull conjecture as well as generalizing the 1-factorization conjecture in an asymptotic way, in this paper, we show that for any given $0<varepsilon <1$, there exists a positive integer $n_0$ such that the following statement holds: if $G$ is a graph on $2nge n_0$ vertices with minimum degree at least $(1+varepsilon)n$, then $G$ has chromatic index $Delta(G)$ if and only if $G$ contains no overfull subgraph.
The degree-based entropy of a graph is defined as the Shannon entropy based on the information functional that associates the vertices of the graph with the corresponding degrees. In this paper, we study extremal problems of finding the graphs attaining the minimum degree-based graph entropy among graphs and bipartite graphs with a given number of vertices and edges. We characterize the unique extremal graph achieving the minimum value among graphs with a given number of vertices and edges and present a lower bound for the degree-based entropy of bipartite graphs and characterize all the extremal graphs which achieve the lower bound. This implies the known result due to Cao et al. (2014) that the star attains the minimum value of the degree-based entropy among trees with a given number of vertices.
We consider numbers and sizes of independent sets in graphs with minimum degree at least $d$, when the number $n$ of vertices is large. In particular we investigate which of these graphs yield the maximum numbers of independent sets of different sizes, and which yield the largest random independent sets. We establish a strengthened form of a conjecture of Galvin concerning the first of these topics.
Given a simple graph $G$, denote by $Delta(G)$, $delta(G)$, and $chi(G)$ the maximum degree, the minimum degree, and the chromatic index of $G$, respectively. We say $G$ is emph{$Delta$-critical} if $chi(G)=Delta(G)+1$ and $chi(H)le Delta(G)$ for every proper subgraph $H$ of $G$; and $G$ is emph{overfull} if $|E(G)|>Delta lfloor |V(G)|/2 rfloor$. Since a maximum matching in $G$ can have size at most $lfloor |V(G)|/2 rfloor$, it follows that $chi(G) = Delta(G) +1$ if $G$ is overfull. Conversely, let $G$ be a $Delta$-critical graph. The well known overfull conjecture of Chetwynd and Hilton asserts that $G$ is overfull provided $Delta(G) > |V(G)|/3$. In this paper, we show that any $Delta$-critical graph $G$ is overfull if $Delta(G) - 7delta(G)/4ge(3|V(G)|-17)/4$.
The weight of a subgraph $H$ in $G$ is the sum of the degrees in $G$ of vertices of $H$. The {em height} of a subgraph $H$ in $G$ is the maximum degree of vertices of $H$ in $G$. A star in a given graph is minor if its center has degree at most five in the given graph. Lebesgue (1940) gave an approximate description of minor $5$-stars in the class of normal plane maps with minimum degree five. In this paper, we give two descriptions of minor $5$-stars in plane graphs with minimum degree five. By these descriptions, we can extend several results and give some new results on the weight and height for some special plane graphs with minimum degree five.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
