A graph $G$ is a $k$-tree if either $G$ is the complete graph on $k+1$ vertices, or $G$ has a vertex $v$ whose neighborhood is a clique of order $k$ and the graph obtained by removing $v$ from $G$ is also a $k$-tree. Clearly, a $k$-tree has at least $k+1$ vertices, and $G$ is a 1-tree (usual tree) if and only if it is a $1$-connected graph and has no $K_3$-minor. In this paper, motivated by some properties of 2-trees, we obtain a characterization of $k$-trees as follows: if $G$ is a graph with at least $k+1$ vertices, then $G$ is...

Let $T$ be a tree. Then a vertex of $T$ with degree one is a leaf of $T$ and a vertex of degree at least three is a branch vertex of $T$. The set of leaves of $T$ is denoted by $L\left(T\right)$ and the set of branch vertices of $T$ is denoted by $B\left(T\right)$. For two distinct vertices $u$, $v$ of $T$, let $P_T[u,v]$ denote the unique path in $T$ connecting $u$ and $v.$ Let $T$ be a tree with $B\left(T\right)\ne \varnothing$. For each leaf $x$ of $T$, let $y_x$ denote the nearest branch vertex to $x$. We delete $V\left(P_T[x,y_x]\right)\setminus \left\{y_x\right\}$ from $T$ for all $x\in L\left(T\right)$. The resulting subtree of $T$ is called the reducible stem...

For a connected graph $G=(V,E)$ and a set $S\subseteq V\left(G\right)$ with at least two vertices, an $S$-Steiner tree is a subgraph $T=(V^{\text{'}},E^{\text{'}})$ of $G$ that is a tree with $S\subseteq V^{\text{'}}$. If the degree of each vertex of $S$ in $T$ is equal to 1, then $T$ is called a pendant $S$-Steiner tree. Two $S$-Steiner trees are if they share no vertices other than $S$ and have no edges in common. For $S\subseteq V\left(G\right)$ and $\left|S\right|\ge 2$, the pendant tree-connectivity ${\tau }_G\left(S\right)$ is the maximum number of internally disjoint pendant $S$-Steiner trees in $G$, and for $k\ge 2$, the $k$-pendant tree-connectivity ${\tau }_k\left(G\right)$ is the...

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

Let $T$ be a tree with $n$ vertices. To each edge of $T$ we assign a weight which is a positive definite matrix of some fixed order, say, $s$. Let $D_{ij}$ denote the sum of all the weights lying in the path connecting the vertices $i$ and $j$ of $T$. We now say that $D_{ij}$ is the distance between $i$ and $j$. Define $D:=\left[D_{ij}\right]$, where $D_{ii}$ is the $s\times s$ null matrix and for $i\ne j$, $D_{ij}$ is the distance between $i$ and $j$. Let $G$ be an arbitrary connected weighted graph with $n$ vertices, where each weight is a positive definite matrix of order...

Let $G_1$ and $G_2$ be two given graphs. The Ramsey number $R(G_1,G_2)$ is the least integer $r$ such that for every graph $G$ on $r$ vertices, either $G$ contains a $G_1$ or $\overline{G}$ contains a $G_2$. Parsons gave a recursive formula to determine the values of $R(P_n,K_{1,m})$, where $P_n$ is a path on $n$ vertices and $K_{1,m}$ is a star on $m+1$ vertices. In this note, we study the Ramsey numbers $R(P_n,K_1\vee F_m)$, where $F_m$ is a linear forest on $m$ vertices. We determine the exact values of $R(P_n,K_1\vee F_m)$ for the cases $m\le n$ and $m\ge 2n$, and for the case that $F_m$ has no odd component. Moreover, we...