Discrete Mathematics, Algorithms and Applications

Let $T$ be a tree of given order $n$ with diameter $d$ and $\mu (T)$ the number of subtrees of $T$. In this paper, we show that:

(1)

(2) If $n\ge 8$ and $d=4$, then

(3) If $n\ge 6$, $d=5$ and $n\equiv r_i$ (mod $i$) for $i=2,3,6$ with $0\le r_i<i$, then

Let $G$ be a simple graph with $m$ edges and $H_1$, $H_2,\dots ,H_m$ be $m$ simple graphs. The generalized edge corona, denoted by $G{[H_i]}_1^m$, is the graph obtained by taking one copy of graphs $G$, $H_1$, $H_2,\dots ,H_m$ and then joining two end-vertices of the $i$th edge $e_i$ of $G$ to every vertex of $H_i$ for $1\le i\le m$. In this paper, we determine and study the characteristic polynomial, Laplacian polynomial and signless Laplacian polynomial of $G{[H_i]}_1^m$. As an application, we also count the number of spanning trees of the generalized edge corona.

Define a new class of graphs by cycles of length 5 or more always having adjacent chords. This is equivalent to cycles of length 5 or more always having noncrossing chords, which is a property that has a known forbidden induced subgraph characterization. Another characterization comes from viewing the graphs in this class in contrast to distance-hereditary graphs (which are characterized by cycles of length 5 or more always having crossing chords). Moreover, the graphs in the new class are those in which every edge of every cycle $C$ of length 5 or more forms a triangle with a third vertex of $C$ (generalizing that a graph is chordal if and only if every edge of every cycle $C$ of length 4 or more forms a triangle with a third vertex of $C$). This leads to a strategically-required subgraph characterization of the new class.

We provide a lightweight algorithm to express each of the elementary symmetric polynomials as a linear combination of (products of) power sum symmetric polynomials and, also, the power sums purely in terms of the elementary symmetric polynomials. Our method does not use Newton’s identities, which give such relations only implicitly. Each identity in the sequence is generated through a single differentiation.

For a connected labeled graph $G$, a spanning tree $T$ is a connected and acyclic subgraph that spans all vertices of $G$. In this paper, we consider a classical combinatorial problem which is to list all spanning trees of $G$. A Halin graph is a graph obtained from a tree with no degree two vertices and by joining all leaves with a cycle. We present a sequential and parallel algorithm to enumerate all spanning trees in Halin graphs. Our approach enumerates without repetitions and we make use of $O({(2pd)}^p)$ processors for parallel algorithmics, where $d$ and $p$ are the depth, the number of leaves, respectively, of the Halin graph. We also prove that the number of spanning trees in Halin graphs is $O({(2pd)}^p)$.

Let $G=(V(G),E(G))$ be a simple connected graph. The inverse sum indeg index of $G$, denoted by $\mathrm{\text{ISI}}(G)$, is defined as the sum of the weights $d(u)d(v)/[d(u)+d(v)]$ of all edges $uv$ of $G$, where $d(u)$ denotes the degree of a vertex in $G$. In this paper, we derive some bounds for the inverse sum indeg index in terms of some graph parameters, such as vertex (edge) connectivity, chromatic number, vertex bipartiteness, etc. The corresponding extremal graphs are characterized, respectively.

Let $G$ be a graph. A vertex coloring $\psi$ of $G$ is called $N_2$-vertex coloring if $|\psi (v)|\le 2$ for every vertex $v$ of $G$, where $\psi (v)$ is the set of colors of vertices adjacent to $v$. Let $t_2(G)$ be the maximum number of colors used in an $N_2$-vertex coloring of $G$. We provide some lower and upper bounds for $t_2(G)$ in terms of girth, diameter or size of $G$. Also, for every tree $T$, we obtain $t_2(T)$.

Let $G$ be a connected graph and $d(u,v)$ be the distance between the vertices $u$ and $v$ in $V(G)$. The diameter of $G$ is defined as ${max}_{u,v\in V(G)}d(u,v)$ and is denoted by $\mathrm{\text{diam}}(G)$. A subset of vertices $W=\{w_1,w_2,\dots ,w_k\}$ is called a resolving set for $G$ if for every two distinct vertices $u,v\in V(G)$, there is a vertex $w_i\in W$, $1\le i\le k$, such that $d(u,w_i)\ne d(v,w_i)$. A resolving set containing the minimum number of vertices is called a metric basis for $G$ and the number of vertices in a metric basis is its metric dimension, denoted by $\mathrm{\text{dim}}(G)$. Metric dimension is a generalization of affine dimension to arbitrary metric spaces (provided a resolving set exists).

Let ${ℱ}$ be a family of connected graphs $G_n:{ℱ}={(G_n)}_n\ge 1$ depending on $n$ as follows: the order $|V(G)|=\phi (n)$ and ${lim}_{n\to \infty }\phi (n)=\infty$. If there exists a constant $C>0$ such that $\mathrm{\text{dim}}(G_n)\le C$ for every $n\ge 1$ then we shall say that ${ℱ}$ has bounded metric dimension, otherwise ${ℱ}$ has unbounded metric dimension. If all graphs in ${ℱ}$ have the same metric dimension, then ${ℱ}$ is called a family of graphs with constant metric dimension.

In this paper, we study the metric properties of an infinite class of circulant graphs with three generators denoted by $C_n(1,2,k)$ for any positive integer $n\ge 11$ and when $k=5$. We compute the diameter and determine the exact value of the metric dimension of these circulant graphs.

A signed bad function of $G$ is a function $f:V(G)\to \{-1,1\}$ such that $f(N[v])\le 1$ for every $v\in V(G)$ where $N[v]$ is the closed neighborhood of $v$. The signed bad number is ${\beta }_s(G)=max\{{\sum }_{v\in V(G)}f(v)|f\mathrm{\text{is a signed bad function of}}G\}$. Ghameshlou et al. [A. N. Ghameshlou, A. Khodkar and S. M. Sheikholeslami, The signed bad numbers in graphs, Discrete Math. Algorithms Appl. 1 (2011) 33–41] proved that for any bipartite graph of order $n$, ${\beta }_s(G)\le n+2-2\lceil \sqrt{n+2}\rceil$. But their proof has a gap and the bound is not correct in general. In this note, we modify their proof and show that for any bipartite graph of order $n$, ${\beta }_s(G)\le n+6-2\sqrt{9+2n}$, and also we characterize the bipartite graphs attaining this bound.

In this paper, the concept of monophonic convexity is extended to weighted graphs. Set theoretic operations of monophonic convex sets and some of their properties are discussed. The notions of weighted monophonic block, weighted monophonic boundary and interior points are also studied and their characterizations are obtained.

A covering array $\text{CA}(N;t,k,v)$ is an $N\times k$ array such that every $N\times t$ subarray covers at least once each $t$-tuple from $v$ symbols. For given $t$, $k$, and $v$, the minimum number of rows for which exists a CA is denoted by $N=\text{CAN}(t,k,v)$ (CAN stands for Covering Array Number) and the corresponding CA is optimal. Optimal covering arrays have been determined algebraically for a small subset of cases; but another alternative to find CANs is the use of computational search. The present work introduces a new orderly algorithm to construct non-isomorphic covering arrays; this algorithm is an improvement of a previously reported algorithm for the same purpose. The construction of non-isomorphic covering arrays is used to prove the nonexistence of certain covering arrays whose nonexistence implies the optimality of other covering arrays. From the computational results obtained, the following CANs were established: $\text{CAN}(2,k,3)=15$ for $11\le k\le 20$, $\text{CAN}(2,7,4)=21$, and $\text{CAN}(2,5,6)=39$. In addition, the new result $\text{CAN}(2,13,3)=15$, and the already known existence of $\text{CA}(45;3,14,3)$, imply $\text{CAN}(3,14,3)=45$.

A set $D\subseteq V(G)$ is a $2$-point set dominating set (2-psd set) of a graph $G$ if for any subset $S\subseteq V-D$, there exists a nonempty subset $T\subseteq D$ containing at most two vertices such that the subgraph $〈S\cup T〉$ induced by $S\cup T$ is connected. The $2$-point set domination number of $G$, denoted by ${\gamma }_{2\mathrm{\text{ps}}}(G)$, is the minimum cardinality of a 2-psd set of $G$. In this paper, we determine the lower bounds and an upper bound on ${\gamma }_{2\mathrm{\text{ps}}}(G)$ of a graph. We also characterize extremal graphs for the lower bounds and identify some well-known classes of both separable and nonseparable graphs attaining the upper bound.

Let $R$ be a commutative ring with identity and ${𝔘}_R$ be the set of all non-zero non-units of $R$. The co-annihilating graph of $R$, denoted by ${{𝒞}{𝒜}}_R$, is a graph with vertex set ${𝔘}_R$ and two vertices $a$ and $b$ are adjacent whenever $\mathrm{\text{Ann}}(a)\cap \mathrm{\text{Ann}}(b)=(0)$. In this paper, we initiate the study of the co-annihilating graph of a commutative ring and we investigate its properties.

A proper vertex coloring of $G$ is acyclic if $G$ contains no bicolored cycle. Namely, every cycle of $G$ must be colored with at least three colors. $G$ is acyclically $L$-colorable if for a given list assignment $L=\{L(v):v\in V\}$, there exists an acyclic coloring $\pi$ of $G$ such that $\pi (v)\in L(v)$ for all $v\in V$. If $G$ is acyclically $L$-colorable for any list assignment with $|L(v)|\ge k$ for all $v\in V$, then $G$ is acyclically $k$-choosable.

In this paper, we prove that planar graphs without intersecting $5^{-}$-cycles are acyclically $4$-choosable. This provides a sufficient condition for planar graphs to be acyclically 4-choosable and also strengthens a result in [M. Montassier, A. Raspaud and W. Wang, Acyclic 4-choosability of planar graphs without cycles of specific lengths, in Topics in Discrete Mathematics, Algorithms and Combinatorics, Vol. 26 (Springer, Berlin, 2006), pp. 473–491] which says that planar graphs without $4$-, $5$-cycles and intersecting 3-cycles are acyclically 4-choosable.