Discrete Mathematics, Algorithms and Applications

The traveling salesman problem (TSP) involves determining the shortest length (optimal tour) for a complete circuit through an arbitrary number of points. In the special case that the points to be visited are randomly distributed in the plane within a unit square, and travel costs correspond to the Euclidean distance between points, it is known that the length of the optimal tour divided by the square root of the number of points ($n$) asymptotically approaches a constant (${\beta }_{\mathrm{\text{TSP}}})$ as $n$ becomes large. If individual points are randomly drawn from a uniform distribution, the optimal lengths for a sufficiently large number of TSP instances of the same size ($n)$ comprise a normal distribution whose mean approaches ${\beta }_{\mathrm{\text{TSP}}}$ as $n$ increases. Moreover, as $n$ approaches infinity, this distribution gradually narrows such that its standard deviation asymptotically approaches zero. Although the precise value of ${\beta }_{\mathrm{\text{TSP}}}$ is unknown, published studies indicate its magnitude is approximately 0.712. In this paper, possibly for the first time, precise formulae are proposed for the parameters of the underlying normal distribution and ${\beta }_{\mathrm{\text{TSP}}}$, based on intuition, mathematical reasoning, and empirical fits to both published and experimentally derived data.

A 2-distance coloring of a graph is a proper $k$-coloring in which any two vertices with distance at most two get different colors. The 2-distance number is the smallest number $k$ such that $G$ has a 2-distance $k$-coloring, denoted as ${\chi }_2(G)$. In 1977, Wegner conjectured that for each planar graph $G$ with maximum degree $\mathrm{\Delta }$, ${\chi }_2(G)\le 7$ if $\mathrm{\Delta }\le 3$, ${\chi }_2(G)\le \mathrm{\Delta }+5$ if $4\le \mathrm{\Delta }\le 7$, and ${\chi }_2(G)\le \lfloor \frac{3\mathrm{\Delta }}{2}\rfloor +1$ if $\mathrm{\Delta }\ge 8$. In 2001, Thomassen supported the conjecture by proving the case $\mathrm{\Delta }=3$. The conjecture is still open even for $\mathrm{\Delta }=4$. In this paper, we show that ${\chi }_2(G)\le 17$ for the case $\mathrm{\Delta }\le 5$ which improves the upper bound 18 recently obtained by Hou et al.

Luo, Tian and Wu [Discrete Math. 345(4) (2022) 112788] conjectured that for any tree $T$ with bipartition $(X,Y)$, every $k$-connected bipartite graph $G$ with minimum degree at least $k+w$, where $w=max\{|X|,|Y|\}$, contains a tree $T^{\prime }\cong T$ such that $\kappa (G-V(T^{\prime }))\ge k$. In the paper, we confirm the conjecture when $T$ is an odd path on $m$ vertices. We remind that Yang and Tian [Proof of a conjecture on connectivity keeping odd paths in k-connected bipartite graphs, arXiv:2209.08373v2] also prove the same result by a different way.

A conjugate skew gain graph is a skew gain graph with the labels (also called, the conjugate skew gains) from the field of complex numbers on the oriented edges such that they get conjugated when we reverse the orientation. In this paper, we introduce distance matrices for conjugate skew gain graphs and characterize balanced conjugate skew gain graphs using these matrices. We provide explicit formulae for the distance spectra of certain conjugate skew gain graphs.

The idea of a fault-tolerant metric dimension can be used in chemistry to examine a molecule’s structural resistance to the failure of particular atoms or chemical bonds. This is especially important when creating molecules for specific uses, like drug candidates, as they may be exposed to biological systems or the environment, which could cause certain atoms or bonds to change or break. One such is the dialkyltin complex, which has two alkyl groups joined to a tin atom. The nitrogen atom of an N-salicylidene-L-valine molecule is coupled to the alkyl groups in the dialkyltin complex-1 of N-salicylidene-L-valine, making it a useful catalyst for numerous processes in organic synthesis. The purpose of this study is to identify the fault-tolerant metric dimension of the chain in N-salicylidene-L-valine dialkyltin complex-3.

In this paper, we consider a tree-like recursion procedure of solving of binary decomposable problems. More specifically, we study some questions of parallelization of this procedure with using of shared round memory. We consider two parallelization schemes for parallel solving of binary decomposable problems by tree-like recursion procedures on a parallel computing system with shared round memory. We call these schemes the TAN-scheme and the TON-scheme of parallelization. We compare the efficiency of these schemes, using different parameters of parallelization. Based on this comparative analysis, we conclude the TON-scheme to be more effective.

Let G be a graph with a set of V vertices and a set of E edges. A function $f:V\to [0,1]$ is called a restrained dominating function (RDF) of G if, for every $v\in V,$ $f(N[v])={\sum }_{u\in N[v]}(deg(u)-1)f(u)\ge 1$. A restrained dominating function f of a graph G is called minimal (MRDF) if, for all functions $g:V\to [0,1]$ such that $g<f$ and g(v) $\ne$ f(v) for at least one $v\in V,$ g is not a RDF. The fractional restrained domination number ${\gamma }_{fr}(G)$ is defined as follows: ${\gamma }_{fr}(G)=min\{|f|$: f is an MRDF of G$\}$ where $\left|f\right|={\sum }_{u\in v}f(v)$.

In this paper, we introduced the notion of hyper $L$-algebras as a generalization of $L$-algebras. We studied basic properties of them and investigated the relationship among hyper $L$-algebras and some other hyper logical algebras such as hyper ($K$,BCI) BCK-algebras and hyper hoops. In the following, we defined the notions of (weak) hyper ideals in hyper $L$-algebras and then by considering the congruence relation (relative to a hyper ideal) on the hyper $L$-algebra, we constructed the quotient hyper $L$-algebras and investigated some properties of them.

Graph operations play a significant role in constructing new and valuable graphs and capturing intermolecular forces between atoms and bonds of a molecule. In mathematical chemistry and chemical graph theory, a topological invariant is a numeric value extracted from the molecular graph of a chemical compound using a mathematical formula involving vertex degrees, distance, spectrum, and their combination. An intriguing problem in chemical graph theory is figuring out the lower and the upper bound on pertinent topological indices among a particular family of graphs. The first Gourava index for a graph $\mathrm{\Gamma }$ is denoted and defined as ${\mathrm{\text{GO}}}_1(\mathrm{\Gamma })={\sum }_{xy\in E(\mathrm{\Gamma })}[{𝔡}_{\mathrm{\Gamma }}(x)+{𝔡}_{\mathrm{\Gamma }}(y)+{𝔡}_{\mathrm{\Gamma }}(x){𝔡}_{\mathrm{\Gamma }}(y)].$ Recently, Kulli studied and derived formulas of the first Gourava index for four graph operations. We proved with the help of counter-examples that the results provided by Kulli produce inaccurate values when compared with exact values. In this paper, we determined the exact formulas and bounds of the first Gourava index for $\mathrm{\Psi }$-sum graphs. Besides, we presented diverse examples to support our results.

Let ${\mathbb{Z}}_n$ be the ring of integer modulo $n$ with two binary operators, addition $(+)$ and multiplication $(.)$, where $n$ is a positive integer. The special set ${𝒮}$ is defined as ${𝒮}=\{a\in {\mathbb{Z}}_n:(\exists b\in {\mathbb{Z}}_n)ba\equiv a,b\not\equiv a,b\not\equiv 1\}$. Our purpose in the present paper is to propose a new family of interconnection networks that are Cayley graphs on this special set ${𝒮}$ and denote it by ${\mathrm{\Omega }}^{-}(Z_n)$. In this paper, we define a relationship between $G$ and $G_e^{\ast }$, $G_e^{\ast }$ is a derived graph from $G$ by removing $r$ edges, where $r$ is a known fixed value. We also give the spectrum of absorption Cayley graph, unitary addition Cayley graph, and ${\mathrm{\Omega }}^{-}(Z_n)$. We also provide values of $n$ for which the graph ${\mathrm{\Omega }}^{-}({\mathbb{Z}}_n)$ is hyperenergetic and discuss the structural properties of this graph, such as planarity and connectedness.

For a graph $G$, let $i_k(G)$ be the number of independent sets of size $k$ in $G$. The independence polynomial $I(G;x)={\sum }_{k\ge 0}{i}_k(G)x^k$ has been the focus of considerable research. In this paper, using the coefficients of independence polynomials, we order graphs with some given parameters. We first determine the extremal graph whose all coefficients of $I(G;x)$ are the largest (respectively, smallest) among all connected graphs (respectively, bipartite graphs) with given vertex cover number. Then we also derive the extremal graph whose all coefficients of $I(G;x)$ are the largest among all connected graphs (respectively, bipartite graphs) with given vertex dominate number.

Let $G$ be a group. Then the order two element graph of $G$ is the simple undirected graph whose vertex set consists of all elements of $G$ and two distinct vertices $u,v$ are adjacent if and only if either $uvorvu\in \{t^2:t\in G\}\cup \{a\in G:a^2=e\}\setminus \{e\}$, where $e$ is the identity element of $G$. This graph is denoted by ${𝕊}_2(G)$. In this paper, we first establish some beautiful results on Merrifield–Simmons index of order two element graph over a group. After that we characterize the product of two order two element graph over two groups. Moreover we study some important results on domination number of order two element graph over a group.

A radio labeling of a graph $G$ is a function $f:V(G)\to \{0,1,2,\dots \}$ such that $|f(u)-f(v)|\ge \mathrm{\text{diam}}(G)+1-d(u,v)$ for every pair of distinct vertices $u,v$ of $G$. The radio number of $G$, denoted by $\mathrm{\text{rn}}(G)$, is the smallest number $k$ such that $G$ has radio labeling $f$ with max$\{f(v):v\in V(G)\}$ = $k$. In this paper, we give a lower bound for the radio number for the Cartesian product of the generalized Petersen graph and tree. We present two necessary and sufficient conditions, and three other sufficient conditions to achieve the lower bound. Using these results, we determine the radio number for the Cartesian product of the Peterson graph and stars.

The harmonic index of graph $G$ is the value $H(G)={\sum }_{uv\in E(G)}\frac{2}{d_u+d_v}$, where $d_x$ refers to the degree of $x$. Zhong [The harmonic index for graphs, Appl. Math. Lett. 25 (2012) 561–566] proved that $H(T)\ge \frac{2(n-1)}{n}$ for any tree $T$ of order $n$. As a results of Ali, Raza and Bhatti [Some vertex-degree-based topological indices of cacti, Ars Combin. 144 (2019) 195–206], it can be shown that $H(T)\ge \frac{2(n-1)}{\ell +1}$ for any tree $T$ of order $n$ with $\ell$ leaves, where $3\le \ell \le n-2$. In this paper, we generalize this lower bound for all cactus graphs. We present a lower bound for the harmonic index of cactus graphs $G$ in terms of the order, the number of leaves and the number of cycles, and characterize all cactus graphs achieving equality for the given bound.

The $k$-$2$-distance coloring of the graph $G$ refers to that it satisfies the mapping: $\varphi :V(G)\to \{1,2,\dots ,k\}$, such that the vertex $u$ and $v$, whose distance is at most $2$, receive different colors, namely $\varphi (u)\ne \varphi (v)$. Denote ${\chi }_2^l(G)=\mathrm{\text{min}}\{k|G\mathrm{\text{has a list}}k\text{-}2\text{-}distancecoloring\}$, which is a list 2-distance chromatic number of the graph $G$. This paper proves that ${\chi }_2^l(G)\le \mathrm{\Delta }+5$ for the graph $G$ without 3-cycles and intersecting 4-cycles and $\mathrm{\Delta }\ge 24$.

A bijective product square $k$-cordial labeling of a graph $G$ with vertex set $V$ and edge set $E$ is a bijection $f$ from $V(G)$ to $\{1,2,\dots ,|V(G)|\}$ such that the induced edge function $f^{\ast }$ from $E(G)$ to $S_k=\{i^2(\mathrm{\text{mod}}k),0\le i\le k-1\}$ defined as $f^{\ast }(uv)\equiv {(f(u)f(v))}^2(\mathrm{\text{mod}}k)$ for every edge $uv\in E(G)$ satisfies the following condition. (i) If $e_f^{\ast }(i)$ is the number of edges labeled with $i$ under $f^{\ast }$, then $|e_f^{\ast }(i)-e_f^{\ast }(j)|\le 1$ where $i,j\in S_k$. A graph which admits a bijective product square $k$-cordial labeling is called bijective product square $k$-cordial graph. In this paper, we find upper limit of the size of the bijective product square $k$-cordial graph for $k=3$ and $5$. Also, we prove that every graph is a subgraph of a connected bijective product square $k$-cordial graph for all odd prime $k$. In addition, we establish the relation between bijective product square $k$-cordial and $k$-product cordial graphs.

Let $G=(V,E)$ be a graph with vertex set $V$ and edge set $E.$ A subset $D$ of $V$ is called a dominating set of $G$ if for any $v$ in $V-D,$ there exists a vertex $u\in D$ such that $u$ and $v$ are adjacent. The minimum cardinality of a dominating set of $G$ is called the domination number of $G$ and is denoted by $\gamma (G).$ Several domination parameters have been introduced. Among them, point set domination was conceived by Sampathkumar and Pushpa Latha [E. Sampathkumar and L. Pushpa Latha, Point-set domination number of a graph, Indian J. Pure Appl. Math. 24(4) (1993) 225–229]. A subset $D$ of $V(G)$ is called a point set dominating set of $G$ if for every subset $T$ of $V-D,$ there exists a vertex $u\in D$ such that $T\cup \{u\}$ is connected in $G.$ The minimum cardinality of a point set dominating set of $G$ is called the point set domination number of $G$ and is denoted by ${\gamma }_p(G).$ Kulli [V. R. Kulli, The Maximal Domination Number of a Graph, Graph Theory Notes of New York XXXIII (Academy of Sciences, 1997), pp. 11–13] introduced the concept of maximal domination number in a graph. A subset $D$ of $V(G)$ is called a maximal dominating set of $G$ if $D$ is a dominating set of $G$ and $V-D$ is not a dominating set of $G.$ The minimum cardinality of a maximal dominating set of $G$ is denoted by ${\gamma }_m(G).$ In this paper, the concept of maximal domination is combined with point set domination and maximal point set domination is studied.

Generalized hypercube network is an interconnection network topology. The topology of interconnection network usually takes graph as a mathematical model, in which the vertex of graph represents the server and the edge of graph represents the connection between servers. As vertex count increases, the vertex degree of hypercube network increases as well. This has advantages, such as increased performance and reliability. The domination parameters are an important basis for analyzing and measuring the reliability of interconnection networks. In this paper, few properties of generalized hypercube network and Roman detour domination number for minimum dimensional generalized hypercube networks and hypercube networks are discussed. And also we determine the bounds for ${\gamma }_{\mathrm{\text{Rd}}}(Q(d_1,d_2,\dots ,d_n))$ and ${\gamma }_{\mathrm{\text{Rd}}}(Q_n)$.