Two vertices u and v in a nontrivial connected graph G are twins if u and v have the same neighbors in V (G) − {u, v}. If u and v are adjacent, they are referred to as true twins; while if u and v are nonadjacent, they are false twins. For a positive integer k, let c : V (G) → Zk be a vertex coloring where adjacent vertices may be assigned the same color. The coloring c induces another vertex coloring c′ : V (G) → Zk defined by c′(v) = P u∈N[v] c(u) for each v ∈ V (G), where N[v] is the closed neighborhood...

A double-star is a tree with exactly two vertices of degree greater than 1. If T is a double-star where the two vertices of degree greater than one have degrees k1+1 and k2+1, then T is denoted by Sk1,k2 . In this note, we show that every double-star with n edges decomposes every 2n-regular graph. We also show that the double-star Sk,k−1 decomposes every 2k-regular graph that contains a perfect matching.

Discrete partially ordered sets can be turned into distance spaces in several ways. The distance functions may or may not satisfy the triangle inequality and restrictions of the distance to finite chains may or may not coincide with the natural, difference-of-height distance measured in a chain. It is shown that for semilattices the semimodularity ensures the good behaviour of the distances considered. The Jordan-Dedekind chain condition, which is weaker than semimodularity, is equivalent to the...

In 1986, Chartrand, Saba and Zou [3] defined a measure of the distance between (the isomorphism classes of) two graphs based on 'edge rotations'. Here, that measure and two related measures are explored. Various bounds, exact values for classes of graphs and relationships are proved, and the three measures are shown to be intimately linked to 'slowly-changing' parameters.

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...