Canadian Mathematical Society
Canadian Mathematical Society
  location:  Publicationsjournals
Search results

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

  Expand all        Collapse all Results 1 - 5 of 5

1. CMB Online first

Shaveisi, Farzad
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, cycle
Categories:05C15, 05C69, 13E05, 13E10

2. CMB 2015 (vol 58 pp. 271)

Jafari, Sayyed Heidar; Jafari Rad, Nader
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 ring

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 selection
Categories: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 number

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, domination
Categories:13AXX, 05C69

© Canadian Mathematical Society, 2016 :