Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userTransitive tournament tilings in oriented graphs with large minimum total degree
158
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
Let $vec{T}_k$ be the transitive tournament on $k$ vertices. We show that every oriented graph on $n=4m$ vertices with minimum total degree $(11/12+o(1))n$ can be partitioned into vertex disjoint $vec{T}_4$s, and this bound is asymptotically tight. We also improve the best known bound on the minimum total degree for partitioning oriented graphs into vertex disjoint $vec{T}_k$s.
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 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$.
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.
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.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
