Discrete Mathematics, Algorithms and Applications

Galileo sequences are generalizations of a simple sequence of integers that Galileo used in early 17th century for describing his law of falling bodies. The curious property he noted happens to be exactly what is needed to quantify his observation that the acceleration of falling bodies is uniform. Among the generalizations and extensions later given are iterated Galileo sequences. We show that these are closely related to polynomials that arise in enumerating integers by their Hamming weight.

We introduce a new notion of convexity in digraphs, which we call incoming-path convexity, and prove that the incoming-path convexity space of a digraph is a convex geometry (that is, it satisfies the Minkowski–Krein–Milman property) if and only if the digraph is acyclic. Moreover, we prove that incoming-path convexity is adequate to characterize collapsibility of models generated by Bayesian networks. Based on these results, we also provide simple linear algorithms to solve two topical problems on Markov properties of a Bayesian network (that is, on conditional independences valid in a Bayesian network).

In this paper, we give lower and upper bounds on the covering radius of codes over the ring $R={\mathbb{Z}}_2+u{\mathbb{Z}}_2,$ where $u^2=0$ with respect to Chinese Euclidean distance and also obtain the covering radius of various Repetition codes, Simplex codes of $\alpha$-Type code and $\beta$-Type code. We give bounds on the covering radius for MacDonald codes of both types over $R={\mathbb{Z}}_2+u{\mathbb{Z}}_2.$

This paper introduces a new domination parameter called coefficient of domination of a graph, which measures the maximum possible efficiency of domination for the given graph. It is evaluated for various classes of graphs and different bounds are proposed. Finally, Nordhaus–Gaddum type inequalities are established for coefficient of domination of a graph and its complement.

Let ${𝒢}$ be a family of graphs. The anti-Ramsey number $AR(G,{𝒢})$ for ${𝒢}$ in the graph $G$ is the maximum number of colors in an edge coloring of $G$ that does not have any rainbow copy of any graph in ${𝒢}$. In this paper, we consider the anti-Ramsey number for matchings in regular bipartite graphs and determine its value under several conditions.

There tend to be no related researches regarding the relationships between graph theory and languages ever since the concept of graph-semigroup was first proposed in 1991. In 2011, after finding out the inner co-relations among digraphs, undirected graphs and languages, we proposed certain concepts including undirected graph language and digraph language; moreover, in 2014, we proposed a broaden concept–(V,R)-language and proved: (1) both undirected graph language and digraph language are (V,R)-languages; (2) both undirected graph language and digraph language are regular languages; (3) natural languages are regular languages. In this paper, we propose a new concept–Random Graph Language and build the relationships between random graph and language, which provides researchers with the possibility to do research about languages by using random graph theory.

A paged recursive tree is constructed as a recursive tree except that it depends on an integer parameter $b\ge 1$ representing a page capacity, small subtrees with size $\le b$. We investigate the number of nodes $N_n$ (size of the tree) in paged recursive trees built from labels $1,\dots ,n$. The expectation and variance of $N_n$ are derived, and it is also shown that $N_n$ is asymptotically normal.

The Mycielski’s construction is a well-known construction on graphs which transforms a $k$-chromatic triangle-free graph $G$ into a $(k+1)$-chromatic triangle-free graph $\mu (G)$ which is called the Mycielski graph of $G$. In this paper, we compute the Harary index, additively weighted Harary index, and multiplicatively weighted Harary index of the Mycielski graph of any simple connected graph with girth greater than $6$.

A Roman dominating function (RDF) on a graph $G=(V,E)$ is a function $f:V\to \{0,1,2\}$ satisfying the condition that every vertex $u$ with $f(u)=0$ is adjacent to at least one vertex $v$ of $G$ for which $f(v)=2$. The weight of a RDF is the sum $f(V)={\sum }_{v\in V}f(v)$, and the minimum weight of a RDF $f$ is the Roman domination number ${\gamma }_R(G)$. A subset $S$ of $V$ is a $2$-independent set of $G$ if every vertex of $S$ has at most one neighbor in $S.$ The maximum cardinality of a $2$-independent set of $G$ is the $2$-independence number ${\beta }_2(G).$ Both parameters are incomparable in general, however, we show that if $T$ is a tree, then ${\beta }_2(T)\ge {\gamma }_R(T)$. Moreover, all extremal trees attaining equality are characterized.

In this paper, we study the signed $k$-domination and its total version in graphs. By a simple uniform approach we give some new upper and lower bounds on these two parameters of a graph in terms of several different graph parameters. In this way, we can improve and generalize some results in literature. Moreover, we make use of the well-known theorem of Turán [On an extremal problem in graph theory, Math. Fiz. Lapok 48 (1941) 436–452] to bound the signed total $k$-domination number, ${\gamma }_{kS}^t(G)$, of a $K_{r+1}$-free graph $G$ for $r\ge 2$.

Let ${{𝒯}}_n$ be the set of trees with $n$ vertices. The first six trees with the maximal Estrada indices in ${{𝒯}}_n$ with $n\ge 6$ were previously reported. A new transformation for studying the Estrada index is introduced. Then, with the aid of the new transformation, we completely deduce the 7th to the 13th trees with the maximal Estrada indices in ${{𝒯}}_n$ with $n\ge 12$. Furthermore, for the trees in ${{𝒯}}_n$ with $n\ge 12$, we obtain the relationship among three decreasing orders, namely, by their largest Estrada indices, by their largest eigenvalues, and by their largest resolvent Estrada indices, respectively.

We study the problem of using mobile guards to defend the vertices of a graph $G=(V,E)$ against a single attack on its vertices. A vertex cover of a graph $G$ is a set $S\subseteq V(G)$ such that for each edge $uv\in E(G)$, at least one of $u$ or $v$ is in $S$. The minimum cardinality of a vertex cover is termed the vertex covering number and it is denoted by $\alpha (G)$. In this context, we introduce a new protection strategy called the secure vertex cover$($SVC$)$ problem, where the guards are placed at the vertices of a graph, in order to protect the graph against a single attack on its vertices. We are concerned with the protection of $G$ against a single attack, using at most one guard per vertex and require the set of guarded vertices to be a vertex cover. In addition, if any guard moves along an edge to deal with an attack to an unguarded vertex, then the resulting placement of guards must also form a vertex cover. Formally, this protection strategy defends the vertices of a graph against a single attack and simultaneously protects the edges. We define a SVC to be a set $S\subseteq V$ such that $S$ is a vertex cover and for each $u\in V\backslash S$, there exists a $v\in S\cap N(u)$ such that $(S\backslash \{v\})\cup \{u\}$ is a vertex cover. The minimum cardinality of an SVC is called the secure vertex covering number and it is denoted by ${\alpha }_s(G)$. In this paper, a few properties of SVC of a graph are studied and specific values of ${\alpha }_s(G)$ for few classes of well-known graphs are evaluated.

A set $W\subseteq V(G)$ is called a resolving set, if for each pair of distinct vertices $u,v\in V(G)$ there exists $t\in W$ such that $d(u,t)\ne d(v,t)$, where $d(x,y)$ is the distance between vertices $x$ and $y$. The cardinality of a minimum resolving set for $G$ is called the metric dimension of $G$ and is denoted by ${dim}_M(G)$. A $k$-tree is a chordal graph all of whose maximal cliques are the same size $k+1$ and all of whose minimal clique separators are also all the same size $k$. A $k$-path is a $k$-tree with maximum degree $2k$, where for each integer $j$, $k\le j<2k$, there exists a unique pair of vertices, $u$ and $v$, such that $deg(u)=deg(v)=j$. In this paper, we prove that if $G$ is a $k$-path, then ${dim}_M(G)=k$. Moreover, we provide a characterization of all $2$-trees with metric dimension two.

Let $R$ be a commutative ring with identity and $A(R)$ be the set of ideals with nonzero annihilator. The strongly annihilating-ideal graph of $R$ is defined as the graph $\mathrm{\text{SAG}}(R)$ with the vertex set $A{(R)}^{\ast }=A(R)\backslash \{0\}$ and two distinct vertices $I$ and $J$ are adjacent if and only if $I\cap \mathrm{\text{Ann}}(J)\ne (0)$ and $J\cap \mathrm{\text{Ann}}(I)\ne (0)$. It is proved that $\mathrm{\text{SAG}}(R)$ is connected with diameter at most two and with girth at most four, if it contains a cycle. Moreover, we characterize all rings whose strongly annihilating-ideal graphs are complete or star. Furthermore, we study the affinity between strongly annihilating-ideal graph and annihilating-ideal graph (a well-known graph with the same vertices and two distinct vertices $I,J$ are adjacent if and only if $IJ=0$) associated with a commutative ring.