Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userDensity of 4-edge paths in graphs with fixed edge density
152
0
0.0
(
0
)
Authors
Daniel T. Nagy
Ask ChatGPT about the research
No Arabic abstract
We investigate the number of 4-edge paths in graphs with a fixed number of vertices and edges. An asymptotically sharp upper bound is given to this quantity. The extremal construction is the quasi-star or the quasi-clique graph, depending on the edge density. An easy lower bound is also proved. This answer resembles the classic theorem of Ahlswede and Katona about the maximal number of 2-edge paths, and a recent theorem of Kenyon, Radin, Ren and Sadun about k-edge stars.
rate research
Read More
An edge-ordering of a graph $G=(V,E)$ is a bijection $phi:Eto{1,2,...,|E|}$. Given an edge-ordering, a sequence of edges $P=e_1,e_2,...,e_k$ is an increasing path if it is a path in $G$ which satisfies $phi(e_i)<phi(e_j)$ for all $i<j$. For a graph $G$, let $f(G)$ be the largest integer $ell$ such that every edge-ordering of $G$ contains an increasing path of length $ell$. The parameter $f(G)$ was first studied for $G=K_n$ and has subsequently been studied for other families of graphs. This paper gives bounds on $f$ for the hypercube and the random graph $G(n,p)$.
Kostochka and Yancey resolved a famous conjecture of Ore on the asymptotic density of $k$-critical graphs by proving that every $k$-critical graph $G$ satisfies $|E(G)| geq (frac{k}{2} - frac{1}{k-1})|V(G)| - frac{k(k-3)}{2(k-1)}$. The class of graphs for which this bound is tight, $k$-Ore graphs, contain a notably large number of $K_{k-2}$-subgraphs. Subsequent work attempted to determine the asymptotic density for $k$-critical graphs that do emph{not} contain large cliques as subgraphs, but only partial progress has been made on this problem. The second author showed that if $G$ is 5-critical and has no $K_3$-subgraphs, then for $varepsilon = 1/84$, $|E(G)| geq (frac{9}{4} + varepsilon)|V(G)| - frac{5}{4}$. It has also been shown that for all $k geq 33$, there exists $varepsilon_k > 0$ such that $k$-critical graphs with no $K_{k-2}$-subgraphs satisfy $|E(G)| geq (frac{k}{2} - frac{1}{k-1} + varepsilon_k)|V(G)| - frac{k(k-3)}{2(k-1)}$. In this work, we develop general structural results that are applicable to resolving the remaining difficult cases $6 leq k leq 32$. We apply our results to carefully analyze the structure of 6-critical graphs and use a discharging argument to show that for $varepsilon_6 = 1/1050$, 6-critical graphs with no $K_4$ subgraph satisfy $|E(G)| geq ( frac{k}{2} - frac{1}{k-1} + varepsilon_6 ) |V(G)| - frac{k(k-3)}{2(k-1)}$.
A strong edge-coloring of a graph $G$ is an edge-coloring such that any two edges on a path of length three receive distinct colors. We denote the strong chromatic index by $chi_{s}(G)$ which is the minimum number of colors that allow a strong edge-coloring of $G$. ErdH{o}s and Nev{s}etv{r}il conjectured in 1985 that the upper bound of $chi_{s}(G)$ is $frac{5}{4}Delta^{2}$ when $Delta$ is even and $frac{1}{4}(5Delta^{2}-2Delta +1)$ when $Delta$ is odd, where $Delta$ is the maximum degree of $G$. The conjecture is proved right when $Deltaleq3$. The best known upper bound for $Delta=4$ is 22 due to Cranston previously. In this paper we extend the result of Cranston to list strong edge-coloring, that is to say, we prove that when $Delta=4$ the upper bound of list strong chromatic index is 22.
A graph is edge-primitive if its automorphism group acts primitively on the edge set, and 2-arc-transitive if its automorphism group acts transitively on the set of 2-arcs. In this paper, we present a classification for those edge-primitive graphs which are 2-arc-transitive and have soluble edge-stabilizers.
A graph $G(V,E)$ of order $|V|=p$ and size $|E|=q$ is called super edge-graceful if there is a bijection $f$ from $E$ to ${0,pm 1,pm 2,...,pm frac{q-1}{2}}$ when $q$ is odd and from $E$ to ${pm 1,pm 2,...,pm frac{q}{2}}$ when $q$ is even such that the induced vertex labeling $f^*$ defined by $f^*(x) = sum_{xyin E(G)}f(xy)$ over all edges $xy$ is a bijection from $V$ to ${0,pm 1,pm 2...,pm frac{p-1}{2}}$ when $p$ is odd and from $V$ to ${pm 1,pm 2,...,pm frac{p}{2}}$ when $p$ is even. indent We prove that all paths $P_n$ except $P_2$ and $P_4$ are super edge-graceful.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
