University of Isfahan Transactions on Combinatorics 2251-8657 5 3 2016 09 01 Total \$k\$-distance domination critical graphs 1 9 11972 10.22108/toc.2016.11972 EN Doost Ali Mojdeh University of Tafresh A. Sayed-Khalkhali University of Tafresh Hossein Abdollahzadeh Ahangar Department of Basic Science, Babol University of Technology, Babol, I.R. Iran Yancai Zhao Wuxi City College of Vocational Technology Journal Article 2015 07 11 A set \$S\$ of vertices in a graph \$G=(V,E)\$ is called a total‎ ‎\$k\$-distance dominating set if every vertex in \$V\$ is within‎ ‎distance \$k\$ of a vertex in \$S\$‎. ‎A graph \$G\$ is total \$k\$-distance‎ ‎domination-critical if \$gamma_{t}^{k} (G‎ - ‎x) < gamma_{t}^{k}‎ ‎(G)\$ for any vertex \$xin V(G)\$‎. ‎In this paper‎, ‎we investigate some results on total \$k\$-distance domination-critical of graphs‎. http://toc.ui.ac.ir/article_11972_e981fb3fc30d07aadf6dd763425eb32b.pdf
University of Isfahan Transactions on Combinatorics 2251-8657 5 3 2016 09 01 Extreme edge-friendly indices of complete bipartite graphs 11 21 12473 10.22108/toc.2016.12473 EN Wai Chee Shiu Hong Kong Baptist University Journal Article 2015 09 30 Let \$G=(V,E)\$ be a simple graph‎. ‎An edge labeling \$f:Eto {0,1}\$ induces a vertex labeling \$f^+:Vto Z_2\$ defined by \$f^+(v)equiv sumlimits_{uvin E} f(uv)pmod{2}\$ for each \$v in V\$‎, ‎where \$Z_2={0,1}\$ is the additive group of order 2‎. ‎For \$iin{0,1}\$‎, ‎let‎ ‎\$e_f(i)=|f^{-1}(i)|\$ and \$v_f(i)=|(f^+)^{-1}(i)|\$‎. ‎A labeling \$f\$ is called edge-friendly if‎ ‎\$|e_f(1)-e_f(0)|le 1\$‎. ‎\$I_f(G)=v_f(1)-v_f(0)\$ is called the edge-friendly index of \$G\$ under an edge-friendly labeling \$f\$‎. ‎Extreme values of edge-friendly index of complete bipartite graphs will be determined‎. http://toc.ui.ac.ir/article_12473_5cd474dbde30ab0cf85638c76d56808a.pdf
University of Isfahan Transactions on Combinatorics 2251-8657 5 3 2016 09 01 A new \$O(m+k n log overline{d})\$ algorithm to find the \$k\$ shortest paths in acyclic digraphs 23 31 12602 10.22108/toc.2016.12602 EN Mehdi Kadivar Academic member of Shahrekord University Journal Article 2015 07 25 ‎We give an algorithm‎, ‎called T\$^{*}\$‎, ‎for finding the <em>k</em> shortest simple paths connecting a certain‎ ‎pair of nodes‎, ‎\$s\$ and \$t\$‎, ‎in a acyclic digraph‎. ‎First the nodes of the graph are labeled according to the topological ordering‎. ‎Then for node \$i\$ an ordered list of simple \$s-i\$ paths is created‎. ‎The length of the list is at most \$k\$ and it is created by using tournament trees‎. ‎We prove the correctness of T\$^{*}\$ and show that its worst-case complexity is \$O(m+k n log overline{d})\$ in which<em> n</em> is the number of nodes and <em>m</em> is the number of arcs and \$overline{d}\$ is the mean degree of the graph‎. ‎The algorithm has a space complexity of \$O(kn)\$ which entails an important improvement in space complexity‎. ‎An experimental evaluation of T\$^{*}\$ is presented which confirms the advantage of our algorithm compared to the‎ ‎most efficient \$k\$ shortest paths algorithms known so far‎. http://toc.ui.ac.ir/article_12602_8c4b300132a9c7b4f66cb1e49e80f1c2.pdf
University of Isfahan Transactions on Combinatorics 2251-8657 5 3 2016 09 01 A new construction for vertex decomposable graphs 33 38 13316 10.22108/toc.2016.13316 EN Nasser Hajisharifi Department of Mathematics, Science and Research branch, Islamic Azad University, Tehran, Iran Abolfazl Tehranian Department of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, Iran Journal Article 2014 11 24 Let \$G\$ be a finite simple graph on the vertex set \$V(G)\$ and let \$S subseteq V(G)\$. Adding a whisker to \$G\$ at \$x\$ means adding a new vertex \$y\$ and edge \$xy\$ to \$G\$ where \$x in V(G)\$. The graph \$Gcup W(S)\$ is obtained from \$G\$ by adding a whisker to every vertex of \$S\$. We prove that if \$Gsetminus S\$ is either a graph with no chordless cycle of length other than \$3\$ or \$5\$, chordal graph or \$C_5\$, then \$G cup W(S)\$ is a vertex decomposable graph. http://toc.ui.ac.ir/article_13316_43779a03b5b9504e38c712a31b3b66d0.pdf
University of Isfahan Transactions on Combinatorics 2251-8657 5 3 2016 09 01 Steiner Wiener index of graph products 39 50 13499 10.22108/toc.2016.13499 EN Yaoping Mao Department of Mathematics, Qinghai Normal University Zhao Wang School of Mathematical Sciences, Beijing Normal Universit Ivan Gutman University of Kragujevac Kragujevac, Serbia Journal Article 2015 12 31 The Wiener index \$W(G)\$ of a connected graph \$G\$‎ ‎is defined as \$W(G)=sum_{u,vin V(G)}d_G(u,v)\$‎ ‎where \$d_G(u,v)\$ is the distance between the vertices \$u\$ and \$v\$ of‎ ‎\$G\$‎. ‎For \$Ssubseteq V(G)\$‎, ‎the <em>Steiner distance</em> \$d(S)\$ of‎ ‎the vertices of \$S\$ is the minimum size of a connected subgraph of‎ ‎\$G\$ whose vertex set is \$S\$‎. ‎The  \$k\$-<em>th Steiner Wiener index</em>‎ ‎\$SW_k(G)\$ of \$G\$ is defined as‎ ‎\$SW_k(G)=sum_{overset{Ssubseteq V(G)}{|S|=k}} d(S)\$‎. ‎We establish‎ ‎expressions for the \$k\$-th Steiner Wiener index on the join‎, ‎corona‎, ‎cluster‎, ‎lexicographical product‎, ‎and Cartesian product of graphs‎. http://toc.ui.ac.ir/article_13499_e8db28e08ac92c0269c208de9cd50572.pdf