University of IsfahanTransactions on Combinatorics2251-865714320240423Density-Based clustering in mapReduce with guarantees on parallel time, space, and solution quality1351562826410.22108/toc.2024.138377.2091ENSepidehAghamolaeiDepartment of Computer Engineering, Sharif University of Technology, Tehran, IranMohammadGhodsiDepartment of Computer Engineering, Sharif University of Technology, Tehran, Iran.
School of Computer Science, Institute for Research in Fundamental Sciences (IPM), Tehran, Iran.Journal Article20230712A well-known clustering problem called Density-Based Spatial Clustering of Applications with Noise~(DBSCAN) involves computing the solutions of at least one disk range query per input point, computing the connected components of a graph, and bichromatic fixed-radius nearest neighbor. MapReduce class is a model where a sublinear number of machines, each with sublinear memory, run for a polylogarithmic number of parallel rounds.<br /> <br />Most of these problems either require quadratic time in the sequential model or are hard to compute in a constant number of rounds in MapReduce. In the Euclidean plane, DBSCAN algorithms with near-linear time and a randomized parallel algorithm with a polylogarithmic number of rounds exist.<br /> <br />We solve DBSCAN in the Euclidean plane in a constant number of rounds in MapReduce, assuming the minimum number of points in range queries is constant and each connected component fits inside the memory of a single machine and has a constant diameter.https://toc.ui.ac.ir/article_28264_25c4b7936d8b67c3489a676b9a960418.pdfUniversity of IsfahanTransactions on Combinatorics2251-865714320250901Minimal graphs with respect to the multiplicative version of some vertex-degree-based topological indices1571722836910.22108/toc.2024.139624.2119ENMehdiEliasiDepartment of Mathematics , Khansar Faculty, University of Isfahan, Isfahan, IranJournal Article20231028As a real-valued function, a graphical parameter is defined on the class of finite simple graphs, and remains invariant under graph isomorphism. In mathematical chemistry, vertex-degree-based topological indices are the graph parameters of the general form of $p_{\phi}(G)=\sum_{uv\in E(G)}\phi(d(u),d(v))$, where $\phi$ represents a real-valued symmetric function, and $d(u)$ shows the degree of $u\in V(G)$. In this paper, it is proved that if $\phi$ has certain conditions, then the graph among those with $n$ vertices and $m$ edges, whose difference between the maximum and minimum degrees is at most $1$, has the minimal value of $p_{\phi}$. Moreover, it is demonstrated that some well-known topological indices are able to satisfy these certain conditions, and the given indices can be treated in a unified manner.https://toc.ui.ac.ir/article_28369_69de69f3082f6df35d742356561470b1.pdfUniversity of IsfahanTransactions on Combinatorics2251-865714320240917Induced Geodetic Sequence of a Graph1731852859210.22108/toc.2024.138982.2100ENLiju AlexOlickalDepartment of Mathematics, Bishop Chulaparambil Memorial(BCM) College, Kottayam - 686001John JoyMulloorDepartment of Mathematics, Bishop Chulaparambil Memorial(BCM)
College, Kottayam, Kerala, IndiaJournal Article20230901A vertex subset $S$ of a graph $G=(V,E)$ is said to be a geodetic set if every vertex in $G$ is in some $u-v$ geodesic for any $u,v \in S$. The minimum cardinality of such a set is the geodetic number, which is denoted as $g(G)$. In this paper, we introduce the concepts of induced geodetic number and induced geodetic sequence of a graph. We discuss this concept in some graph classes. Also, established the characterization of induced geodetic sequences for trees, unicyclic graphs and cacti.https://toc.ui.ac.ir/article_28592_09b21d4fb23b2b9e5ace659235425f85.pdfUniversity of IsfahanTransactions on Combinatorics2251-865714320240917Some results on $\lambda$-design conjecture1871962865210.22108/toc.2024.139121.2102ENAjeet KumarYadavDepartment of Mathematics, St. Gonsalo Garcia College, University of Mumbai, IndiaJournal Article20230914Let $v$ and $\lambda$ be integers with $0<\lambda<v$. A $\lambda$-design $D$ is a pair $(X, \mathcal{A})$, where $X$ is a finite set with $v$ elements called points and $\mathcal{A}$ is a family of subsets of $X$ called blocks, with $|\mathcal{A}|=|X|$ such that<br /><br /> (1) for all $B_i, B_j\in \mathcal{A},$ $i\neq j,$ $|B_i\cap B_j|=\lambda$;<br /> (2) for all $B_j\in \mathcal{A},$ $|B_j|=k_j>\lambda$, and not all $k_j$ are equal.<br /><br />The only known examples of $\lambda$-designs are so called of type-1 designs, which are obtained from symmetric designs by a certain complementation procedure. Ryser and Woodall had independently conjectured that all $\lambda$-designs are of type-1. Suppose $r$ and $r^*(r>r^*)$ are replication numbers of $D$ and for distinct points $x$ and $y$ of $D$, let $\lambda(x,y)$ denote the number of blocks of $X$ containing $x$ and $y$.<br /> <br />In this paper we investigate the possibilities of $\lambda$-designs to be of type-1 under the condition that $|\lambda(x,y)-\lambda(x,y')|< 2 \left(\dfrac{r-r^*}{r+r^*-2}\right)$. Under this condition, we prove that if $ \dfrac{r-1}{r^*-1} \le 3$, then $\lambda$-design $D$ is of type-1. Also we prove that $D$ has exactly two distinct block sizes.https://toc.ui.ac.ir/article_28652_1adc13206e5fd3f793fec6317a3cb9a9.pdfUniversity of IsfahanTransactions on Combinatorics2251-865714320240903On relationship between reformulated Sombor and other vertex--degree indices1972092872810.22108/toc.2024.136304.2036ENEmina I.MilovanovicFaculty of Electronic Engineering, University of Niš, Niš, SerbiaStefanStankovFaculty of Electronic Engineering, University of Niš, Niš, SerbiaŞerife BurcuBozkurt AltındağDepartment of Mathematics, Faculty of Science, Selçuk University, Konya, TurkeyMarjanMatejicFaculty of Electronic Engineering, University of Nis, SerbiaIgor Z.MilovanovicFaculty of Electronic Engineering, University of Niš, Niš, SerbiaJournal Article20230102Let $G=(V,E)$, $V=\{v_1, v_2,\ldots,v_n\}$, $E=\{e_1, e_2,\ldots,e_m\}$, be a simple connected graph with $n\ge 2$ vertices and $m$ edges, with vertex degree sequence $\Delta=d_1\ge d_2\ge \cdots \ge d_n=\delta$, $ d_i=d(v_i)$, and edge degree sequence $\Delta_e=d(e_1)\ge d(e_2)\ge \cdots \ge d(e_n)=\delta_e$. The reformulated Sombor index is defined as $RS(G) =\sum_{e_i\sim e_j}\sqrt{d(e_i)^2+d(e_j)^2}$. We consider a relationship between reformulated Sombor index and some of the vertex--degree-based indices.https://toc.ui.ac.ir/article_28728_33cf749a9f637f268ea9d91e11e339b3.pdf