Chromatic and clique numbers of a class of perfect graphs
Mohammad Reza
Fander
Azad University, Chaluse Branch
author
text
article
2015
eng
Let $p$ be a prime number and $n$ be a positive integer. The graph $G_p(n)$ is a graph with vertex set $[n]=\{1, 2,\ldots, n\}$, in which there is an arc from $u$ to $v$ if and only if $u\neq v$ and $p\nmid u+v$. In this paper it is shown that $G_p(n)$ is a perfect graph. In addition, an explicit formula for the chromatic number of such graph is given.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
4
no.
2015
1
4
http://toc.ui.ac.ir/article_7340_88e0ca90702ff396dfd3dfe5d04f5bcc.pdf
dx.doi.org/10.22108/toc.2015.7340
On the harmonic index of graph operations
B.
Shwetha Shetty
Don Bosco Institute of Technology, Bangalore-78, India
author
V.
Lokesha
Dept.of Mathematics, VSK University,Bellary
Karnataka
author
P. S.
Ranjini
Don Bosco Institute of Technology, Bangalore-78, India
author
text
article
2015
eng
The harmonic index of a connected graph $G$, denoted by $H(G)$, is defined as $H(G)=\sum_{uv\in E(G)}\frac{2}{d_u+d_v}$ where $d_v$ is the degree of a vertex $v$ in G. In this paper, expressions for the Harary indices of the join, corona product, Cartesian product, composition and symmetric difference of graphs are derived.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
4
no.
2015
5
14
http://toc.ui.ac.ir/article_7389_3e9ec295be34a42ee71a0570cc2fbfa9.pdf
dx.doi.org/10.22108/toc.2015.7389
A dynamic domination problem in trees
William
Klostermeyer
School of Computing
University of North Florida
author
Christina
Mynhardt
Department of Mathematics and Statistics
University of Victoria
author
text
article
2015
eng
We consider a dynamic domination problem for graphs in which an infinite sequence of attacks occur at vertices with guards and the guard at the attacked vertex is required to vacate the vertex by moving to a neighboring vertex with no guard. Other guards are allowed to move at the same time, and before and after each attack and the resulting guard movements, the vertices containing guards form a dominating set of the graph. The minimum number of guards that can successfully defend the graph against such an arbitrary sequence of attacks is the m-eviction number. This parameter lies between the domination and independence numbers of the graph. We characterize the classes of trees for which the m-eviction number equals the domination number and the independence number, respectively.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
4
no.
2015
15
31
http://toc.ui.ac.ir/article_7590_fbf0dbf66e3b8321a9266cd46dabc47a.pdf
dx.doi.org/10.22108/toc.2015.7590
The resistance distance and the Kirchhoff index of the $k$-th semi total point graphs
Denglan
Cui
Department of Mathematics
Hunan Nornal University
Changsha, Hunan 410081
author
Yaoping
Hou
Department of Mathematics
Hunan Normal University
Changsha, Hunan,410081
author
text
article
2015
eng
The $k$-th semi-total point graph $R^k(G)$ of a graph $G$, is a graph obtained from $G$ by adding $k$ vertices corresponding to each edge and connecting them to the endpoints of the edge considered. In this paper, we obtain formulas for the resistance distance and Kirchhoff index of $R^k(G).$
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
4
no.
2015
33
41
http://toc.ui.ac.ir/article_7767_d003df08d9fc1d3ea3e0f98ad110cc1b.pdf
dx.doi.org/10.22108/toc.2015.7767
Broadcast domination in Tori
Kian Wee
Soh
Dept of Mathematics, National University of Singapore
author
Khee-Meng
Koh
Department of Mathematics
National University of Singapore
author
text
article
2015
eng
A broadcast on a graph $G$ is a function $f : V(G) \rightarrow \{0, 1,\dots, diam(G)\}$ such that for every vertex $v \in V(G)$, $f(v) \leq e(v)$, where $diam(G)$ is the diameter of $G$, and $e(v)$ is the eccentricity of $v$. In addition, if every vertex hears the broadcast, then the broadcast is a dominating broadcast. The cost of a broadcast $f$ is the value $\sigma(f) = \sum_{v \in V(G)} f(v)$. In this paper we determine the minimum cost of a dominating broadcast (also known as the broadcast domination number) for a torus $C_{m} \;\Box\; C_{n}$.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
4
no.
2015
43
53
http://toc.ui.ac.ir/article_7654_d69d40ef7aab331d7b142121c88012e9.pdf
dx.doi.org/10.22108/toc.2015.7654
A classification of finite groups with integral bi-Cayley graphs
Majid
Arezoomand
Departmant of Mathematical Sciences, Isfahan University of Technology, Isfahan, Iran
author
Bijan
Taeri
Department of Mathematics, Isfahan University of Technology, Isfahan, Iran
author
text
article
2015
eng
The bi-Cayley graph of a finite group $G$ with respect to a subset $S\subseteq G$, which is denoted by $BCay(G,S)$, is the graph with vertex set $G\times\{1,2\}$ and edge set $\{\{(x,1), (sx,2)\}\mid x\in G, \ s\in S\}$. A finite group $G$ is called a \textit{bi-Cayley integral group} if for any subset $S$ of $G$, $BCay(G,S)$ is a graph with integer eigenvalues. In this paper we prove that a finite group $G$ is a bi-Cayley integral group if and only if $G$ is isomorphic to one of the groups $\Bbb Z_2^k$, for some $k$, $\Bbb Z_3$ or $S_3$.
Transactions on Combinatorics
University of Isfahan
2251-8657
4
v.
4
no.
2015
55
61
http://toc.ui.ac.ir/article_7807_741eee48891d7eafd3a189c9e3afd5fb.pdf
dx.doi.org/10.22108/toc.2015.7807