Transactions on Combinatorics
Volume:9 Issue: 1, Mar 2020

For a graph $G=(V,E)$, a set $S subseteq V$ is a $[1,2]$-set if it is a dominating set for $G$ and each vertex $v in V setminus S$ is dominated by at most two vertices of $S$, i.e. $1 leq vert N(v) cap S vert leq 2$. Moreover a set $S subseteq V$ is a total $[1,2]$-set if for each vertex of $V$, it is the case that $1 leq vert N(v) cap S vert leq 2$. The $[1,2]$-domination number of $G$, denoted $gamma_{[1,2]}(G)$, is the minimum number of vertices in a $[1,2]$-set. Every $[1,2]$-set with cardinality of $gamma_{[1,2]}(G)$ is called a $gamma_{[1,2]}$-set. Total $[1,2]$-domination number and $gamma_{t[1,2]}$-sets of $G$ are defined in a similar way. This paper presents a linear time algorithm to find a $gamma_{[1,2]}$-set and a $gamma_{t[1,2]}$-set in generalized series-parallel graphs.

‎Metric dimension and defensive $k$-alliance number are two distance-based graph invariants‎ ‎which have applications in robot navigation‎, ‎quantitative analysis of secondary RNA structures‎, ‎national defense and fault-tolerant computing‎. ‎In this paper‎, ‎some bounds for metric‎ ‎dimension and defensive $k$-alliance of deleted lexicographic product of graphs are presented‎. ‎We also show that the bounds are sharp‎.

* The formula in not displayed correctly!

Let $R$ be a ring and $alpha$ be a ring endomorphism of $R$‎. ‎The undirected nilpotent graph of $R$‎, ‎denoted by $Gamma_N(R)$‎, ‎is a graph with vertex set $Z_N(R)^*$‎, ‎and two distinct vertices $x$ and $y$ are connected by an edge if and only if $xy$ is nilpotent‎, ‎where $Z_N(R)={xin R;|; xy; rm{is; nilpotent,;for; some}; yin R^*}.$ In this article‎, ‎we investigate the interplay between the ring theoretical properties of a skew polynomial ring $R[x;alpha]$ and the graph-theoretical properties of its nilpotent graph $Gamma_N(R[x;alpha])$‎. ‎It is shown that if $R$ is a symmetric and $alpha$-compatible with exactly two minimal primes‎, ‎then $diam(Gamma_N(R[x,alpha]))=2$‎. ‎Also we prove that $Gamma_N(R)$ is a complete graph if and only if $R$ is isomorphic to $Z_2timesZ_2$‎.

* The formula is not displayed correctly!

In this paper we classify distance-regular graphs‎, ‎including strongly regular graphs‎, ‎admitting a transitive action of the linear groups $L(3,2)$‎, ‎$L(3,3)$‎, ‎$L(3,4)$ and $L(3,5)$ for which the rank of the permutation representation is at most 15‎. ‎We give details about constructed graphs‎. ‎In addition‎, ‎we construct self-orthogonal codes from distance-regular graphs obtained in this paper‎.

* The formula is not displayed correctly!