Open Journal of Discrete Applied Mathematics (ODAM)

Abstract: Shadi I.K et al. [1] introduced the edge hub number of graphs. This work extends the concept to fuzzy graphs. We derive several properties of edge hub number of fuzzy graphs and establish some relations that connect the new parameter with other fuzzy graph parameters. Also, some bounds of such a parameter are investigated. Moreover, we provide empirical evidence examples to elucidate the behavior and implications of edge hub number of fuzzy graph parameters.

Abstract: In this paper, we give a relationship between the covering number of a simple graph \(G\), \(\beta(G)\), and a new parameter associated to \(G\), which is called 2-degree-packing number of \(G\), \(\nu_2(G)\). We prove that \[\lceil \nu_{2}(G)/2\rceil\leq\beta(G)\leq\nu_2(G)-1,\] for any simple graph \(G\), with \(|E(G)|>\nu_2(G)\). Also, we give a characterization of connected graphs that attain the equalities.

Abstract: Let \(A\) and \(B\) be two graph and \(P(A,z)\) and \(P(B,z)\) are their chromatic polynomial, respectively. The two graphs \(A\) and \(B\) are said to be chromatic equivalent denoted by \( A \sim B \) if \(P(A,z)=P(B,z)\). A graph \(A\) is said to be chromatically unique(or simply \(\chi\)- unique) if for any graph \(B\) such that \(A\sim B \), we have \(A\cong B\), that is \(A\) is isomorphic to \(B\). In this paper, the chromatic uniqueness of a new family of \(6\)-bridge graph \(\theta(r,r,s,s,t,u)\) where \(2\leq r\leq s \leq t\leq u\) is investigated.

Abstract: In mathematical chemistry, a large number of topological indices are used to predict the physicochemical properties of compounds, especially in the study of quantitative structure-proerty relationship (QSPR).
However, many topological indices have almost the same predictive ability. In this paper, we focus on how to use fewer topological indices to predict the physicochemical properties of compounds through the QSPR analysis of connectivity indices of benzene hydrocarbons.

Abstract: In this paper, we obtain the bounds for the Laplacian eigenvalues of a weighted graph using traces. Then, we find the bounds for the Kirchhoff and Laplacian Estrada indices of a weighted graph. Finally, we define the Laplacian energy of a weighted graph and get the upper bound for this energy.

Abstract: A number of results on claw-free, paw-free graphs have been presented in the literature. Although the proofs of such results are elegant, sound and valid, it has gone unnoticed that all the results about claw-free, paw-free graphs in the literature are a consequence of a result by Olariu [1]. The note, apart from covering the aforementioned gap, also provides an alternate proof to a result by Faudree and Gould found in [2] in that, an unnoticed consequence resulted in the characterization of claw-free, paw-free graphs.

Abstract: A graph \(G\) is said to be super edge-magic if there exists a bijective function \(f:V\left(G\right) \cup E\left(G\right)\rightarrow \left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert +\left\vert E\left( G\right) \right\vert \right\}\) such that \(f\left(V \left(G\right)\right) =\left\{1, 2, \ldots , \left\vert V\left( G\right) \right\vert \right\}\) and \(f\left(u\right) + f\left(v\right) + f\left(uv\right)\) is a constant for each \(uv\in E\left( G\right)\). In this paper, we study the super edge-magicness of graphs of order \(n\) with degree sequence \(s:4, 2, 2, \ldots, 2\). We also investigate the super edge-magic properties of certain families of graphs. This leads us to propose some open problems.

Abstract: Coronoids are nice chemical structures that may be represented mathematically in the planar hexagonal lattice. They have been well-studied both for their chemical properties and also their enumerative aspects. Typical approaches to the latter type of questions often include classification and algorithmic techniques. Here we study one simple class of coronoids called hollow hexagons. Notably, hollow hexagons may be represented with a collection of partitions on the set \(\{2,3,4,6\}\). The hollow hexagons are used to classify another family of primitive coronoids, which we introduce here, called lattice path coronoids. Techniques from lattice path enumeration are used to count these newly-defined structures within equivalence classes indexed by enclosing hollow hexagons.

Abstract:A \(2\)-noncrossing tree is a rooted tree drawn in the plane with its vertices (colored black or white) on the boundary of a circle such that the edges are line segments that do not intersect inside the circle and there is no black-black ascent in any path from the root. A rooted tree is said to be increasing if the labels of the vertices are increasing as one moves away from the root. In this paper, we use generating functions and bijections to enumerate \(2\)-noncrossing increasing trees by the number of blacks vertices and by root degree. Bijections with noncrossing trees, ternary trees, 2-plane trees, certain Dyck paths, and certain restricted lattice paths are established.

Abstract:This paper introduces the new notion of total chromatic vertex stress of a graph. Results for certain tree families and other \(2\)-colorable graphs are presented. The notions of chromatically-stress stability and chromatically-stress regularity are also introduced. New research avenues are also proposed.

Abstract:Coloring the arcs of biregular graphs was introduced with possible applications to industrial chemistry, molecular biology, cellular neuroscience, etc. Here, we deal with arc coloring in some non-bipartite graphs. In fact, for \(1< k \in\mathbb{Z}\), we find that the odd graph \(O_k\) has an arc factorization with colors \(0,1,\ldots,k\) such that the sum of colors of the two arcs of each edge equals \(k\). This is applied to analyzing the influence of such arc factorizations in recently constructed uniform 2-factors in \(O_k\) and in Hamilton cycles in \(O_k\) as well as in its double covering graph known as the middle-levels graph \(M_k\).

Abstract:Let \(G\) be a graph with \(n\) vertices. The second Zagreb energy of graph \(G\) is defined as the sum of the absolute values of the eigenvalues of the second Zagreb matrix of graph \(G\). In this paper, we derive the relation between the second Zagreb matrix and the adjacency matrix of graph \(G\) and derive the new upper bound for the second Zagreb energy in the context of trace. We also derive the second Zagreb energy of \(m-\)splitting graph and \(m-\)shadow graph of a graph.

Abstract:The Sombor index (\(SO\)) and the modified Sombor index (\(^mSO\)) are two closely related vertex-degree-based graph invariants. Both were introduced in the 2020s, and have already found a variety of chemical, physicochemical, and network-theoretical applications. In this paper, we examine the product \(SO \cdot {^mSO}\) and determine its main properties. It is found that the structure-dependence of this product is fully different from that of either \(SO\) or \(^mSO\). Lower and upper bounds for \(SO \cdot {^mSO}\) are established and the extremal graphs are characterized. For connected graphs, the minimum value of the product \(SO \cdot {^mSO}\) is the square of the number of edges. In the case of trees, the maximum value pertains to a special type of eclipsed sun graph, trees
with a single branching point.

Abstract:Using coalescence and cones, this study defines three types of graphs formed by amalgamating vertices of disjoint unions of complete graphs. The three types include the cone over a disjoint union of two complete graphs (C1), the cone over a disjoint union of \(k\) complete graphs (C2), and the \(l\) cone over a disjoint union of two complete graphs (C3). Coalescence of complete graphs (C1, C3) and the \(l\) cone (C3) are determined by their Laplacian spectra, a novel finding. Their Laplacian spectra reveal the size of the vertex cutset. Applications include the analysis of corporate networks, where individuals form coalescence of complete graphs through joint membership of two or more company boards.

Abstract:A famous conjecture of Ryser states that any \(r\)-partite set system has transversal number at most \(r-1\) times their matching number. This conjecture is only known to be true for \(r\leq3\) in general, for \(r\leq5\) if the set system is intersecting, and for \(r\leq9\) if the set system is intersecting and linear. In this note, we deal with Ryser’s conjecture for intersecting \(r\)-partite linear systems: if \(\tau\) is the transversal number for an intersecting \(r\)-partite linear system, then \(\tau\leq r-1\). If this conjecture is true, this is known to be sharp for \(r\) for which there exists a projective plane of order \(r-1\). There has also been considerable effort to find intersecting \(r\)-partite set systems whose transversal number is \(r-1\). In this note, we prove that if \(r\geq2\) is an even integer, then \(f_l(r)\geq3r-5\), where \(f_l(r)\) is the minimum number of lines of an intersecting \(r\)-partite linear system whose transversal number is \(r-1\). Aharoni \emph{et al.,} [R. Aharoni, J. Barát and I.M. Wanless, \emph{Multipartite hypergraphs achieving equality in Ryser’s conjecture}, Graphs Combin. {\bf 32}, 1–15 (2016)] gave an asymptotic lower bound: \(f_l(r)\geq3\).\(052r+O(1)\) as \(r\to\infty\). For some small values of \(r\) (\(r\geq2\) an even integer), our lower bound is better. Also, we prove that any \(r\)-partite linear system satisfies \(\tau\leq r-1\) if \(\nu_2\leq r\) for all \(r\geq3\) odd integer and \(\nu_2\leq r-2\) for all \(r\geq4\) even integer, where \(\nu_2\) is the maximum cardinality of a subset of lines \(R\subseteq\mathcal{L}\) such that any three elements chosen in \(R\) do not have a common point.

Abstract:The vertex-degree based (VDB) topological index (or graphical function-index) \(TI_{f}(G)\) of \(G\) with edge-weight function \(f(x,y)\) was defined as \(TI_{f}(G)=\sum\limits_{uv\in E(G)}f(d(u),d(v))\), where \(d(u)\) is the degree of vertex \(u\) in \(G\). In this paper, we use a unified way to determine the extremal values of VDB indices of connected \((n,m)\)-graphs. When \(f(x,y)\) satisfies some special properties, we determine the connected \((n,m)\)-graphs with maximum (or minimum) \(TI_{f}(G)\) is the almost regular graphs. Our results generalize the results of paper [Aashtab, A., Akbari, S., Madadinia, S., Noei, M., \& Salehi, F. (2022) On the graphs with minimum Sombor index. MATCH Commun. Math. Comput. Chem., {88}, 553-559].

Abstract:For all positive even integers \(n\), graphs of order \(n\) with degree sequence \(S_{n}:1,2,\dots,n/2,n/2,n/2+1,n/2+2,\dots,n-1\) naturally arose in the study of a labeling problem in [1].This fact motivated the authors of the aforementioned paper to study these sequences and as a result of this study they proved that there is a unique graph of order \(n\) realizing \(S_{n}\) for every even integer \(n\). The main goal of this paper is to generalize this result.

Abstract:The Sombor index has gained lot of attention in the recent days for its mathematical properties and chemical applicabilities. Here, we initiated the novel block number version of the classical Sombor index and its matrix representation of a graph. The Block Sombor index \(BS(G)\) is defined as the sum total of square root of the sum of squares of block numbers of adjacent vertices, where the block number of a vertex is the number of blocks to which that vertex belongs to. The main purpose of this paper is to obtain some bounds and characterizations of \(BS(G)\) and its Block Sombor energy \(E_{BS}\). Also, we estimate some properties of spectral radius of Block Sombor matrix \(A_{BS}(G)\).

Abstract: We find the maximum and minimum connected unicyclic and connected well-covered unicyclic graphs of a given order with respect to \(\preceq\). This extends 2013 work by Csikv’ari where the maximum and minimum trees of a given order were determined and also answers an open question posed in the same work. Corollaries of our results give the graphs that minimize and maximize \(\xi(G)\) among all connected (well-covered) unicyclic graphs. We also answer more related open questions posed by Oboudi in 2018 and disprove a conjecture due to Levit and Mandrescu from 2008. The independence polynomial of a graph \(G\), denoted \(I(G,x)\), is the generating polynomial for the number of independent sets of each size. The roots of \(I(G,x)\) are called the independence roots of \(G\). It is known that for every graph \(G\), the independence root of smallest modulus, denoted \(\xi(G)\), is real. The relation \(\preceq\) on the set of all graphs is defined as follows, \(H\preceq G\) if and only if \(I(H,x)\ge I(G,x)\text{ for all }x\in [\xi(G),0].\)

Abstract: In this paper, the fuzzy nonlinear partial differential equations of fractional order are considered. The generalization differential transform method (DTM) and fuzzy variational iteration method (VIM) were applied to solve fuzzy nonlinear partial differential equations of fractional order. The above methods are investigated based on Taylor’s formula, and fuzzy Caputo’s fractional derivative. The proposed methods are also illustrated by some examples. The results reveal the methods are a highly effective scheme for obtaining the fuzzy fractional partial differential equations.

Abstract: This paper presents several fixed point theorems for intuitionistic generalized fuzzy metric spaces with an implicit relation. Specifically, we utilize compatible maps of type \((\beta)\) in intuitionistic generalized fuzzy metric spaces to derive our fixed point theorems. Our results not only extend but also generalize some fixed point theorems that were previously established in complete fuzzy metric spaces. This is achieved by introducing a novel technique, which enhances the applicability and scope of the existing fixed point theorems.

Abstract: The paper is concerned with the KG-Sombor index (\(KG\)), a recently introduced vertex-and-edge-degree-based version of the Sombor index, applied to Kragujevac trees (\(Kg\)). A general combinatorial expression for \(KG(Kg)\) is established. The species with minimum and maximum \(KG(Kg)\)-values are determined.

Abstract: In an improper coloring, an edge $uv$ for which, \(c(u)=c(v)\) is called a bad edge. The notion of the chromatic completion number of a graph \(G\) denoted by \(\zeta(G),\) is the maximum number of edges over all chromatic colorings that can be added to \(G\) without adding a bad edge. We introduce the stability of a graph in respect of chromatic completion. We prove that the set of chromatic completion edges denoted by \(E_\chi(G),\) which corresponds to \(\zeta(G)\) is unique if and only if \(G\) is stable in respect of chromatic completion. After that, chromatic completion and stability regarding Johan coloring are discussed. The difficulty of studying chromatic completion of graph operations is shown by presenting results for two elementary graph operations.

Abstract:This note establishes the induced vertex stress, total induced vertex stress, vertex stress and total vertex stress of the generalized Johnson graphs of diameter \(2\). The note serves as the foundation to establish the same parameters for generalized Johnson graphs of diameter greater than or equal to \(3\).

Abstract:The Sombor index (\(SO\)) is a vertex-degree-based graph invariant, defined as the sum over all pairs of adjacent vertices of \(\sqrt{d_i^2+d_j^2}\), where \(d_i\) is the degree of the \(i\)-th vertex. It has been conceived using geometric considerations. Numerous researches of \(SO\) that followed, ignored its geometric origin. We now show that geometry-based reasonings reveal the geometric background of several classical topological indices (Zagreb, Albertson) and lead to a series of new \(SO\)-like degree-based graph invariants.

Abstract:In 2006, Konstantinova proposed the marginal entropy of a graph based on the Wiener index. In this paper, we obtain the marginal entropy of the complete multipartite graphs, firefly graphs, lollipop graphs, clique-chain graphs, Cartesian product and join of two graphs, which extends the results of ¸Sahin.

Abstract:The concept of Lucky colorings of a graph is used to introduce the notion of the Lucky \(k\)-polynomials of null graphs. We then give the Lucky \(k\)-polynomials for complete split graphs and generalized star graphs. Finally, further problems of research related to this concept are discussed.

Abstract:In the present communication, we introduce the theory of Type-II generalized Pythagorean bipolar fuzzy soft sets and define complementation, union, intersection, AND, and OR. The Type-II generalized Pythagorean bipolar fuzzy soft sets are presented as a generalization of soft sets. We showed De Morgan’s laws, associate laws, and distributive laws in Type-II generalized Pythagorean bipolar fuzzy soft set theory. Also, we advocate an algorithm to solve the decision-making problem based on a soft set model.

Abstract:A \(k\)-plane tree is a tree drawn in the plane such that the vertices are labeled by integers in the set \(\{1,2,\ldots,k\}\), the children of all vertices are ordered, and if \((i,j)\) is an edge in the tree, where \(i\) and \(j\) are labels of adjacent vertices in the tree, then \(i+j\leq k+1\). In this paper, we construct bijections between these trees and the sets of \(k\)-noncrossing increasing trees, locally oriented \((k-1)\)-noncrossing trees, Dyck paths, and some restricted lattice paths.

Abstract:TEMO = topological effect on molecular orbitals was discovered by Polansky and Zander in 1982, in connection with the eigenvalues of molecular graphs. Eventually, analogous regularities were established for a variety of other topological indices. We now show that a TEMO-type regularity also holds for the Sombor index (\(SO\)): For the graphs \(S\) and \(T\), constructed by connecting a pair of vertex-disjoint graphs by two edges, \(SO(S) < SO(T)\) holds. Analogous relations are verified for several other degree-based graph invariants.

Abstract:In this paper, we define the binomial transform of the generalized fifth order Jacobsthal sequence and as special cases, the binomial transform of the fifth order Jacobsthal, fifth order Jacobsthal-Lucas, adjusted fifth order Jacobsthal and modified fifth order Jacobsthal-Lucas sequences will be introduced. We investigate their properties in details.