Canadian Mathematical Society www.cms.math.ca
 location:  Publications → journals
Search results

Search: MSC category 05C69 ( Dominating sets, independent sets, cliques )

 Expand all        Collapse all Results 1 - 5 of 5

1. CMB Online first

 Some Results on the Annihilating-Ideal Graphs The annihilating-ideal graph of a commutative ring $R$, denoted by $\mathbb{AG}(R)$, is a graph whose vertex set consists of all non-zero annihilating ideals and two distinct vertices $I$ and $J$ are adjacent if and only if $IJ=(0)$. Here, we show that if $R$ is a reduced ring and the independence number of $\mathbb{AG}(R)$ is finite, then the edge chromatic number of $\mathbb{AG}(R)$ equals its maximum degree and this number equals $2^{|{\rm Min}(R)|-1}-1$; also, it is proved that the independence number of $\mathbb{AG}(R)$ equals $2^{|{\rm Min}(R)|-1}$, where ${\rm Min}(R)$ denotes the set of minimal prime ideals of $R$. Then we give some criteria for a graph to be isomorphic with an annihilating-ideal graph of a ring. For example, it is shown that every bipartite annihilating-ideal graph is a complete bipartite graph with at most two horns. Among other results, it is shown that a finite graph $\mathbb{AG}(R)$ is not Eulerian, and it is Hamiltonian if and only if $R$ contains no Gorenstain ring as its direct summand. Keywords:annihilating-ideal graph, independence number, edge chromatic number, bipartite, cycleCategories:05C15, 05C69, 13E05, 13E10

2. CMB 2015 (vol 58 pp. 271)

 On Domination of Zero-divisor Graphs of Matrix Rings We study domination in zero-divisor graphs of matrix rings over a commutative ring with $1$. Keywords:vector space, linear transformation, zero-divisor graph, domination, local ringCategory:05C69

3. CMB 2015 (vol 58 pp. 306)

Khoshkhah, Kaveh; Zaker, Manouchehr
 On the Largest Dynamic Monopolies of Graphs with a Given Average Threshold Let $G$ be a graph and $\tau$ be an assignment of nonnegative integer thresholds to the vertices of $G$. A subset of vertices, $D$ is said to be a $\tau$-dynamic monopoly, if $V(G)$ can be partitioned into subsets $D_0, D_1, \ldots, D_k$ such that $D_0=D$ and for any $i\in \{0, \ldots, k-1\}$, each vertex $v$ in $D_{i+1}$ has at least $\tau(v)$ neighbors in $D_0\cup \ldots \cup D_i$. Denote the size of smallest $\tau$-dynamic monopoly by $dyn_{\tau}(G)$ and the average of thresholds in $\tau$ by $\overline{\tau}$. We show that the values of $dyn_{\tau}(G)$ over all assignments $\tau$ with the same average threshold is a continuous set of integers. For any positive number $t$, denote the maximum $dyn_{\tau}(G)$ taken over all threshold assignments $\tau$ with $\overline{\tau}\leq t$, by $Ldyn_t(G)$. In fact, $Ldyn_t(G)$ shows the worst-case value of a dynamic monopoly when the average threshold is a given number $t$. We investigate under what conditions on $t$, there exists an upper bound for $Ldyn_{t}(G)$ of the form $c|G|$, where $c\lt 1$. Next, we show that $Ldyn_t(G)$ is coNP-hard for planar graphs but has polynomial-time solution for forests. Keywords:spread of influence in graphs, irreversible dynamic monopolies, target set selectionCategories:05C69, 05C85

4. CMB 2013 (vol 57 pp. 141)

Mukwembi, Simon
 Size, Order, and Connected Domination We give a sharp upper bound on the size of a triangle-free graph of a given order and connected domination. Our bound, apart from strengthening an old classical theorem of Mantel and of TurÃ¡n , improves on a theorem of Sanchis. Further, as corollaries, we settle a long standing conjecture of Graffiti on the leaf number and local independence for triangle-free graphs and answer a question of Griggs, Kleitman and Shastri on a lower bound of the leaf number in triangle-free graphs. Keywords:size, connected domination, local independence number, leaf numberCategory:05C69

5. CMB 2011 (vol 56 pp. 407)

Rad, Nader Jafari; Jafari, Sayyed Heidar; Mojdeh, Doost Ali
 On Domination in Zero-Divisor Graphs We first determine the domination number for the zero-divisor graph of the product of two commutative rings with $1$. We then calculate the domination number for the zero-divisor graph of any commutative artinian ring. Finally, we extend some of the results to non-commutative rings in which an element is a left zero-divisor if and only if it is a right zero-divisor. Keywords:zero-divisor graph, dominationCategories:13AXX, 05C69
 top of page | contact us | privacy | site map |

© Canadian Mathematical Society, 2016 : https://cms.math.ca/