Discrete Mathematics, Algorithms and Applications

Let $G$ be a connected graph of order $n$ and let $\mathrm{\text{RD}}(G)$ be the reciprocal distance matrix (also called Harary matrix) of the graph $G$. Let ${\rho }_1\ge {\rho }_2\ge \cdots \ge {\rho }_n$ be the eigenvalues of the reciprocal distance matrix $\mathrm{\text{RD}}(G)$ of the connected graph $G$ called the reciprocal distance eigenvalues of $G$. The Harary energy $\mathrm{\text{HE}}(G)$ of a connected graph $G$ is defined as sum of the absolute values of the reciprocal distance eigenvalues of $G$, that is, $\mathrm{\text{HE}}(G)={\sum }_{i=1}^n\left|{\rho }_i\right|.$ In this paper, we establish some new lower and upper bounds for $\mathrm{\text{HE}}(G),$ in terms of different graph parameters associated with the structure of the graph $G$. We characterize the extremal graphs attaining these bounds. We also obtain a relation between the Harary energy and the sum of $k$ largest adjacency eigenvalues of a connected graph.

For any integer $k\ge 1$, a minus total $k$-dominating function is a function $f:V(G)\to \{-1,0,1\}$ satisfying ${\sum }_{w\in N(v)}f(w)\ge k$ for every $v\in V(G)$, where $N(v)=\{u\in V(G)|uv\in E(G)\}$. The minimum of the values of ${\sum }_{v\in V(G)}f(v)$, taken over all minus total $k$-dominating functions $f$, is called the minus total $k$-domination number and is denoted by ${\gamma }_{tk}^{-}(G)$. In this paper, we initiate the study of minus total $k$-domination in graphs, and we present different sharp bounds on ${\gamma }_{tk}^{-}(G)$. In addition, we determine the minus total $k$-domination number of some classes of graphs. Some of our results are extensions of known properties of the minus total domination number ${\gamma }_t^{-}(G)={\gamma }_{t1}^{-}(G)$.

A signed graph is a pair $(G,\sigma )$, where $G$ is a graph and $\sigma :E(G)\to \{1,-1\}$ is a signature of $G$. A set $S$ of integers is symmetric if $i\in S$ implies that $-i\in S$. Given a list assignment $L$ of $G$, an $L$-coloring of a signed graph $(G,\sigma )$ is a coloring $f$ of $(G,\sigma )$ such that $f(v)\in L(v)$ for each $v\in V(G)$ and $f(u)\ne \sigma (uv)f(v)$ for every edge $uv\in E(G)$. The signed choice number ${\mathrm{\text{ch}}}_{\pm }(G)$ of a graph $G$ is defined to be the minimum integer $k$ such that for any $k$-list assignment $L$ of $G$ and for any signature $\sigma$ on $G$, there is a proper $L$-coloring of $(G,\sigma )$.

List signed coloring is a generalization of list coloring. However, the difference between signed choice number and choice number can be arbitrarily large. Hu and Wu [Planar graphs without intersecting $5$-cycles are $4$-choosable, Discrete Math. 340 (2017) 1788–1792] showed that every planar graph without intersecting 5-cycles is 4-choosable. In this paper, we prove that ${\mathrm{\text{ch}}}_{\pm }(G)\le 4$ if $G$ is a planar graph without intersecting 5-cycles, which extends the main result of [D. Hu and J. Wu, Planar graphs without intersecting $5$-cycles are $4$-choosable, Discrete Math. 340 (2017) 1788–1792].

Goldbach’s conjecture is one of the oldest and famous unproved problems in number theory. Using a deep learning model, we obtain an approximation of the Goldbach partition function, which counts the number of ways of representing an even number greater than 4 as a sum of two primes. We use residues of number modulo first 25 primes as features and archive a more accurate approximation, which reduces error rate from $3.0\%$ to $0.6\%$.

The sum-connectivity index of a graph $G$ is defined as the sum of weights $1/\sqrt{d_u+d_v}$ over all edges $uv$ of $G$, where $d_u$ and $d_v$ are the degrees of the vertices $u$ and $v$ in $G$, respectively. In this paper, some extremal problems on the sum-connectivity index of trees are studied. The extremal values on the sum-connectivity index of trees with given graphic parameters, such as pendant number, matching number, domination number and diameter, are determined. The corresponding extremal graphs are characterized, respectively.

In this paper, we introduce and study a new coloring problem of graphs called the double total dominator coloring. A double total dominator coloring of a graph $G$ with minimum degree at least 2 is a proper vertex coloring of $G$ such that each vertex has to dominate at least two color classes. The minimum number of colors among all double total dominator coloring of $G$ is called the double total dominator chromatic number, denoted by ${\chi }_{dd}^t(G)$. Therefore, we establish the close relationship between the double total dominator chromatic number ${\chi }_{dd}^t(G)$ and the double total domination number ${\gamma }_{\times 2,t}(G)$. We prove the NP-completeness of the problem. We also examine the effects on ${\chi }_{dd}^t(G)$ when $G$ is modified by some operations. Finally, we discuss the ${\chi }_{dd}^t(G)$ number of square of trees by giving some bounds.

Let $G$ be an orientation of a simple graph $G$ with $n$ vertices and $m$ edges. The skew Laplacian matrix $\mathrm{\text{SL}}(G)$ of the digraph $G$ is defined as $\mathrm{\text{SL}}(G)=\tilde{D}(G)-iS(G)$, where $i=\sqrt{-1}$ is the imaginary unit, $\tilde{D}(G)$ is the diagonal matrix with oriented degrees ${\alpha }_i=d_i^{+}-d_i^{-}$ as diagonal entries and $S(G)$ is the skew matrix of the digraph $G$. The largest eigenvalue of the matrix $\mathrm{\text{SL}}(G)$ is called skew Laplacian spectral radius of the digraph $G$. In this paper, we study the skew Laplacian spectral radius of the digraph $G$. We obtain some sharp lower and upper bounds for the skew Laplacian spectral radius of a digraph $G$, in terms of different structural parameters of the digraph and the underlying graph. We characterize the extremal digraphs attaining these bounds in some cases. Further, we end the paper with some problems for the future research in this direction.

A simple graph $G=(V(G),E(G))$ admits an $H$-covering if every edge in $E(G)$ belongs to at least one subgraph of $G$ isomorphic to a given graph $H$. The graph $G$ admits an $H$-irregular total $k$-labeling $f:V(G)\cup E(G)\to \{1,2,\dots ,k\}$ if $G$ admits an $H$-covering and for every two different subgraphs $H^{\prime }$ and $H^{″}$ isomorphic to $H$, there is ${\mathrm{\text{wt}}}_f(H^{\prime })\ne {\mathrm{\text{wt}}}_f(H^{″})$, where ${\mathrm{\text{wt}}}_f(H)={\sum }_{v\in V(H)}f(v)+{\sum }_{e\in E(H)}f(e)$ is the associated $H$-weight. The total $H$-irregularity strength of $G$ is $\mathrm{\text{ths}}(G,H)=min\{k:G\text{ has}\text{ an }H\text{-irregular total }k\text{-labeling}\}$.

In this paper, we give the exact values of $\mathrm{\text{ths}}(C_n,P_m)$, where $m\in \{3,\frac{n}{2},\frac{n}{2}+1,n\}$. For the versions edge and vertex $H$-irregularity strength $\mathrm{\text{ehs}}$ and $\mathrm{\text{vhs}}$, respectively, we determine the exact values of $\mathrm{\text{ehs}}({\mathrm{\text{Br}}}_n,C_3)$, $\mathrm{\text{ehs}}({\mathrm{\text{Br}}}_n,{\mathrm{\text{Br}}}_m)$ and $\mathrm{\text{vhs}}({\mathrm{\text{Br}}}_n,{\mathrm{\text{Br}}}_m)$, where ${\mathrm{\text{Br}}}_n$ is the diamond graph.

Global dominator coloring of the graph $G$ is the proper coloring of $G$ such that every vertex of $G$ dominates atleast one color class as well as anti-dominates atleast one color class. The minimum number of colors required for global dominator coloring of $G$ is called global dominator chromatic number of $G$ denoted by ${\chi }_{\mathrm{\text{gd}}}(G)$. In this paper, we characterize trees $T$ of order $n$ $(n\ge 6)$ such that ${\chi }_{\mathrm{\text{gd}}}(T)=\lfloor \frac{n}{2}\rfloor +2$ and also establish a strict upper bound for ${\chi }_{\mathrm{\text{gd}}}(T)$ for a tree of even order $n$ $(n\ge 6)$. We construct some family of graphs $G$ with ${\chi }_{\mathrm{\text{gd}}}(G)=4$ and prove some results on ${\chi }_{\mathrm{\text{gd}}}$-partitions of $G$ when ${\chi }_{\mathrm{\text{gd}}}(G)=4$.

A matrix with entries $0,1$ is graphical if it is symmetric and all its diagonal entries are zero. Let $G_1$, $G_2$ and $G_3$ be graphs defined on the same set of vertices. The graph $G_3$ is said to be the matrix product of graphs $G_1$ and $G_2$, if $A(G_1)A(G_2)=A(G_3)$, where $A(G_i)$ is the adjacency matrix of the graph $G_i,1\le i\le 3$. In such a case, we say that $G_1$ and $G_2$ are companions of each other. The main purpose of this paper is to design an algorithm to check whether a given graph $G$ has a companion. We derive conditions on $n$ and $m$ so that the generalized wheel graph, denoted by $W_{m,n}$, has a companion and also show that the $m$th power of the path graph $P_n$ has no companion. Finally, we indicate a possible application of the algorithm in a problem of coloring of edges of the complete graph $K_n$.

Let $C$ be a set of $n$ customers and $F$ be a set of $m$ facilities. An $r$-gather clustering of $C$ is a partition of the customers in clusters such that each cluster contains at least $r$ customers. The $r$-gather clustering problem asks to find an $r$-gather clustering which minimizes the maximum distance between a pair of customers in a cluster. An $r$-gathering of $C$ to $F$ is an assignment of each customer $c\in C$ to a facility $f\in F$ such that each facility has zero or at least $r$ customers. The $r$-gathering problem asks to find an $r$-gathering that minimizes the maximum distance between a customer and his/her facility. In this work, we consider the $r$-gather clustering and $r$-gathering problems when the customers and the facilities are lying on a “star”. We show that the $r$-gather clustering problem and the $r$-gathering problem with customers and facilities on a star with $d$ rays can be solved in $O(n+d^d{r}^{d}drlogd)$ and $O(n+m+(d+logm)d^4{r}^2+d^d{r}^d{2}^{d}drlogd)$ time, respectively. Furthermore, we prove the hardness of a variant of the $r$-gathering problem, called the min-max-sum $r$-gathering problem, even when the customers and the facilities are on a star. We also study the $r$-gathering problem when the customers and the facilities are on a line, and each customer location is uncertain. We show that the $r$-gathering problem can be solved in $O(nk+mnlogn+(m+nlogkn+n{r}^{\frac{n}{r}})logmn)$ and $O(mnlogn+(nlogn+m)logmn)$ time when the customers and the facilities are on a line, and the customer locations are given by piecewise uniform functions of at most $k+1$ pieces and “well-separated” uniform distribution functions, respectively.

Let $R$ be a commutative ring with identity, $n\ge 2$ be a positive integer and $M_n(R)$ be the set of all $n\times n$ matrices over $R.$ For a matrix $A\in M_n(R),$ Tr$(A)$ is the trace of $A.$ The trace graph of the matrix ring $M_n(R),$ denoted by ${\mathrm{\Gamma }}_t(M_n(R)),$ is the simple undirected graph with vertex set $\{A\in M_n{(R)}^{\ast }:\text{there exists }B\in M_n{(R)}^{\ast }$$\text{ such that Tr}(AB)=0\}$ and two distinct vertices $A$ and $B$ are adjacent if and only if Tr$(AB)=0.$ The ideal-based trace graph of the matrix ring $M_n(R)$ with respect to an ideal $I$ of $R,$ denoted by ${\mathrm{\Gamma }}_{I^t}(M_n(R)),$ is the simple undirected graph with vertex set $M_n(R)\setminus M_n(I)$ and two distinct vertices $A$ and $B$ are adjacent if and only if Tr$(AB)\in I.$ In this paper, we investigate some properties and structure of ${\mathrm{\Gamma }}_{I^t}(M_n(R)).$ Further, it is proved that both ${\mathrm{\Gamma }}_t(M_n(R))$ and ${\mathrm{\Gamma }}_{I^t}(M_n(R))$ are Hamiltonian.

For a connected graph $G=(V,E)$, a set $S$ subset of $V(G)$ is said to be a geodetic set if all vertices in G should lie in some $u-v$ geodesic for some $u,v\in S$. The minimum cardinality of the geodetic set is the geodetic number. In this paper, the authors discussed the geodetic number, geodetic domination number, and the restrained geodetic domination of the edge subdivision graph.

This paper is a continuation of ideas presented in [M. B. Safari, B. Davvaz and V. Leoreanu-Fotea, Enumeration of 3- and 4-hypergroups on sets with two elements, Eur. J. Combin. 44 (2015) 298–306]. We find the number and structure of non-isomorphism $5$-hypergroups on sets with two elements. Moreover, we present a general template for some special cases of $n$-hypergroups by linking the last results on $n$-hypergroups.

Let $G=(V,E)$ be a connected graph. A function $f:V\to \{0,1,2\}$ is called a Roman dominating function if every vertex $v$ with $f(v)=0$ is adjacent to a vertex $u$ with $f(u)=2$. If further the set $V_0=\{v:f(v)=0\}$ is an independent set, then $f$ is called an outer independent Roman dominating function (OIRDF). Let $w(f)={\sum }_{v\in V}f(v)$ and ${\gamma }_{\mathrm{\text{oiR}}}(G)=\mathrm{\text{min}}\{w(f):f\text{ is an OIRDF of }G\}$. Then ${\gamma }_{oiR}(G)$ is called the outer independent Roman domination number of $G$. In this paper, we prove that the decision problem for ${\gamma }_{oiR}(G)$ is NP-complete for chordal graphs. We also show that ${\gamma }_{oiR}(G)$ is linear time solvable for threshold graphs and bounded tree width graphs. Moreover, we show that the domination and outer independent Roman domination problems are not equivalent in computational complexity aspects.

In this paper, we investigate the crosscap of 3-annihilating-ideal hypergraph ${{𝒜}{𝒢}}_3(R)$ of a commutative ring $R$ and the topological embedding of ${{𝒜}{𝒢}}_3(R)$ to the nonorientable compact surfaces. Furthermore, we determine all Artinian commutative non-local rings R (up to isomorphism) such that ${{𝒜}{𝒢}}_3(R)$ is a projective graph.

Let $f:V\to \{0,1,2\}$ be a function on a graph $G=(V,E)$. A vertex $v$ with $f(v)=0$ is said to be undefended with respect to $f$ if it is not adjacent to a vertex $u$ with $f(u)>0$. A function $f$ is called a weak Roman dominating function (WRDF) if each vertex $v$ with $f(v)=0$ is adjacent to a vertex $u$ with $f(u)>0$, such that the function $f^{\prime }$ defined by $f^{\prime }(v)=1$, $f^{\prime }(u)=f(u)-1$ and $f^{\prime }(w)=f(w)$ for all $w\in V\setminus \{v,u\}$, has no undefended vertex. The weight of a WRDF is the sum of its function values over all vertices, and the weak Roman domination number ${\gamma }_r(G)$ is the minimum weight of a WRDF in $G$. In this paper, we consider the effects of edge deletion on the weak Roman domination number of a graph. We show that the deletion of an edge of $G$ can increase the weak Roman domination number by at most 1. Then we give a necessary condition for ${\gamma }_r$-ER-critical graphs, that is, graphs $G$ whose weak Roman domination number increases by the deletion of any edge. Restricted to the class of trees, we provide a constructive characterization of all ${\gamma }_r$-ER-critical trees.

Let $C_k(M)$ be the $k$th-order circuit graph of a simple connected matroid M. The first-order circuit graph is also called a circuit graph. There are lots of results about connectivity and Hamiltonian properties of circuit graph of matroid, while there are few related results on the second-order circuit graph of a matroid. This paper mainly focuses on the connectivity and Hamiltonian properties of the second-order circuit graphs of the cycle matroid of wheels. It determines the minimum degree and connectivity of these graphs, and proves that the second-order circuit graph of the cycle matroid of a wheel is uniformly Hamiltonian.