Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userThe overfullness of graphs with small minimum degree and large maximum degree
148
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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$.
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.
Given a digraph $D$ with $m $ arcs, a bijection $tau: A(D)rightarrow {1, 2, ldots, m}$ is an antimagic labeling of $D$ if no two vertices in $D$ have the same vertex-sum, where the vertex-sum of a vertex $u $ in $D$ under $tau$ is the sum of labels of all arcs entering $u$ minus the sum of labels of all arcs leaving $u$. We say $(D, tau)$ is an antimagic orientation of a graph $G$ if $D$ is an orientation of $G$ and $tau$ is an antimagic labeling of $D$. Motivated by the conjecture of Hartsfield and Ringel from 1990 on antimagic labelings of graphs, Hefetz, M{u}tze, and Schwartz in 2010 initiated the study of antimagic orientations of graphs, and conjectured that every connected graph admits an antimagic orientation. This conjecture seems hard, and few related results are known. However, it has been verified to be true for regular graphs and biregular bipartite graphs. In this paper, we prove that every connected graph $G$ on $nge9$ vertices with maximum degree at least $n-5$ admits an antimagic orientation.
This paper presents sufficient conditions for Hamiltonian paths and cycles in graphs. Letting $lambdaleft( Gright) $ denote the spectral radius of the adjacency matrix of a graph $G,$ the main results of the paper are: (1) Let $kgeq1,$ $ngeq k^{3}/2+k+4,$ and let $G$ be a graph of order $n$, with minimum degree $deltaleft( Gright) geq k.$ If [ lambdaleft( Gright) geq n-k-1, ] then $G$ has a Hamiltonian cycle, unless $G=K_{1}vee(K_{n-k-1}+K_{k})$ or $G=K_{k}vee(K_{n-2k}+overline{K}_{k})$. (2) Let $kgeq1,$ $ngeq k^{3}/2+k^{2}/2+k+5,$ and let $G$ be a graph of order $n$, with minimum degree $deltaleft( Gright) geq k.$ If [ lambdaleft( Gright) geq n-k-2, ] then $G$ has a Hamiltonian path, unless $G=K_{k}vee(K_{n-2k-1}+overline {K}_{k+1})$ or $G=K_{n-k-1}+K_{k+1}$ In addition, it is shown that in the above statements, the bounds on $n$ are tight within an additive term not exceeding $2$.
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.
A {em strong $k$-edge-coloring} of a graph $G$ is a mapping from $E(G)$ to ${1,2,ldots,k}$ such that every two adjacent edges or two edges adjacent to the same edge receive distinct colors. The {em strong chromatic index} $chi_s(G)$ of a graph $G$ is the smallest integer $k$ such that $G$ admits a strong $k$-edge-coloring. We give bounds on $chi_s(G)$ in terms of the maximum degree $Delta(G)$ of a graph $G$. when $G$ is sparse, namely, when $G$ is $2$-degenerate or when the maximum average degree ${rm Mad}(G)$ is small. We prove that the strong chromatic index of each $2$-degenerate graph $G$ is at most $5Delta(G) +1$. Furthermore, we show that for a graph $G$, if ${rm Mad}(G)< 8/3$ and $Delta(G)geq 9$, then $chi_s(G)leq 3Delta(G) -3$ (the bound $3Delta(G) -3$ is sharp) and if ${rm Mad}(G)<3$ and $Delta(G)geq 7$, then $chi_s(G)leq 3Delta(G)$ (the restriction ${rm Mad}(G)<3$ is sharp).
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
