University of IsfahanTransactions on Combinatorics2251-86573420141201Randic incidence energy of graphs19557310.22108/toc.2014.5573ENRanGuNankai UniversityFeiHuangNankai UniversityXueliangLiCenter for Combinatorics, Nankai University, Tianjin 300071, ChinaJournal Article20140529Let $G$ be a simple graph with vertex set $V(G) = \{v_1, v_2,\ldots, v_n\}$ and edge set $E(G) = \{e_1, e_2,\ldots, e_m\}$. Similar to the Randi\'c matrix, here we introduce the Randi\'c incidence matrix of a graph $G$, denoted by $I_R(G)$, which is defined as the $n\times m$ matrix whose $(i,j)$-entry is $(d_i)^{-\frac{1}{2}}$ if $v_i$ is incident to $e_j$ and $0$ otherwise. Naturally, the Randi\'c incidence energy $I_RE$ of $G$ is the sum of the singular values of $I_R(G)$. We establish lower and upper bounds for the Randic incidence energy. Graphs for which these bounds are best possible are characterized. Moreover, we investigate the relation between the Randic incidence energy of a graph and that of its subgraphs. Also we give a sharp upper bound for the Randic incidence energy of a bipartite graph and determine the trees with the maximum Randic incidence energy among all $n$-vertex trees. As a result, some results are very different from those for incidence energy.https://toc.ui.ac.ir/article_5573_68f2261c2087d1f09fb34c2f8de4b053.pdfUniversity of IsfahanTransactions on Combinatorics2251-86573420141201On Lict sigraphs1118562710.22108/toc.2014.5627ENVeenaMathadUniversity of Mysore0000-0002-6621-9596Kishori P.NarayankarMangalore UniversityJournal Article20130620A signed graph (marked graph) is an ordered pair $S=(G,\sigma)$ $(S=(G,\mu))$, where $G=(V,E)$ is a graph called the underlying graph of $S$ and $\sigma:E\rightarrow\{+,-\}$ $(\mu:V\rightarrow\{+,-\})$ is a function. For a graph $G$, $V(G), E(G)$ and $C(G)$ denote its vertex set, edge set and cut-vertex set, respectively. The lict graph $L_{c}(G)$ of a graph $G=(V,E)$ is defined as the graph having vertex set $E(G)\cup C(G)$ in which two vertices are adjacent if and only if they correspond to adjacent edges of $G$ or one corresponds to an edge $e_{i}$ of $G$ and the other corresponds to a cut-vertex $c_{j}$ of $G$ such that $e_{i}$ is incident with $c_{j}$. In this paper, we introduce lict sigraphs, as a natural extension of the notion of lict graph to the realm of signed graphs. We show that every lict sigraph is balanced. We characterize signed graphs $S$ and $S^{'}$ for which $S\sim L_{c}(S)$, $\eta(S)\sim L_{c}(S)$, $L(S)\sim L_{c}(S')$, $J(S)\sim L_{c}(S^{'})$ and $T_{1}(S)\sim L_{c}(S^{'})$, where $\eta(S)$, $L(S)$, $J(S)$ and $T_{1}(S)$ are negation, line graph, jump graph and semitotal line sigraph of $S$, respectively, and $\sim$ means switching equivalence.https://toc.ui.ac.ir/article_5627_e7de2aef7c26e21d97bfaf79f2112406.pdfUniversity of IsfahanTransactions on Combinatorics2251-86573420141201The geodetic domination number for the product of graphs1930575010.22108/toc.2014.5750ENS. RobinsonChellathuraiScott Christian CollegeS. PadmaVijayaUniversity College of Engineering NagercoilJournal Article20140306A subset $S$ of vertices in a graph $G$ is called a geodetic set if every vertex not in $S$ lies on a shortest path between two vertices from $S$. A subset $D$ of vertices in $G$ is called dominating set if every vertex not in $D$ has at least one neighbor in $D$. A geodetic dominating set $S$ is both a geodetic and a dominating set. The geodetic (domination, geodetic domination) number $g(G) (\gamma(G),\gamma_g(G))$ of $G$ is the minimum cardinality among all geodetic (dominating, geodetic dominating) sets in $G$. In this paper, we show that if a triangle free graph $G$ has minimum degree at least 2 and $g(G) = 2$, then $\gamma _g(G) = \gamma(G)$. It is shown, for every nontrivial connected graph $G$ with $\gamma(G) = 2$ and $diam(G) > 3$, that $\gamma_g(G) > g(G)$. The lower bound for the geodetic domination number of Cartesian product graphs is proved. Geodetic domination number of product of cycles (paths) are determined. In this work, we also determine some bounds and exact values of the geodetic domination number of strong product of graphs.https://toc.ui.ac.ir/article_5750_87bdcf395fa6e3fd7e39a154bc0f1442.pdfUniversity of IsfahanTransactions on Combinatorics2251-86573420141201Comparing the second multiplicative Zagreb coindex with some graph invariants3141595110.22108/toc.2014.5951ENFarzanehFalahati NezhadScience and Research Branch, Islamic Azad UniversityAliIranmaneshDepartment of Mathematics, Tarbiat Modares University, P. O. Box 14115-137, TehranAbolfazlTehranianScience and Research Branch, Islamic Azad UniversityMahdiehAzariKazerun Branch, Islamic Azad UniversityJournal Article20140716The second multiplicative Zagreb coindex of a simple graph $G$ is defined as: $${\overline{\Pi{}}}_2\left(G\right)=\prod_{uv\not\in{}E(G)}d_G\left(u\right)d_G\left(v\right),$$ where $d_G\left(u\right)$ denotes the degree of the vertex $u$ of $G$. In this paper, we compare $\overline{{\Pi}}_2$-index with some well-known graph invariants such as the Wiener index, Schultz index, eccentric connectivity index, total eccentricity, eccentric-distance sum, the first Zagreb index and coindex and the first multiplicative Zagreb index and coindex.https://toc.ui.ac.ir/article_5951_503474fbf2c1d8a206d3e6dd20f8a32e.pdfUniversity of IsfahanTransactions on Combinatorics2251-86573420141201Perfect state transfer in unitary Cayley graphs over local rings4354597410.22108/toc.2014.5974ENYotsananMeemarkChulalongkorn UniversitySongponSriwongsaChulalongkorn UniversityJournal Article20140321In this work, using eigenvalues and eigenvectors of unitary Cayley graphs over finite local rings and elementary linear algebra, we characterize which local rings allowing PST occurring in its unitary Cayley graph. Moreover, we have some developments when $R$ is a product of local rings.https://toc.ui.ac.ir/article_5974_ee7986b6514f7db7db00ebf91f7de927.pdfUniversity of IsfahanTransactions on Combinatorics2251-86573420141201Complete solution to a conjecture of Zhang-Liu-Zhou5558598610.22108/toc.2014.5986ENMostafaTavakoliFerdowsi University of MashhadF.RahbarniaFerdowsi University of MashhadM.MirzavaziriFerdowsi University of MashhadA. R.AshrafiUniversity of KashanJournal Article20140120Let $d_{n,m}=\big[\frac{2n+1-\sqrt{17+8(m-n)}}{2}\big]$ and $E_{n,m}$ be the graph obtained from a path $P_{d_{n,m}+1}=v_0v_1 \cdots v_{d_{n,m}}$ by joining each vertex of $K_{n-d_{n,m}-1}$ to $v_{d_{n,m}}$ and $v_{d_{n,m}-1}$, and by joining $m-n+1-{n-d_{n,m}\choose 2}$ vertices of $K_{n-d_{n,m}-1}$ to $v_{d_{n,m}-2}$. Zhang, Liu and Zhou [On the maximal eccentric connectivity indices of graphs, Appl. Math. J. Chinese Univ., in press] conjectured that if $d_{n,m}\geqslant 3$, then $E_{n,m}$ is the graph with maximal eccentric connectivity index among all connected graph with $n$ vertices and $m$ edges. In this note, we prove this conjecture. Moreover, we present the graph with maximal eccentric connectivity index among the connected graphs with $n$ vertices. Finally, the minimum of this graph invariant in the classes of tricyclic and tetracyclic graphs are computed.https://toc.ui.ac.ir/article_5986_740f215bc6659e95ccaa77c44e50e504.pdf