Narrow Results

This paper focuses on situations in several companies each of which has a set of jobs that it has to complete. Each job has a specific starting and ending time and a specific starting and ending point. In order to complete its jobs a company needs to acquire components. There are several types of components. Each job requires exactly one component but not all components are suitable for all jobs. By cooperating, the companies can reduce the costs of acquisition. A component can be used by several companies as long as there is no overlap in the time-intervals of usage by different companies and there is enough time to move the component from where a company has stopped using it to where the next company needs it. A cooperative component acquisition game is constructed to model the cooperation between the companies. This game need not be balanced. Additional properties are introduced that guarantee the game to be totally balanced. We construct an element of the core by using the integer programming formulation of the characteristic function. These games have some relationship with coloring games but we show that results that are valid for coloring games do not hold for them.

The intersection graph I_TΓ(R) of gamma sets in the total graph T_Γ(R) of a commutative ring R, is the undirected graph with vertex set as the collection of all γ-sets in the total graph of R and two distinct vertices u and v are adjacent if and only if u ∩ v ≠ ∅. Tamizh Chelvam and Asir [The intersection graph of gamma sets in the total graph I, to appear in J. Algebra Appl.] studied about I_TΓ(R) where R is a commutative Artin ring. In this paper, we continue our interest on I_TΓ(R) and actually we study about Eulerian, Hamiltonian and pancyclic nature of I_TΓ(R). Further, we focus on certain graph theoretic parameters of I_TΓ(R) like the independence number, the clique number and the connectivity of I_TΓ(R). Also, we obtain both vertex and edge chromatic numbers of I_TΓ(R). In fact, it is proved that if R is a finite commutative ring, then χ(I_TΓ(R)) = ω(I_TΓ(R)). Having proved that I_TΓ(R) is weakly perfect for all finite commutative rings, we further characterize all finite commutative rings for which I_TΓ(R) is perfect. In this sequel, we characterize all commutative Artin rings for which I_TΓ(R) is of class one (i.e. χ′(I_TΓ(R)) = Δ(I_TΓ(R))). Finally, it is proved that the vertex connectivity and edge connectivity of I_TΓ(R) are equal to the degree of any vertex in I_TΓ(R).

The enhanced power graph ${{𝒢}}_e(G)$ of a group $G$ is the graph with vertex set $G$ such that two vertices $x$ and $y$ are adjacent if they are contained in the same cyclic subgroup. We prove that finite groups with isomorphic enhanced power graphs have isomorphic directed power graphs. We show that any isomorphism between undirected power graph of finite groups is an isomorphism between enhanced power graphs of these groups, and we find all finite groups $G$ for which $\mathrm{\text{Aut}}({{𝒢}}_e(G)$ is abelian, all finite groups $G$ with $|\mathrm{\text{Aut}}({{𝒢}}_e(G)|$ being prime power, and all finite groups $G$ with $|\mathrm{\text{Aut}}({{𝒢}}_e(G)|$ being square-free. Also, we describe enhanced power graphs of finite abelian groups. Finally, we give a characterization of finite nilpotent groups whose enhanced power graphs are perfect, and we present a sufficient condition for a finite group to have weakly perfect enhanced power graph.

Let $(P,\le )$ be an atomic poset with the least element $0$. The complement of the intersection graph of ideals of $P$, denoted by $\mathrm{\Gamma }(P)$, is defined to be a graph whose vertices are all non-trivial ideals of $P$ and two distinct vertices $I$ and $J$ are adjacent if and only if $I\cap J=\{0\}$. In this paper, we consider the complement of the intersection graph of ideals of a poset. We prove that $\mathrm{\Gamma }(P)$ is totally disconnected or $\text{diam}(\mathrm{\Gamma }(P)\backslash 𝔄)\in \{1,2,3\}$, where $𝔄$ is the set of all isolated vertices of $\mathrm{\Gamma }(P)$. We show that $gr(\mathrm{\Gamma }(P))\in \{3,4,\infty \}$. Also, we characterize all posets whose complement of the intersection graph is forest, unicyclic or complete $r$-partite graph. Among other results, we prove that $\mathrm{\Gamma }(P)$ is weakly perfect; and it is perfect if and only if $|\text{Atom}(P)|\le 4$. Finally, we show that $\mathrm{\Gamma }(P)$ is class $1$, where $P=\text{Atom}(P)\cup \{0\}$.

For a lattice $L$, we associate a graph called the strongly annihilator ideal graph of $L$, which is denoted by $\mathrm{\text{SAnnIG}}(L)$. It is a graph with vertex set consists of all ideals of $L$ having nontrivial annihilators, and any two distinct vertices $I$ and $J$ are adjacent in $\mathrm{\text{SAnnIG}}(L)$ if and only if the annihilator of $I$ contains a nonzero element of $J$ and the annihilator of $J$ contains a nonzero element of $I$. We show that $\mathrm{\text{SAnnIG}}(L)$ is connected with the diameter at most two and its girth is 3, 4, or infinity. We characterize all lattices whose $\mathrm{\text{SAnnIG}}(L)$ is planar. Among other results, it is proved that $\mathrm{\text{SAnnIG}}(L)$ is perfect.

R-processes are a new type of discrete stationary stochastic process. In this paper, we investigate the underlying structure of two special classes of r-processes. For each class, we will prove precisely when the associated multidigraph is perfect.

In this paper, we study the non-commuting graph $\mathrm{\Gamma }(M_3^{\mathrm{\text{su}}}(C_n))$ of strictly upper triangular $3\times 3$ matrices over an $n$-element chain $C_n$. We prove that $\mathrm{\Gamma }(M_3^{\mathrm{\text{su}}}(C_n))$ is a compact graph. From $\mathrm{\Gamma }(M_3^{\mathrm{\text{su}}}(C_n))$, we construct a poset $P$. We further prove that $P\oplus 1$ is a dismantlable lattice and its zero-divisor graph is isomorphic to $\mathrm{\Gamma }(M_3^{\mathrm{\text{su}}}(C_n))$. Lastly, we prove that $\mathrm{\Gamma }(M_3^{\mathrm{\text{su}}}(C_n))$ is a perfect graph.

Let $R$ be a commutative ring and $M$ be an $R$-module, and let $I{(R)}^{\ast }$ be the set of all nontrivial ideals of $R$. The $M$-intersection graph of ideals of $R$, denoted by $G_M(R)$, is a graph with the vertex set $I{(R)}^{\ast }$, and two distinct vertices $I$ and $J$ are adjacent if and only if $IM\cap JM\ne \{0\}$. For every multiplication $R$-module $M$, the diameter and the girth of $G_M(R)$ are determined. Among other results, we prove that if $M$ is a faithful $R$-module and the clique number of $G_M(R)$ is finite, then $R$ is a semilocal ring. We denote the ${\mathbb{Z}}_n$-intersection graph of ideals of the ring ${\mathbb{Z}}_m$ by $G_n({\mathbb{Z}}_m)$, where $n,m\ge 2$ are integers and ${\mathbb{Z}}_n$ is a ${\mathbb{Z}}_m$-module. We determine the values of $n$ and $m$ for which $G_n({\mathbb{Z}}_m)$ is perfect. Furthermore, we derive a sufficient condition for $G_n({\mathbb{Z}}_m)$ to be weakly perfect.

Let $R$ be a commutative ring with identity which is not an integral domain. An ideal $I$ of a ring $R$ is called an annihilating ideal if there exists $r\in R\backslash \{0\}$ such that $Ir=(0)$. Let $\mathrm{\Omega }(R)$ be a simple undirect graph associated with $R$ whose vertex set is the set of all nonzero annihilating ideals of $R$ and two distinct vertices $I,J$ are joined if and only if $I+J$ is also an annihilating ideal of $R$. A perfect graph is a graph in which the chromatic number of every induced subgraph equals the size of the largest clique of that subgraph. In this paper, we characterize all rings whose $\mathrm{\Omega }(R)$ is perfect.

Let $R$ be a commutative ring with identity, and let $Z(R)$ be the set of zero-divisors of $R$. The annihilator graph of $R$ is defined as the graph $\mathrm{\text{AG}}(R)$ with the vertex set $Z{(R)}^{\ast }=Z(R)\setminus \{0\}$, and two distinct vertices $x$ and $y$ are adjacent if and only if ${\mathrm{\text{ann}}}_R(xy)\ne {\mathrm{\text{ann}}}_R(x)\cup {\mathrm{\text{ann}}}_R(y)$. In this paper, we study the perfectness of annihilator graphs of a vast range of rings. Indeed, it is shown that if $R$ is reduced with finitely many minimal primes or nonreduced, then $\mathrm{\text{AG}}(R)$ is perfect.

Some of the published results on super strongly perfect graphs are found to be erroneous. We provide some examples and counter examples on the concepts associated with super strongly perfects.

Super strongly perfect graphs and their association with certain other classes of graphs are discussed in this paper. It is observed that every split graph is super strongly perfect. An existing result on super strongly perfect graphs is disproved providing a counter example. It is also established that if a graph G contains a cycle of odd length, then its line graph L(G) is not always super strongly perfect. Complements of cycles of length six or above are proved to be non-super strongly perfect. If a graph is strongly perfect, then it is shown that they are super strongly perfect and hence all $P_4$-free graphs are super strongly perfect.

Let $R$ be a finite commutative ring with identity, $I$ be an ideal of $R$ and $J(R)$ denotes the Jacobson radical of $R$. The ideal-based zero-divisor graph ${\mathrm{\Gamma }}_I(R)$ of $R$ is a graph with vertex set $V({\mathrm{\Gamma }}_I(R))=\{x\in R-I:xy\in I,$ for some $y\in R-I\}$ in which distinct vertices $x$ and $y$ are adjacent if and only if $xy\in I$. In this paper, we determine the diameter, girth of ${\mathrm{\Gamma }}_{J(R)}(R)$. Specifically, we classify all finite commutative nonlocal rings for which ${\mathrm{\Gamma }}_{J(R)}(R)$ is perfect. Furthermore, we discuss about the planarity, outerplanarity, genus and crosscap of ${\mathrm{\Gamma }}_{J(R)}(R)$ and characterize all of them.

A graph $G=G(V,E)$ is called $L$-list colorable if there is a vertex coloring of $G$ in which the color assigned to a vertex $v$ is chosen from a list $L(v)$ associated with this vertex. We say $G$ is $k$-choosable if all lists $L(v)$ have the cardinality $k$ and $G$ is $L$-list colorable for all possible assignments of such lists. A graph $G$ is said to be chromatic choosable if its chromatic and list chromatic numbers are equal. Investigation of $\chi$-choosable graphs is one of the open problems. In this paper, we investigate this problem for classes of perfect graphs.