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

We consider random dynamics on the edges of a uniform Cayley tree with $n$ vertices, in which edges are either flammable, fireproof, or burnt. Every flammable edge is replaced by a fireproof edge at unit rate, while fires start at smaller rate $n^{-\alpha }$ on each flammable edge, then propagate through the neighboring flammable edges and are only stopped at fireproof edges. A vertex is called fireproof when all its adjacent edges are fireproof. We show that as $n\to \infty$, the terminal density of fireproof...

Let G be a graph of order n and size m. A γ-labeling of G is a one-to-one function f:V(G) → 0,1,2,...,m that induces a labeling f’: E(G) → 1,2,...,m of the edges of G defined by f’(e) = |f(u)-f(v)| for each edge e = uv of G. The value of a γ-labeling f is $val\left(f\right)={\Sigma }_{e\in E\left(G\right)}{f}^{\text{'}}K\left(e\right)$. The maximum value of a γ-labeling of G is defined as $va{l}_{max}\left(G\right)=maxval\left(f\right):fisa\gamma -labelingofG$; while the minimum value of a γ-labeling of G is $va{l}_{min}\left(G\right)=minval\left(f\right):fisa\gamma -labelingofG$; The values $va{l}_{max}\left(S_{p,q}\right)$ and $va{l}_{min}\left(S_{p,q}\right)$ are determined for double stars $S_{p,q}$. We present characterizations of connected graphs G of order n for which...

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

For any two positive integers $n$ and $k\ge 2$, let $G(n,k)$ be a digraph whose set of vertices is $\{0,1,...,n-1\}$ and such that there is a directed edge from a vertex $a$ to a vertex $b$ if $a^k\equiv b(modn)$. Let $n={\prod }_{i=1}^r{p}_i^{e_i}$ be the prime factorization of $n$. Let $P$ be the set of all primes dividing $n$ and let $P_1,P_2\subseteq P$ be such that $P_1\cup P_2=P$ and $P_1\cap P_2=\varnothing$. A fundamental constituent of $G(n,k)$, denoted by $G_{P_2}^{*}(n,k)$, is a subdigraph of $G(n,k)$ induced on the set of vertices which are multiples of ${\prod }_{p_i\in P_2}{p}_i$ and are relatively prime to all primes $q\in P_1$. L. Somer and M. Křížek proved that the trees attached...

In this paper, we investigate a measure of similarity of graphs similar to the Ramsey number. We present values and bounds for $g(n,l)$, the biggest number $k$ guaranteeing that there exist $l$ graphs on $n$ vertices, each two having edit distance at least $k$. By edit distance of two graphs $G$, $F$ we mean the number of edges needed to be added to or deleted from graph $G$ to obtain graph $F$. This new extremal number $g(n,l)$ is closely linked to the edit distance of graphs. Using probabilistic methods we show...

Let $G=\left(V\right(G),E(G\left)\right)$ be a simple graph and $E_G\left(v\right)$ denote the set of edges incident with a vertex $v$. A neighbor sum distinguishing (NSD) total coloring $\phi$ of $G$ is a proper total coloring of $G$ such that ${\sum }_{z\in E_G\left(u\right)\cup \left\{u\right\}}\phi \left(z\right)\ne {\sum }_{z\in E_G\left(v\right)\cup \left\{v\right\}}\phi \left(z\right)$ for each edge $uv\in E\left(G\right)$. Pilśniak and Woźniak asserted in 2015 that each graph with maximum degree $\Delta$ admits an NSD total $(\Delta +3)$-coloring. We prove that the list version of this conjecture holds for any IC-planar graph with $\Delta \ge 11$ but without $5$-cycles by applying the Combinatorial Nullstellensatz.

The domination subdivision number $s{d}_{\gamma }\left(G\right)$ of a graph is the minimum number of edges that must be subdivided (where an edge can be subdivided at most once) in order to increase the domination number. Arumugam showed that this number is at most three for any tree, and conjectured that the upper bound of three holds for any graph. Although we do not prove this interesting conjecture, we give an upper bound for the domination subdivision number for any graph G in terms of the minimum degrees of...

The generalized $k$-connectivity ${\kappa }_k\left(G\right)$ of a graph $G$ was introduced by Chartrand et al. in 1984. As a natural counterpart of this concept, Li et al. in 2011 introduced the concept of generalized $k$-edge-connectivity which is defined as ${\lambda }_k\left(G\right)=min\{\lambda \left(S\right):S\subseteq V\left(G\right)$ and $\left|S\right|=k\}$, where $\lambda \left(S\right)$ denotes the maximum number $\ell$ of pairwise edge-disjoint trees $T_1,T_2,...,T_{\ell }$ in $G$ such that $S\subseteq V\left(T_i\right)$ for $1\le i\le \ell$. In this paper we prove that for any two connected graphs $G$ and $H$ we have ${\lambda }_3(G\square H)\ge {\lambda }_3\left(G\right)+{\lambda }_3\left(H\right)$, where $G\square H$ is the Cartesian product of $G$ and $H$. Moreover, the bound is sharp. We also...

A total dominating set of a graph G = (V,E) with no isolated vertex is a set S ⊆ V such that every vertex is adjacent to a vertex in S. A total dominating set S of a graph G is a locating-total dominating set if for every pair of distinct vertices u and v in V-S, N(u)∩S ≠ N(v)∩S, and S is a differentiating-total dominating set if for every pair of distinct vertices u and v in V, N[u]∩S ≠ N[v] ∩S. Let $\gamma {ₜ}^L\left(G\right)$ and $\gamma {ₜ}^D\left(G\right)$ be the minimum cardinality of a locating-total dominating set and a differentiating-total...

Let $ex(n,G)$ denote the maximum number of edges in a graph on $n$ vertices which does not contain $G$ as a subgraph. Let $P_i$ denote a path consisting of $i$ vertices and let $m{P}_i$ denote $m$ disjoint copies of $P_i$. In this paper we count $ex(n,3P_4)$.

Let $T_1,\cdots ,T_d$ be homogeneous trees with degrees $q_1+1,\cdots ,q_d+1\ge 3$, respectively. For each tree, let $𝔥:T_j\to \mathbb{Z}$ be the Busemann function with respect to a fixed boundary point (end). Its level sets are the horocycles. The horocyclic product of $T_1,\cdots ,T_d$ is the graph $\mathrm{𝖣𝖫}(q_1,\cdots ,q_d)$ consisting of all $d$-tuples $x_1\cdots x_d\in T_1\times \cdots \times T_d$ with $𝔥\left(x_1\right)+\cdots +𝔥\left(x_d\right)=0$, equipped with a natural neighbourhood relation. In the present paper, we explore the geometric, algebraic, analytic and probabilistic properties of these graphs and their isometry groups. If $d=2$ and $q_1=q_2=q$ then we obtain a Cayley graph...

Edge-colourings of graphs have been studied for decades. We study edge-colourings with respect to hereditary graph properties. For a graph $G$, a hereditary graph property $𝒫$ and $l\ge 1$ we define ${\chi }_{𝒫,l}^{\text{'}}\left(G\right)$ to be the minimum number of colours needed to properly colour the edges of $G$, such that any subgraph of $G$ induced by edges coloured by (at most) $l$ colours is in $𝒫$. We present a necessary and sufficient condition for the existence of ${\chi }_{𝒫,l}^{\text{'}}\left(G\right)$. We focus on edge-colourings of graphs with respect to the hereditary...