Discrete Mathematics, Algorithms and Applications

Blockchain is a promising technology, which may change the way of transactions and affect our lives in the future, and has attracted the attention of more and more scholars recently. This paper provides an overview of the important issues of blockchain and the aim is to lead researchers to comprehensive understand applications, challenges and evaluation from the technical perspective. The basic technology including authorization, incentive and consensus is presented, focusing on their latest methods. Then, a wide range of blockchain applications are described. Specially, some of the latest intersection and integration areas with blockchain are introduced. Moreover, research challenges of blockchain are summarized and analyzed. Finally, evaluation metrics of blockchain are presented and as far as we know, these metrics are first designed for evaluating blockchain performance.

The adjacent vertex distinguishing edge coloring of a graph $G$ is a proper edge coloring of $G$ such that the color sets of any pair of adjacent vertices are distinct. The minimum number of colors required for an adjacent vertex distinguishing edge coloring of $G$ is denoted by ${\chi }_a^{\prime }(G)$. It is observed that ${\chi }_a^{\prime }(G)\ge \mathrm{\Delta }(G)+1$ when $G$ contains two adjacent vertices of degree $\mathrm{\Delta }(G)$. In this paper, we prove that if $G$ is a planar graph without 3-cycles, then ${\chi }_a^{\prime }(G)\le max\{10,\mathrm{\Delta }(G)+1\}$. Furthermore, we characterize the adjacent vertex distinguishing chromatic index for planar graphs of $\mathrm{\Delta }\ge 10$ and without 3-cycles. This improves a result from [D. Huang, Z. Miao and W. Wang, Adjacent vertex distinguishing indices of planar graphs without 3-cycles, Discrete Math. 338 (2015) 139–148] that established ${\chi }_a^{\prime }(G)\le max\{12,\mathrm{\Delta }(G)+1\}$ for planar graphs without 3-cycles.

We propose a scheme for generating a weakly chordal graph on $n$ vertices with $m$ edges. In this method, we first construct a tree and then generate an orthogonal layout (which is a weakly chordal graph on the $n$ vertices) based on this tree. We then insert additional edges, if needed, for a total of $m$ edges. Our algorithm ensures that the graph remains weakly chordal after each edge is inserted. The time complexity of an insertion query is $O(d_u^2{d}_v^2(n+m))$, where $d_u$ and $d_v$ are the degrees of the vertices $u$ and $v$ we want to join with an edge and an insertion takes constant time. The advantages of this method are that it uses very simple data structures and exploits the basic structural properties of a weakly chordal graph.

Binary and $m$-ary trees have extensive applications, particularly in computer science and chemistry. We present exact values of all important distance-based indices for complete $m$-ary trees. We solve recurrence relations to obtain the value of the most well-known index called the Wiener index. New methods are used to express the other indices (the degree distance, the eccentric distance sum, the Gutman index, the edge-Wiener index, the hyper-Wiener index and the edge-hyper-Wiener index) as well. Values of distance-based indices for complete binary trees are corollaries of the main results.

A set S of vertices in a connected graph $G=(V,E)$ is called a geodetic set if every vertex not in $S$ lies on a shortest path between two vertices from $S$. A set $D$ of vertices in $G$ is called a dominating set of $G$ if every vertex not in $D$ has at least one neighbor in $D$. A set $S$ is called a geodetic global dominating set of $G$ if $S$ is both geodetic and global dominating set of $G$. The geodetic global domination number is the minimum cardinality of a geodetic global dominating set in $G$. In this paper, we determine the geodetic global domination number of the corona and strong products of two graphs.

In this paper, we study the double Roman domination number of generalized Sierpiński graphs $S(G,t)$. More precisely, we obtain a bound for the double Roman domination number of $S(G,t)$. We also find the exact value of ${\gamma }_{\mathrm{\text{dR}}}(S(K_n,2))$.

Starter sequences are natural generalizations of well-known Skolem sequences. In this paper, we introduce different types of starter sequences and determine some of the conditions for their existence; we also extend the results to $m$-fold starter sequences and excess starter sequences.

Let $G=(V,E)$ be a graph and $f:V\to \{0,1,2\}$ be a function. A vertex $u\in V$ with weight $f(u)$ is said to be undefended with respect to $f$, if it is not adjacent to any vertex with positive weight. The function $f$ is a weak Roman dominating function (WRDF) if each vertex $u$ with $f(u)=0$ is adjacent to a vertex $v$ with $f(v)>0$ such that the function $f^{\prime }:V\to \{0,1,2\}$ defined by $f^{\prime }(u)=1$, $f^{\prime }(v)=f(v)-1$ and $f^{\prime }(w)=f(w)$ if $w\in V-\{u,v\}$, has no undefended vertex. The weight of $f$ is $w(f)={\sum }_{v\in V}f(v)$. The weak Roman domination number, denoted by ${\gamma }_r(G)$, is the minimum weight of a WRDF on $G$. In this paper, we present two linear time algorithms one that obtains the weak Roman domination number of an arbitrary tree and the labeling of its vertices, to produce the weak Roman domination number, and the other, that determines whether the given tree is in $r_{UVR}$.

The concept of reciprocal degree distance $\mathrm{\text{RDD}}(G)$ of a connected graph $G$ was introduced in 2012. The Steiner distance in a graph, introduced by Chartrand et al. in 1989, is a natural generalization of the concept of classical graph distance. The $k$-center Steiner reciprocal degree distance defined as ${\mathrm{\text{SRDD}}}_k(G)={\sum }_{\begin{array}{c}S\subseteq V(G)\\ \left|S\right|=k\end{array}}[{\sum }_{v\in S}{\mathrm{\text{deg}}}_G(v)]\frac{1}{d_G(S)}$, where $d_G(S)$ is the Steiner $k$-distance of $S$ and ${\mathrm{\text{deg}}}_G(v)$ is the degree of the vertex $v$ in $G$. Motivated from Zhang’s paper [X. Zhang, Reciprocal Steiner degree distance, Utilitas Math., accepted for publication], we find the expression for ${\mathrm{\text{SRDD}}}_k$ of complete bipartite graphs. Also, we give a straightforward method to compute Steiner Gutman index and Steiner degree distance of path.

For a group $G$ and a subset $S$ of $G$ the bi-Cayley graph BCay$(G,S)$ of $G$ with respect to $S$ is the bipartite graph with vertex set $G\times \{0,1\}$ and edge set $\{\{(x,0),(sx,1)\}|x\in G,s\in S\}$. A bi-Cayley graph BCay$(G,S)$ is called a BCI-graph if for any bi-Cayley graph BCay$(G,T)$, $\mathrm{\text{BCay}}(G,S)\cong \mathrm{\text{BCay}}(G,T)$ implies that $T=g{S}^{\alpha }$ for some $g\in G$ and $\alpha \in \mathrm{\text{Aut}}(G)$. A group $G$ is called a $m$-BCI-group if all bi-Cayley graphs of $G$ with valency at most $m$ are BCI-graphs. In this paper, we characterize the $m$-BCI dihedral groups for $m\le 3$. Also, we show that the dihedral group $D_{2p}$ ($p$ is prime) is a $4$-BCI-group.

Let $k$ be a positive integer and $G$ be a simple connected graph. The eccentric distance sum of $G$ is defined as ${\xi }^d(G)={\sum }_{v\in V(G)}{𝜀}_G(v)D_G(v)$, where ${𝜀}_G(v)$ is the maximum distance from $v$ to any other vertex and $D_G(v)={\sum }_{u\in V(G)}{d}_G(u,v)$ is the sum of all distances from $v$. A set $D\subseteq V(G)$ is a distance $k$-dominating set of $G$ if for every vertex $u\in V(G)\setminus D$, $d_G(u,v)\le k$ for some vertex $v\in D$. The minimum cardinality among all distance $k$-dominating sets of $G$ is called the distance $k$-domination number ${\gamma }_k(G)$ of $G$. In this paper, the trees among all $n$-vertex trees with distance $k$-domination number ${\gamma }_k$ having the minimal eccentric distance sum are determined.

The strong nonsplit domination polynomial of a graph $G$ of order $n$ is the polynomial $D_{\mathrm{\text{sns}}}(G,x)={\sum }_{i={\gamma }_{\mathrm{\text{sns}}}(G)}^n{d}_{\mathrm{\text{sns}}}(G,i)x^i$, where $d_{\mathrm{\text{sns}}}(G,i)$ is the number of strong nonsplit dominating sets of $G$ of size $i$ and ${\gamma }_{\mathrm{\text{sns}}}(G)$ is the strong nonsplit domination number of $G$. We obtain some properties of $D_{\mathrm{\text{sns}}}(G,x)$ and its coefficients. Also, we compute the polynomial for some specific graphs.

The Wiener index of a connected graph is the sum of the distance of all pairs of distinct vertices. It was introduced by Wiener in 1947 to analyze some aspects of branching by fitting experimental data for several properties of alkane compounds. Denote by ${{𝒰}}_{n,r}$ the set of unicyclic graphs with $n$ vertices and $r$ vertices of even degree. In this paper, we present a structural result on the graphs in ${{𝒰}}_{n,r}$ with minimum Wiener index and completely characterize such graphs when $r\le \frac{n+3}{2}$.

Let $G=(V,E)$ be a simple undirected graph. $G$ is a circulant graph defined on $V={\mathbb{Z}}_n$ with difference set $D\subseteq \{1,2,\dots ,\lfloor \frac{n}{2}\rfloor \}$ provided two vertices $i$ and $j$ in ${\mathbb{Z}}_n$ are adjacent if and only if $min\{|i-j|,n-|i-j|\}\in D$. For convenience, we use $G(n;D)$ to denote such a circulant graph.

A function $f:V(G)\to \mathbb{N}\cup \{0\}$ is an integer $\{k\}$-domination function if for each $v\in V(G)$, ${\sum }_{u\in N_G[v]}f(u)\ge k.$ By considering all $\{k\}$-domination functions $f$, the minimum value of ${\sum }_{v\in V(G)}f(v)$ is the $\{k\}$-domination number of $G$, denoted by ${\gamma }_k(G)$. In this paper, we prove that if $D=\{1,2,\dots ,t\}$, $1\le t\le \frac{n-1}{2}$, then the integer $\{k\}$-domination number of $G(n;D)$ is $\lceil \frac{kn}{2t+1}\rceil$.

Edges that are the unique chords of at least one cycle have been studied by a variety of authors over the past dozen years. This paper begins the study of those graphs in which each edge is the unique chord of exactly one cycle. The $3$-connected planar graphs that enjoy this restriction are characterized by two infinite sequences (the dipyramid and trapezohedron $3$-polytopes) together with three special graphs (the $4$-antiprism, and the $5$- and $6$-prism graphs).