Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
3
2
2018
12
01
Classification of rings with toroidal annihilating-ideal graph
93
119
EN
Selvakumar
Krishnan
0000-0002-0405-3287
Department of Mathematics
Manonmaniam Sundaranar University
Tirunelveli
selva_158@yahoo.co.in
Subbulakshmi
P
Manonmaniam Sundaranar University
shunlaxmi@gmail.com
10.22049/cco.2018.26060.1072
Let $R$ be a non-domain commutative ring with identity and $A^*(R)$ be the set of non-zero ideals with non-zero annihilators. We call an ideal $I$ of $R$, an annihilating-ideal if there exists a non-zero ideal $J$ of $R$ such that $IJ =(0)$. The annihilating-ideal graph of $R$ is defined as the graph $AG(R)$ with the vertex set $A^*(R)$ and two distinct vertices $I$ and $J$ are adjacent if and only if $IJ =(0)$. In this paper, we characterize all commutative Artinian nonlocal rings $R$ for which $AG(R)$ has genus one.
annihilating-ideal,planar,genus,local ring,annihilating-ideal graph
http://comb-opt.azaruniv.ac.ir/article_13745.html
http://comb-opt.azaruniv.ac.ir/article_13745_64b16e21db453555d1fe39afe192d7e5.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
3
2
2018
12
01
On the harmonic index of bicyclic graphs
121
142
EN
Reza
Rasi
Azarbaijan Shahid Madani University
r.rasi@azaruniv.edu
10.22049/cco.2018.26171.1081
The harmonic index of a graph $G$, denoted by $H(G)$, is defined as the sum of weights $2/[d(u)+d(v)]$ over all edges $uv$ of $G$, where $d(u)$ denotes the degree of a vertex $u$. Hu and Zhou [Y. Hu and X. Zhou, WSEAS Trans. Math. {\bf 12} (2013) 716--726] proved that for any bicyclic graph $G$ of order $ngeq 4$, $H(G)\le \frac{n}{2}-\frac{1}{15}$ and characterize all extremal bicyclic graphs. In this paper, we prove that for any bicyclic graph $G$ of order $n\geq 4$ and maximum degree $\Delta$, <br />$$H(G)\le \left\{\begin{array}{ll}<br />\frac{3n-1}{6} & {\rm if}\; \Delta=4\\<br />&\\<br />2(\frac{2\Delta-n-3}{\Delta+1}+\frac{n-\Delta+3}{\Delta+2}+\frac{1}{2}+\frac{n-\Delta-1}{3}) & {\rm if}\;\Delta\ge 5 \;{\rm and}\; n\le 2\Delta-4\\<br />&\\<br />2(\frac{\Delta}{\Delta+2}+\frac{\Delta-4}{3}+\frac{n-2\Delta+4}{4}) & {\rm if}\;\Delta\ge 5 \;{\rm and}\;n\ge 2\Delta-3,\\<br />\end{array}\right.$$ <br />and characterize all extreme bicyclic graphs.
harmonic index,bicyclic graphs,trees
http://comb-opt.azaruniv.ac.ir/article_13746.html
http://comb-opt.azaruniv.ac.ir/article_13746_f0c613a9e6610951d57150aad863731f.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
3
2
2018
12
01
Complexity and approximation ratio of semitotal domination in graphs
143
150
EN
Zehui
Shao
0000-0003-0764-4135
Guangzhou University
zshao@gzhu.edu.cn
Pu
Wu
Guangzhou University
wupu@mail.cdu.edu.cn
10.22049/cco.2018.25987.1065
A set $S \subseteq V(G)$ is a semitotal dominating set of a graph $G$ if it is a dominating set of $G$ and every vertex in $S$ is within distance 2 of another vertex of $S$. The semitotal domination number $\gamma_{t2}(G)$ is the minimum cardinality of a semitotal dominating set of $G$. We show that the semitotal domination problem is APX-complete for bounded-degree graphs, and the semitotal domination problem in any graph of maximum degree $\Delta$ can be approximated with an approximation ratio of $2+\ln(\Delta-1)$.
semitotal domination,APX-complete,NP-completeness
http://comb-opt.azaruniv.ac.ir/article_13748.html
http://comb-opt.azaruniv.ac.ir/article_13748_70d5d03f125812cbc3dc8d0aec38312f.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
3
2
2018
12
01
Some results on a supergraph of the comaximal ideal graph of a commutative ring
151
172
EN
S.
Visweswaran
Saurashtra University
s_visweswaran2006@yahoo.co.in
Jaydeep
Parejiya
Department of Mathematics, Saurashtra University, Rajkot, Gujarat, India.
parejiyajay@gmail.com
10.22049/cco.2018.26132.1079
Let $R$ be a commutative ring with identity such that $R$ admits at least two maximal ideals. In this article, we associate a graph with $R$ whose vertex set is the set of all proper ideals $I$ of $R$ such that $I$ is not contained in the Jacobson radical of $R$ and distinct vertices $I$ and $J$ are joined by an edge if and only if $I$ and $J$ are not comparable under the inclusion relation. The aim of this article is to study the interplay between the graph-theoretic properties of this graph and the ring-theoretic properties of the ring $R$.
Chained ring,Bipartite graph,Split graph,Complemented graph
http://comb-opt.azaruniv.ac.ir/article_13778.html
http://comb-opt.azaruniv.ac.ir/article_13778_c5b20d65e49415f10224ec5da091faf6.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
3
2
2018
12
01
Lower bounds on the signed (total) $k$-domination number
173
178
EN
Lutz
Volkmann
0000-0003-3496-277X
RWTH Aachen University
volkm@math2.rwth-aachen.de
10.22049/cco.2018.26055.1071
Let $G$ be a graph with vertex set $V(G)$. For any integer $k\ge 1$, a signed (total) $k$-dominating function is a function $f: V(G) \rightarrow \{ -1, 1\}$ satisfying $\sum_{x\in N[v]}f(x)\ge k$ ($\sum_{x\in N(v)}f(x)\ge k$) for every $v\in V(G)$, where $N(v)$ is the neighborhood of $v$ and $N[v]=N(v)\cup\{v\}$. The minimum of the values $\sum_{v\in V(G)}f(v)$, taken over all signed (total) $k$-dominating functions $f$, is called the signed (total) $k$-domination number. The clique number of a graph $G$ is the maximum cardinality of a complete subgraph of $G$. In this note we present some new sharp lower bounds on the signed (total) $k$-domination number depending on the clique number of the graph. Our results improve some known bounds.
signed $k$-dominating function,signed $k$-domination number,clique number
http://comb-opt.azaruniv.ac.ir/article_13779.html
http://comb-opt.azaruniv.ac.ir/article_13779_039e0161b2a16abce42b7a252a65cb4e.pdf
Azarbaijan Shahid Madani University
Communications in Combinatorics and Optimization
2538-2128
2538-2136
3
2
2018
12
01
Leap Zagreb indices of trees and unicyclic graphs
179
194
EN
Ivan
Gutman
0000-0001-9681-1550
University of Kragujevac
gutman@kg.ac.rs
Zehui
Shao
0000-0003-0764-4135
Guangzhou University
zshao@gzhu.edu.cn
Zepeng
Li
Lanzhou University
lizp@lzu.edu.cn
ShaohuiShaohui
Wang
Department of Mathematics and Computer Science, Adelphi University,
Garden City, NY, USA.
shaohuiwang@yahoo.com
Pu
We
Guangzhou University,
puwu1997@126.com
10.22049/cco.2018.26285.1092
By $d(v|G)$ and $d_2(v|G)$ are denoted the number of first and second neighbors of the vertex $v$ of the graph $G$. The first, second, and third leap Zagreb indices of $G$ are defined as $LM_1(G) = \sum_{v \in V(G)} d_2(v|G)^2$, $LM_2(G) = \sum_{uv \in E(G)} d_2(u|G)\,d_2(v|G)$, and $LM_3(G) = \sum_{v \in V(G)} d(v|G)\,d_2(v|G)$, respectively. In this paper, we generalize the results of Naji et al. [Commun. Combin. Optim. {\bf 2} (2017), 99--117], pertaining to trees and unicyclic graphs. In addition, we determine upper and lower bounds on these leap Zagreb indices and characterize the extremal graphs.
Leap Zagreb index,Zagreb index,degree (of vertex)
http://comb-opt.azaruniv.ac.ir/article_13782.html
http://comb-opt.azaruniv.ac.ir/article_13782_6ae3457e7f09b8f6c913dd0fa53fa742.pdf