Transactions on Combinatorics
Volume:11 Issue: 4, Dec 2022

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.

* Formulas are not displayed correctly.

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 NG[x] ∩ C and NG[y] ∩ 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 γ ID(G). Two vertices x and y are twins when NG[x] = NG[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 ≥ 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.

* Formulas are not displayed correctly.

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 π(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 π(GH) from 2π(G)π(H) to  2 − 1 min{π(G),π(H)}  π(G)π(H) where π(G), π(H) and π(GH) are the pebbling number of graphs G, H and the Cartesian product graph GH, respectively. Moreover, we also discuss such bound for strong product graphs, cross product graphs and coronas.

* Formulas are not displayed correctly.

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.

* Formulas are not displayed correctly.

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 C2 × M11 where M11 is the Sporadic Mathieu group and C2 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 k 2 to characterize Hamming codes Hk(2) and their automorphism group.