Hrnciar and Haviar [3] gave a method to construct a graceful labeling for all trees of diameter at most five. Based on their method and the methods described in Balbuena et al. [1], we shall describe a new construction for gracefully labeled trees by attaching trees to the vertices of a tree admitting a bipartite graceful labeling.

Given two graphs $G$ and $H$ and a function $f\subset V(G)\times V(H)$, Hedetniemi [9] defined the \emph{function graph} $GfH$ by $V(GfH)=V(G)\cup V(H)$ and $E(GfH)=E(G)\cup E(H)\cup \{uv\mid v:f(u)\}$. Whenever $G\cong H$, the function graph was called a functigraph by Chen, Ferrero, Gera, and Yi [7]. A function graph is a generalization of the $\alpha$-permutation graph introduced by Chartrand and Harary [5]. The independence number of a graph is the size of a largest set of mutually non-adjacent vertices. In this paper, we study independence number in function graphs. In particular, we give a lower bound in terms of the order and the chromatic number, which improves on some elementary results and has a number of interesting corollaries.

A $k$-edge labeling of a graph $G$ is a function $f$ from the edge set $E(G)$ to the set of integers $\{0,\dots ,k-1\}$. Such a labeling induces a labeling $f$ on the vertex set $V(G)$ by defining $f(v)=\sum f(e)$, where the summation is taken over all the edges incident on the vertex $v$ and the value is reduced modulo $k$. Cahit calls this labeling edge-$k$-equitable if $f$ assigns the labels $\{0,\dots ,k-1\}$ equitably to the vertices as well as edges.

If $G_1,\dots ,G_T$ is a family of graphs each having a graph $H$ as an induced subgraph, then by $H$-union $G$ of this family we mean the graph obtained by identifying all the corresponding vertices as well as edges of the copies of $H$ in $G_1,\dots ,G_T$.

In this paper, which is a sequel to the paper entitled `On edge-$3$-equitability of ${\overline{K}}_n$-union of gears’, we prove that ${\overline{K}}_n$-union of copies of helm $H_n$ is edge-$3$-equitable for all $n\ge 6$.

A graceful labeling of a graph $G$ with $q$ edges is an injective assignment from the vertices of $G$ into $\{0,1,\dots ,q\}$ such that when each edge is assigned the absolute value of the difference of the vertex labels it connects, the resulting edge labels are distinct. In 1978, Frucht conjectured that for gracefully labeled coronas $C_n\odot K_1$, the omitted vertex label is always even. In this paper, we will verify Frucht’s conjecture.

Let $\mathcal{C}=\{C_1,\dots ,C_n\}$ be a family of distinct boxes in ${\mathbb{R}}^d$, and let $S=C_1\cup \cdots \cup C_n$. Assume that $S$ is staircase starshaped. If the intersection graph of $\mathcal{C}$ is a tree, then the staircase kernel of $S$, $\ker S$, will be staircase convex. However, an example in ${\mathbb{R}}^3$ reveals that, without this requirement on the intersection graph of $\mathcal{C}$, components of $\ker S$ need not be staircase convex. Thus the structure of the kernel in higher dimensional staircase starshaped sets provides a striking contrast to its structure in planar sets.

We study cube-complementary graphs, that is, graphs whose com- plement and cube are isomorphic. We prove several necessary conditions for a graph to be cube-complementary, describe ways of building new cube-complementary graphs from existing ones, and construct infinite families of cube-complementary graphs.

We suggest the notion of the surface area centered at an edge for a network structure, which generalizes the usual notion of surface area of a structure centered at a vertex. As a specific result, we derive explicit expressions of the edge-centered surface areas for the edge-asymmetric $(n,k)$-star graph, following a generating function approach, in terms of two different kinds of edges.

For a set $S$ of $k$ vertices of $G$, let $\kappa (S)$ denote the maximum number $\ell$ of pairwise edge-disjoint trees $T_1,T_2,\dots ,T_{\ell }$ in $G$ such that $V(T_i)\cap V(T_j)=S$ for $1\le i\ne j\le \ell$ and $\lambda (S)$ denote the maximum number $\ell$ of pairwise edge-disjoint trees $T_1,T_2,\dots ,T_{\ell }$ in $G$ such that $S\subseteq V(T_i)$ for $1\le i\le \ell$. Similar to the classical maximum local connectivity, H. Li et al. introduced the parameter ${\overline{\kappa }}_k(G)=max\{\kappa (S)\mid S\subseteq V(G),|S|=k\}$, which is called the maximum generalized local connectivity of $G$. The maximum generalized local edge-connectivity of $G$ which was introduced by X. Li et al. is defined as ${\overline{\lambda }}_k(G)=max\{\lambda (S)\mid S\subseteq V(G),|S|=k\}$. In this paper, we investigate the maximum generalized local connectivity and edge-connectivity of a cubic connected Cayley graph $G$ on an Abelian group. We determine the precise values for ${\overline{\kappa }}_3(G)$ and ${\overline{\lambda }}_3(G)$ and also prove some results of ${\overline{\kappa }}_k(G)$ and ${\overline{\lambda }}_k(G)$ for general $k$.

The generalized $k$-connectivity ${\kappa }_k(G)$ 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. In this paper, we completely determine the precise values of the generalized $3$-connectivity and generalized $3$-edge-connectivity for the Cartesian products of some graph classes.

In this work, we investigate the gap-adjacent-chromatic number, a graph colouring parameter introduced by M. A. Tahraoui, E. Duchéne, and H. Kheddouci in $[5]$. From an edge labelling $f:E\to \{1,\dots ,k\}$ of a graph $G=(V,E)$, the vertices of $G$ get an induced colouring. Vertices of degree greater than one are coloured with the difference between their maximum and their minimum incident edge label, i.e., with their so-called gap, and vertices of degree one get their incident edge label as colour. The gap-adjacent-chromatic number of $G$ is the minimum $k$ for which a labelling $f$ of $G$ exists that induces a proper vertex colouring.

The main purpose of this work is to state easy colouring approaches for bipartite graphs and to estimate the gap-adjacent-chromatic number for arbitrary graphs in terms of the chromatic number.

We call $T=(G_1,G_2,G_3)$ a graph-triple of order $t$ if the $G_i$ are pairwise non-isomorphic graphs on $t$ non-isolated vertices whose edges can be combined to form $K_t$. If $m\ge t$, we say $T$ divides $K_m$ if $E(K_m)$ can be partitioned into copies of the graphs in $T$ with each $G_i$ used at least once, and we call such a partition a $T$-multidecomposition. For each graph-triple $T$ of order $6$ for which it was not previously known, we determine all $K_m$, $m\ge 6$, that admit a $T$-multidecomposition. Moreover, we determine maximum multipackings and minimum multicoverings when $K_m$ does not admit a multidecomposition.

For the Firefighter Process with weights on the vertices, we show that the problem of deciding whether a subset of vertices of a total weight can be saved from burning remains NP-complete when restricted to binary trees. In addition, we show that a greedy algorithm that defends the vertex of highest degree adjacent to a burning vertex is not an $ϵ$-\emph{approximation} algorithm for any $ϵ\in (0,1]$ for the problem of determining the maximum weight that can be saved. This closes an open problem posed by MacGillivray and Wang.

Let $K_v$ be the complete graph with $v$ vertices. Let $G$ be a finite simple graph. A $G$-decomposition of $K_v$, denoted by $(v,G,1)$-GD, is a pair $(X,\mathcal{B})$, where $X$ is the vertex set of $K_v$, and $\mathcal{B}$ is a collection of subgraphs of $K_v$, called blocks, such that each block is isomorphic to $G$. In this paper, the discussed graphs are $G_i$, $i=1,2,3,4$, where $G_i$ are four kinds of graphs with eight vertices and eight edges. We obtain the existence spectrum of $(v,G_i,1)$-GD.

We present a simple bijection between the set of triangulations of a convex polygon and the set of $312$-avoiding permutations.

A $2-rainbowdominatingfunction$ of a graph $G$ is a function $g$ that assigns to each vertex a set of colors chosen from the set $\{1,2\}$ so that for each vertex $v$ with $g(v)=\mathrm{\varnothing }$ we have ${\cup }_{u\in N(v)}g(u)=\{1,2\}$. The minimum of $g(V(G))=\sum _{v\in V(G)}|g(v)|$ over all such functions is called the $2-rainbowdominationnumber$ ${\gamma }_{r2}(G)$. A $2$-rainbow dominating function $g$ of a graph $G$ is independent if no two vertices assigned non-empty sets are adjacent. The $independent2-rainbowdominationnumber$ $i_{r2}(G)$ is the minimum weight of an independent $2$-rainbow dominating function of $G$. In this paper, we study independent $2$-rainbow domination in graphs. We present some bounds and relations with other domination parameters.

For a connected graph $G$ of order at least $3$ and an integer $k\ge 2$, a $twinedge$ $k$-coloring of $G$ is a proper edge coloring of $G$ with the elements of ${\mathbb{Z}}_k$, so that the induced vertex coloring in which the color of a vertex $v$ in $G$ is the sum (in ${\mathbb{Z}}_k$) of the colors of the edges incident with $v$ is a proper vertex coloring. The minimum $k$ for which $G$ has a twin edge $k$-coloring is called the $twinchromaticindex$ of $G$ and is denoted by ${\chi }_t^{\prime }(G)$. It was conjectured that $\mathrm{\Delta }(T)\le {\chi }_t^{\prime }(T)\le 2+\mathrm{\Delta }(T)$ for every tree of order at least $3$, where $\mathrm{\Delta }(T)$ is the maximum degree of $T$. This conjecture is verified for several classes of trees, namely brooms, double stars, and regular trees.

For a nontrivial connected graph $G$, let $c:V(G)\to {\mathbb{Z}}_2$ be a vertex coloring of $G$ where $c(v)\ne 0$ for at least one vertex $v$ of $G$. Then the coloring $c$ induces a new coloring $\sigma :V(G)\to {\mathbb{Z}}_2$ of $G$ defined by
$$\sigma (v)=\sum _{u\in N[v]}c(u)$$
where $N[v]$ is the closed neighborhood of $v$ and addition is performed in ${\mathbb{Z}}_2$. If $\sigma (v)=0\in {\mathbb{Z}}_2$ for every vertex $v$ in $G$, then the coloring $c$ is called a (modular) monochromatic $(2,0)$-coloring of $G$. A graph $G$ having a monochromatic $(2,0)$-coloring is a (monochromatic) $(2,0)$-colorable graph. The minimum number of vertices colored $1$ in a monochromatic $(2,0)$-coloring of $G$ is the $(2,0)$-chromatic number of $G$ and is denoted by ${\chi }_{(2,0)}(G)$. For a $(2,0)$-colorable graph $G$, the monochromatic $(2,0)$-spectrum $S_{(2,0)}(G)$ of $G$ is the set of all positive integers $k$ for which exactly $k$ vertices of $G$ can be colored $1$ in a monochromatic $(2,0)$-coloring of $G$. Monochromatic $(2,0)$-spectra are determined for several well-known classes of graphs. If $G$ is a connected graph of order $n\ge 2$ and $a\in S_{(2,0)}(G)$, then $a$ is even and $1\le |S_{(2,0)}(G)|\le \lfloor \frac{n}{2}\rfloor$. It is shown that for every pair $k,n$ of integers with $1\le k\le \lfloor \frac{n}{2}\rfloor$, there is a connected graph $G$ of order $n$ such that $|S_{(2,0)}(G)|=k$. A set $S$ of positive even integers is $(2,0)$-realizable if $S$ is the monochromatic $(2,0)$-spectrum of some connected graph. Although there are infinitely many non-$(2,0)$-realizable sets, it is shown that every set of positive even integers is a subset of some $(2,0)$-realizable set. Other results and questions are also presented on $(2,0)$-realizable sets in graphs.

For two graphs $H$ and $G$, a decomposition $\mathcal{D}=\{H_1,H_2,\dots ,H_k,R\}$ of $G$ is called an $H$-maximal $k$-decomposition if $H_i\cong H$ for $1\le i\le k$ and $R$ contains no subgraph isomorphic to $H$. Let $\text{Min}(G,H)$ and $\text{Max}(G,H)$ be the minimum and maximum $k$, respectively, for which $G$ has an $H$-maximal $k$-decomposition. A graph $G$ without isolated vertices is said to possess the intermediate decomposition property if for each connected graph $G$ and each integer $k$ with $\text{Min}(G,H)\le k\le \text{Max}(G,H)$, there exists an $H$-maximal $k$-decomposition of $G$. For a set $S$ of graphs and a graph $G$, a decomposition $\mathcal{D}=\{H_1,H_2,\dots ,H_k,R\}$ of $G$ is called an $S$-maximal $k$-decomposition if $H_i\cong H$ for some $H\in S$ for each integer $i$ with $1\le i\le k$ and $R$ contains no subgraph isomorphic to any subgraph in $S$. Let $\text{Min}(G,S)$ and $\text{Max}(G,S)$ be the minimum and maximum $k$, respectively, for which $G$ has an $S$-maximal $k$-decomposition. A set $S$ of graphs without isolated vertices is said to possess the intermediate decomposition property if for every connected graph $G$ and each integer $k$ with $\text{Min}(G,S)\le k\le \text{Max}(G,S)$, there exists an $S$-maximal $k$-decomposition of $G$. While all those graphs of size $3$ have been determined that possess the intermediate decomposition property, as have all sets consisting of two such graphs, here all remaining sets of graphs having size $3$ that possess the intermediate decomposition property are determined.

An Eulerian graph $G$ of size $m$ is said to satisfy the Eulerian Cycle Decomposition Conjecture if the minimum number of odd cycles in a cycle decomposition of $G$ is $a$, the maximum number of odd cycles in a cycle decomposition is $b$, and $\ell$ is an integer such that $a\le \ell \le b$ where $\ell$ and $m$ are of the same parity, then there is a cycle decomposition of $G$ with exactly $\ell$ odd cycles. Several regular complete $5$-partite graphs are shown to have this property.

An $H_3$ graph is a multigraph on three vertices with double edges between two pairs of distinct vertices and a single edge between the third pair. To settle the $H_3$ decomposition problem completely, one needs to complete the decomposition of a $2K_{10t+5}$ into $H_3$ graphs. In this paper, we present two new construction methods for such decompositions, resulting in previously unknown decompositions for $v=15,25,35,45$ and two new infinite families.

Analog modulation has served us very well over the years. Digital modulation is an improvement over analog modulation because it provides better bandwidth utilization over analog modulation, less power for signal propagation, it is natural for packet transmission, forward error correction, automatic repeat request, encryption, compression, and signal transformation so that it looks like noise to the adversary. Digital wireless communication is an enormous area that is rapidly growing. Digital communication is a field in which theoretical ideas have had an unusually powerful impact on system design and practice. In this research paper we provide a digital modulation algorithm for efficient transmission based on circular probability distribution theory.

A primitive hypergraph is a hypergraph with maximum cardinality three and maximum degree three such that every $3$-edge is adjacent only to $2$-edges and is incident only to vertices of degree two. Deciding the bicolorability of a primitive hypergraph is NP-complete (a straightforward consequence of results in [14]). We provide sufficient conditions, similar to the Sterboul conditions proved by Défossez [5], for the existence of a bicoloring of a primitive hypergraph, and we provide a polynomial algorithm for bicoloring a primitive hypergraph if those conditions hold. We then draw a connection between this algorithm and the well-known necessary and sufficient conditions given by Berge [1] for maximal matchings in graphs, which leads to a characterization of bicolorability of primitive hypergraphs.

Let $D$ be a strongly connected oriented graph with vertex-set $V$ and arc-set $A$. The distance from a vertex $u$ to another vertex $v$, $d(u,v)$, is the minimum length of oriented paths from $u$ to $v$. Suppose $B=\{b_1,b_2,b_3,\dots ,b_k\}$ is a nonempty ordered subset of $V$. The representation of a vertex $v$ with respect to $B$, $r(v|B)$, is defined as a vector $(d(v,b_1),d(v,b_2),\dots ,d(v,b_k))$. If any two distinct vertices $u,v$ satisfy $r(u|B)\ne r(v|B)$, then $B$ is said to be a resolving set of $D$. If the cardinality of $B$ is minimum, then $B$ is said to be a basis of $D$, and the cardinality of $B$ is called the directed metric dimension of $D$.

Let $G$ be the underlying graph of $D$ admitting a $C_n$-covering. A $C_n$-simple orientation is an orientation on $G$ such that every $C_n$ in $D$ is strongly connected. This paper deals with metric dimensions of oriented wheels, oriented fans, and amalgamation of oriented cycles, all of which admit $C_n$-simple orientations.

A Stanton-type graph $S(n,m)$ is a connected multigraph on $n$ vertices such that for a fixed integer $m$ with $n–1\le m\le (\genfrac{}{}{0ex}{}{n}{2})$, there is exactly one edge of multiplicity $i$ (and no others) for each $i=1,2,\dots ,m$. In a recent paper, the authors decomposed $\lambda K_n$ (for the appropriate minimal values of $\lambda$) into two of the four possible types of $S(4,3)$’s. In this note, decompositions of $\lambda K_n$ (for the appropriate minimal values of $\lambda$) into the remaining two types of $S(4,3)$’s are given.