University of Isfahan Transactions on Combinatorics 2251-8657 11 4 2022 12 01 Total perfect codes in graphs realized by commutative rings 295 307 26081 10.22108/toc.2021.122946.1727 EN Rameez Raja Department of Mathematics, National Institute of Technology, Hazratbal-190006, Srinagar, India Journal Article 2020 05 08 Let \$R\$ be a commutative ring with unity not equal to zero and let \$Gamma(R)\$ be a zero-divisor graph realized by \$R\$. For a simple, undirected, connected graph \$G = (V, E)\$, a {it total perfect code} denoted by \$C(G)\$ in \$G\$ is a subset \$C(G) subseteq V(G)\$ such that \$|N(v) cap C(G)| = 1\$ for all \$v in V(G)\$, where \$N(v)\$ denotes the open neighbourhood of a vertex \$v\$ in \$G\$. In this paper, we study total perfect codes in graphs which are realized as zero-divisor graphs. We show a zero-divisor graph realized by a local commutative ring with unity admits a total perfect code if and only if the graph has degree one vertices. We also show that if \$Gamma(R)\$ is a regular graph on \$|Z^*(R)|\$ number of vertices, then \$R\$ is a reduced ring and \$|Z^*(R)| equiv 0 (mod ~2)\$, where \$Z^*(R)\$ is a set of non-zero zero-divisors of \$R\$. We provide a characterization for all commutative rings with unity of which the realized zero-divisor graphs admit total perfect codes. Finally, we determine the cardinality of a total perfect code in \$Gamma(R)\$ and discuss the significance of the study of total perfect codes in graphs realized by commutative rings with unity. https://toc.ui.ac.ir/article_26081_b310028bfbd7cbc36e3ad3df8708b1fd.pdf
University of Isfahan Transactions on Combinatorics 2251-8657 11 4 2022 12 01 The identifying code number and Mycielski's construction of graphs 309 316 26088 10.22108/toc.2021.126368.1794 EN Athena Shaminejad Department of Mathematics, Imam Khomeini International University of Qazvin, P.O.Box 3414896818, Qazvin, Iran Ebrahim Vatandoost Department of Mathematics, Imam Khomeini International University of Qazvin, P.O.Box 3414896818, Qazvin, Iran Kamran Mirasheh Department of Mathematics, Imam Khomeini International University of Qazvin, P.O.Box 3414896818, Qazvin, Iran Journal Article 2020 12 07 Let \$G=(V, E)\$ be a simple graph. A set \$C\$ of vertices \$G\$ is an identifying code of \$G\$ if for every two vertices \$x\$ and \$y\$ the sets \$N_{G} [x] cap C\$ and \$N_{G} [y] cap C\$ are non-empty and different. Given a graph \$G,\$ the smallest size of an identifying code of \$G\$ is called the identifying code number of \$G\$ and denoted by \$gamma^{ID}(G).\$ Two vertices \$x\$ and \$y\$ are twins when \$N_{G}[x]=N_{G}[y].\$ Graphs with at least two twin vertices are not an identifiable graph. In this paper, we deal with the identifying code number of Mycielski's construction of graph \$G.\$ We prove that the Mycielski's construction of every graph \$G\$ of order \$n geq 2,\$ is an identifiable graph. Also, we present two upper bounds for the identifying code number of Mycielski's construction \$G,\$ such that these two bounds are sharp. Finally, we show that Foucaud et al.'s conjecture is holding for Mycielski's construction of some graphs. https://toc.ui.ac.ir/article_26088_858b032cc710d026f084d95cbe679621.pdf
University of Isfahan Transactions on Combinatorics 2251-8657 11 4 2022 12 01 Bounds for the pebbling number of product graphs 317 326 25997 10.22108/toc.2021.128705.1855 EN Nopparat Pleanmani Department of Mathematics, Faculty of Science, Khon Kaen University, Khon Kaen 40002, Thailand 0000-0002-1889-3826 Nuttawoot Nupo Department of Mathematics, Faculty of Science, Khon Kaen University, Khon Kaen 40002, Thailand Somnuek Worawiset Department of Mathematics, Faculty of Science, Khon Kaen University, Khon Kaen 40002, Thailand Journal Article 2021 05 15 Let \$G\$ be a connected graph. Given a configuration of a fixed number of pebbles on the vertex set of \$G\$, a pebbling move on \$G\$ is the process of removing two pebbles from a vertex and adding one pebble on an adjacent vertex. The pebbling number of \$G\$, denoted by \$pi(G)\$, is defined to be the least number of pebbles to guarantee that there is a sequence of pebbling movement that places at least one pebble on each vertex \$v\$, for any configuration of pebbles on \$G\$. In this paper, we improve the upper bound of \$pi(Gsquare H)\$ from \$2pi(G)pi(H)\$ to \$left(2-frac{1}{min{pi(G),pi(H)}}right)pi(G)pi(H)\$ where \$pi(G)\$, \$pi(H)\$ and \$pi(Gsquare H)\$ are the pebbling number of graphs \$G\$, \$H\$ and the Cartesian product graph \$Gsquare H\$, respectively. Moreover, we also discuss such bound for strong product graphs, cross product graphs and coronas. https://toc.ui.ac.ir/article_25997_501663d1ee8baceb41a23ea159ff00d0.pdf
University of Isfahan Transactions on Combinatorics 2251-8657 11 4 2022 12 01 Chromatic number and signless Laplacian spectral radius of graphs 327 334 26159 10.22108/toc.2021.129720.1876 EN Mohammad Reza Oboudi Department of Mathematics, College of Sciences, Shiraz University, Shiraz, 71457-44776, Iran Journal Article 2021 07 23 For any simple graph \$G\$, the signless Laplacian matrix of \$G\$ is defined as \$D(G)+A(G)\$, where \$D(G)\$ and \$A(G)\$ are the diagonal matrix of vertex degrees and the adjacency matrix of \$G\$, respectively. %Let \$chi(G)\$ be the chromatic number of \$G\$ Let \$q(G)\$ be the signless Laplacian spectral radius of \$G\$ (the largest eigenvalue of the signless Laplacian matrix of \$G\$). In this paper we find some relations between the chromatic number and the signless Laplacian spectral radius of graphs. In particular, we characterize all graphs \$G\$ of order \$n\$ with odd chromatic number \$chi\$ such that \$q(G)=2nBig(1-frac{1}{chi}Big)\$. Finally we show that if \$G\$ is a graph of order \$n\$ and with chromatic number \$chi\$, then under certain conditions, \$q(G)<2nBig(1-frac{1}{chi}Big)-frac{2}{n}\$. This result improves some previous similar results. https://toc.ui.ac.ir/article_26159_fec709a44b419ec4680f4424fb080a49.pdf
University of Isfahan Transactions on Combinatorics 2251-8657 11 4 2022 12 01 Linear codes resulting from finite group actions 335 343 26249 10.22108/toc.2022.126254.1786 EN Driss Harzalla Department of Mathematics, University of Cadi Ayyad, Box 63 46000 Route Sidi Bouzid, Safi, Morocco Journal Article 2020 11 29 In this article, we use group action theory to define some important ternary linear codes. Some of these codes are self-orthogonal having a minimum distance achieving the lower bound in the previous records. Then, we define two new codes sharing the same automorphism group isomorphic to \$C_2 times M_{11}\$ where \$M_{11}\$ is the Sporadic Mathieu group and \$C_{2}\$ is a cyclic group of two elements. We also study the natural action of the general linear group \$GL (k, 2) \$ on the vector space \$F_2 ^ k\$ to characterize Hamming codes \$H_k (2) \$ and their automorphism group. https://toc.ui.ac.ir/article_26249_cef63884ba688f96468d5abf3cb393bb.pdf