University of IsfahanTransactions on Combinatorics2251-865710320210901Upper bounds for the reduced second zagreb index of graphs1371482517410.22108/toc.2020.125478.1774ENBatmendHoroldagvaDepartment of Mathematics, Mongolian National University of Education, Baga toiruu-14, Ulaanbaatar, Mongolia0000-0003-3417-2612Tsend-AyushSelengeDepartment of Mathematics, National University of Mongolia, P.O.Box 187/46A, Ulaanbaatar, Mongolia0000-0002-8479-6389LkhagvaBuyantogtokhDepartment of Mathematics, Mongolian National University of Education, Baga toiruu-14, Ulaanbaatar, MongoliaShiikharDorjsembeDepartment of Mathematics, Mongolian National University of Education, Baga toiruu-14, Ulaanbaatar, MongoliaJournal Article20201018The graph invariant $RM_2$, known under the name reduced second Zagreb index, is defined as $RM_2(G)=\sum_{uv\in E(G)}(d_G(u)-1)(d_G(v)-1)$, where $d_G(v)$ is the degree of the vertex $v$ of the graph $G$. In this paper, we give a tight upper bound of $RM_2$ for the class of graphs of order $n$ and size $m$ with at least one dominating vertex. Also, we obtain sharp upper bounds on $RM_2$ for all graphs of order $n$ with $k$ dominating vertices and for all graphs of order $n$ with $k$ pendant vertices. Finally, we give a sharp upper bound on $RM_2$ for all $k$-apex trees of order $n$. Moreover, the corresponding extremal graphs are characterized.https://toc.ui.ac.ir/article_25174_4be757e0eb219336680ac34256e5727e.pdfUniversity of IsfahanTransactions on Combinatorics2251-865710320210901A local core number based algorithm for the maximum clique problem1491632538510.22108/toc.2021.120153.1686ENNedaMohammadiDepartment of computer science, University of Shahrekord, Shahrekord, IranMehdiKadivarDepartment of computer science, University of Shahrekord, Shahrekord, IranJournal Article20191124The maximum clique problem (MCP) is to determine a complete subgraph of maximum cardinality in a graph. MCP is a fundamental problem in combinatorial optimization and is noticeable for its wide range of applications. In this paper, we present two branch-and-bound exact algorithms for finding a maximum clique in an undirected graph. Many efficient exact branch and bound maximum clique algorithms use approximate coloring to compute an upper bound on the clique number but, as a new pruning strategy, we show that local core number is more efficient. Moreover, instead of neighbors set of a vertex, our search area is restricted to a subset of the set in each subproblem which speeds up clique finding process. This subset is based on the core of the vertices of a given graph. We improved the MCQ and MaxCliqueDyn algorithms with respect to the new pruning strategy and search area restriction. Experimental results demonstrate that the improved algorithms outperform the previous well-known algorithms for many instances when applied to DIMACS benchmark and random graphs.https://toc.ui.ac.ir/article_25385_50a91fd9b6c1a6f01801fd7000d2ca60.pdfUniversity of IsfahanTransactions on Combinatorics2251-865710320210901$Kite_{p+2,p}$ is determined by its Laplacian spectrum1651702548210.22108/toc.2021.126646.1798ENHaticeTopcuDepartment of Mathematics, Nev¸ sehir Hacı Bekta¸ s Veli University, P.O.Box 50300, Nev¸ sehir, TurkeyJournal Article20201225$Kite_{n,p}$ denotes the kite graph that is obtained by appending complete graph with order $p\geq4$ to an endpoint of path graph with order $n-p$. It is shown that $Kite_{n,p}$ is determined by its adjacency spectrum for all $p$ and $n$ [H. Topcu and S. Sorgun, The kite graph is determined by its adjacency spectrum, <em>Applied Math. and Comp.</em>, <strong>330</strong> (2018) 134--142]. For $n-p=1$, it is proven that $Kite_{n,p}$ is determined by its signless Laplacian spectrum when $n\geq4$, $n\neq5$ and is also determined by its distance spectrum when $n\geq4$ [K. C. Das and M. Liu, Kite graphs are determined by their spectra, <em>Applied Math. and Comp.</em>, <strong>297</strong> (2017) 74--78]. In this note, we say that $Kite_{n,p}$ is determined by its Laplacian spectrum for $n-p\leq2$.https://toc.ui.ac.ir/article_25482_54393cd57fb5ad62d1123c0c0e64b758.pdfUniversity of IsfahanTransactions on Combinatorics2251-865710320210901Integrity of graph operations1711852556610.22108/toc.2021.121736.1710ENB.BasavanagoudDepartment of Mathematics, Karnatak University, Dharwad - 580 003, Karnataka, Indiahttps://orcid.org/00ShrutiPolicepatilDepartment of
Mathematics, Karnatak University, Dharwad - 580 003, Karnataka, IndiaPraveenJakkannavarDepartment of Mathematics, Karnatak University, Dharwad - 580 003, Karnataka, IndiaJournal Article20200220A communication network can be considered to be highly vulnerable to disruption if the failure of few members (nodes or links) can result in no members being able to communicate with very many others. These communication networks can be modeled through graphs. There are several graph-theoretic parameters to describe the stability of graphs. But, these parameters are not sufficient to study stability of graphs. This leads to the concept of integrity of a graph. In this paper, we obtain the integrity of some graph operations and some special graphs which can help us to reconstruct the given network in such a way that it is more stable than the earlier one.https://toc.ui.ac.ir/article_25566_fc7079a097bf1118f46877e7d576a569.pdfUniversity of IsfahanTransactions on Combinatorics2251-865710320210901Iota energy orderings of bicyclic signed digraphs1872002556710.22108/toc.2021.126881.1805ENXiuwenYangSchool of Mathematics and Statistics, Northwestern Polytechnical University, 710129, Xi’an, Shaanxi, P. R. ChinaLigongWangSchool of Mathematics and Statistics, Northwestern Polytechnical University, 710129, Xi’an, Shaanxi, P. R. ChinaJournal Article20210108The concept of energy of a signed digraph is extended to iota energy of a signed digraph. The energy of a signed digraph $S$ is defined by $E(S)=\sum_{k=1}^n|{Re}(z_k)|$, where ${Re}(z_k)$ is the real part of eigenvalue $z_k$ and $z_k$ is the eigenvalue of the adjacency matrix of $S$ with $n$ vertices, $k=1, 2,\ldots,n$. Then the iota energy of $S$ is defined by $E(S)=\sum_{k=1}^n|{Im}(z_k)|$, where ${Im}(z_k)$ is the imaginary part of eigenvalue $z_k$. In this paper, we consider a special graph class for bicyclic signed digraphs $\mathcal{S}_n$ with $n$ vertices which have two vertex-disjoint signed directed even cycles. We give two iota energy orderings of bicyclic signed digraphs, one is including two positive or two negative directed even cycles, the other is including one positive and one negative directed even cycles.https://toc.ui.ac.ir/article_25567_b7b94ad4ded8b3949671f85716761580.pdf