Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userSuper edge-graceful paths
218
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
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.
rate research
Read More
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.
In 2006, Barat and Thomassen posed the following conjecture: for each tree $T$, there exists a natural number $k_T$ such that, if $G$ is a $k_T$-edge-connected graph and $|E(G)|$ is divisible by $|E(T)|$, then $G$ admits a decomposition into copies of $T$. This conjecture was verified for stars, some bistars, paths of length $3$, $5$, and $2^r$ for every positive integer $r$. We prove that this conjecture holds for paths of any fixed length.
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)$.
Given an integer $1leq j <n$, define the $(j)$-coloring of a $n$-dimensional hypercube $H_{n}$ to be the $2$-coloring of the edges of $H_{n}$ in which all edges in dimension $i$, $1leq i leq j$, have color $1$ and all other edges have color $2$. Cheng et al. [Proper distance in edge-colored hypercubes, Applied Mathematics and Computation 313 (2017) 384-391.] determined the number of distinct shortest properly colored paths between a pair of vertices for the $(1)$-colored hypercubes. It is natural to consider the number for $(j)$-coloring, $jgeq 2$. In this note, we determine the number of different shortest proper paths in $(j)$-colored hypercubes for arbitrary $j$.
An edge-ordered graph is a graph with a total ordering of its edges. A path $P=v_1v_2ldots v_k$ in an edge-ordered graph is called increasing if $(v_iv_{i+1}) > (v_{i+1}v_{i+2})$ for all $i = 1,ldots,k-2$; it is called decreasing if $(v_iv_{i+1}) < (v_{i+1}v_{i+2})$ for all $i = 1,ldots,k-2$. We say that $P$ is monotone if it is increasing or decreasing. A rooted tree $T$ in an edge-ordered graph is called monotone if either every path from the root of to a leaf is increasing or every path from the root to a leaf is decreasing. Let $G$ be a graph. In a straight-line drawing $D$ of $G$, its vertices are drawn as different points in the plane and its edges are straight line segments. Let $overline{alpha}(G)$ be the maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing path of length $overline{alpha}(G)$. Let $overline{tau}(G)$ be the maximum integer such that every edge-ordered straight-line drawing of $G$ %under any edge labeling contains a monotone non-crossing complete binary tree of size $overline{tau}(G)$. In this paper we show that $overline alpha(K_n) = Omega(loglog n)$, $overline alpha(K_n) = O(log n)$, $overline tau(K_n) = Omega(loglog log n)$ and $overline tau(K_n) = O(sqrt{n log n})$.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
