A graph $G$ is a locally $k$-tree graph if for any vertex $v$ the subgraph induced by the neighbours of $v$ is a $k$-tree, $k\ge 0$, where $0$-tree is an edgeless graph, $1$-tree is a tree. We characterize the minimum-size locally $k$-trees with $n$ vertices. The minimum-size connected locally $k$-trees are simply $(k+1)$-trees. For $k\ge 1$, we construct locally $k$-trees which are maximal with respect to the spanning subgraph relation. Consequently, the number of edges in an $n$-vertex locally $k$-tree graph is between $\Omega \left(n\right)$ and $O\left(n^2\right)$, where both...

A proper coloring $c:V\left(G\right)\to \{1,2,...,k\}$, $k\ge 2$ of a graph $G$ is called a graceful $k$-coloring if the induced edge coloring $c^{\text{'}}:E\left(G\right)\to \{1,2,...,k-1\}$ defined by $c^{\text{'}}\left(uv\right)=|c\left(u\right)-c\left(v\right)|$ for each edge $uv$ of $G$ is also proper. The minimum integer $k$ for which $G$ has a graceful $k$-coloring is the graceful chromatic number ${\chi }_g\left(G\right)$. It is known that if $T$ is a tree with maximum degree $\Delta$, then ${\chi }_g\left(T\right)\le \lceil \frac{5}{3}\Delta \rceil$ and this bound is best possible. It is shown for each integer $\Delta \ge 2$ that there is an infinite class of trees $T$ with maximum degree $\Delta$ such that ${\chi }_g\left(T\right)=\lceil \frac{5}{3}\Delta \rceil$. In particular, we investigate for each integer $\Delta \ge 2$ a...

The concept of the $k$-pairable graphs was introduced by Zhibo Chen (On $k$-pairable graphs, Discrete Mathematics 287 (2004), 11–15) as an extension of hypercubes and graphs with an antipodal isomorphism. In the same paper, Chen also introduced a new graph parameter $p\left(G\right)$, called the pair length of a graph $G$, as the maximum $k$ such that $G$ is $k$-pairable and $p\left(G\right)=0$ if $G$ is not $k$-pairable for any positive integer $k$. In this paper, we answer the two open questions raised by Chen in the case that the graphs involved...

The signed edge domination number of a graph is an edge variant of the signed domination number. The closed neighbourhood $N_G\left[e\right]$ of an edge $e$ in a graph $G$ is the set consisting of $e$ and of all edges having a common end vertex with $e$. Let $f$ be a mapping of the edge set $E\left(G\right)$ of $G$ into the set $\{-1,1\}$. If ${\sum }_{x\in N\left[e\right]}f\left(x\right)\ge 1$ for each $e\in E\left(G\right)$, then $f$ is called a signed edge dominating function on $G$. The minimum of the values ${\sum }_{x\in E\left(G\right)}f\left(x\right)$, taken over all signed edge dominating function $f$ on $G$, is called the signed edge domination number of $G$ and is...