Total $k$-distance domination critical graphs
Doost Ali
Mojdeh
University of Tafresh
author
A.
Sayed-Khalkhali
University of Tafresh
author
Hossein
Abdollahzadeh Ahangar
Department of Basic Science, Babol University of Technology, Babol, I.R. Iran
author
Yancai
Zhao
Wuxi City College of Vocational Technology
author
text
article
2016
eng
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 $x\in V(G)$. In this paper, we investigate some results on total $k$-distance domination-critical of graphs.
Transactions on Combinatorics
University of Isfahan
2251-8657
5
v.
3
no.
2016
1
9
http://toc.ui.ac.ir/article_11972_e981fb3fc30d07aadf6dd763425eb32b.pdf
dx.doi.org/10.22108/toc.2016.11972
Extreme edge-friendly indices of complete bipartite graphs
Wai Chee
Shiu
Hong Kong Baptist University
author
text
article
2016
eng
Let $G=(V,E)$ be a simple graph. An edge labeling $f:E\to \{0,1\}$ induces a vertex labeling $f^+:V\to Z_2$ defined by $f^+(v)\equiv \sum\limits_{uv\in E} f(uv)\pmod{2}$ for each $v \in V$, where $Z_2=\{0,1\}$ is the additive group of order 2. For $i\in\{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.
Transactions on Combinatorics
University of Isfahan
2251-8657
5
v.
3
no.
2016
11
21
http://toc.ui.ac.ir/article_12473_5cd474dbde30ab0cf85638c76d56808a.pdf
dx.doi.org/10.22108/toc.2016.12473
A new $O(m+k n \log \overline{d})$ algorithm to find the $k$ shortest paths in acyclic digraphs
Mehdi
Kadivar
Academic member of Shahrekord University
author
text
article
2016
eng
We give an algorithm, called T$^{*}$, for finding the k 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 n is the number of nodes and m 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.
Transactions on Combinatorics
University of Isfahan
2251-8657
5
v.
3
no.
2016
23
31
http://toc.ui.ac.ir/article_12602_8c4b300132a9c7b4f66cb1e49e80f1c2.pdf
dx.doi.org/10.22108/toc.2016.12602
A new construction for vertex decomposable graphs
Nasser
Hajisharifi
Department of Mathematics, Science and Research branch, Islamic Azad University, Tehran, Iran
author
Abolfazl
Tehranian
Department of Mathematics, Science and Research Branch, Islamic Azad University, Tehran, Iran
author
text
article
2016
eng
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 $G\cup W(S)$ is obtained from $G$ by adding a whisker to every vertex of $S$. We prove that if $G\setminus 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.
Transactions on Combinatorics
University of Isfahan
2251-8657
5
v.
3
no.
2016
33
38
http://toc.ui.ac.ir/article_13316_43779a03b5b9504e38c712a31b3b66d0.pdf
dx.doi.org/10.22108/toc.2016.13316
Steiner Wiener index of graph products
Yaoping
Mao
Department of Mathematics, Qinghai Normal University
author
Zhao
Wang
School of Mathematical Sciences, Beijing Normal Universit
author
Ivan
Gutman
University of Kragujevac
Kragujevac, Serbia
author
text
article
2016
eng
The Wiener index $W(G)$ of a connected graph $G$ is defined as $W(G)=\sum_{u,v\in V(G)}d_G(u,v)$ where $d_G(u,v)$ is the distance between the vertices $u$ and $v$ of $G$. For $S\subseteq V(G)$, the Steiner distance $d(S)$ of the vertices of $S$ is the minimum size of a connected subgraph of $G$ whose vertex set is $S$. The $k$-th Steiner Wiener index $SW_k(G)$ of $G$ is defined as $SW_k(G)=\sum_{\overset{S\subseteq 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.
Transactions on Combinatorics
University of Isfahan
2251-8657
5
v.
3
no.
2016
39
50
http://toc.ui.ac.ir/article_13499_e8db28e08ac92c0269c208de9cd50572.pdf
dx.doi.org/10.22108/toc.2016.13499