eng
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
2015-12-01
4
4
1
4
7340
Chromatic and clique numbers of a class of perfect graphs
Mohammad Reza Fander
mohamadrezafander@yahoo.com
1
Azad University, Chaluse Branch
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 $uneq v$ and $pnmid 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.
http://toc.ui.ac.ir/article_7340_88e0ca90702ff396dfd3dfe5d04f5bcc.pdf
perfect graph
Clique number
chromatic number
eng
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
2015-12-01
4
4
5
14
7389
On the harmonic index of graph operations
B. Shwetha Shetty
1
V. Lokesha
v.lokesha@gmail.com
2
P. S. Ranjini
3
Don Bosco Institute of Technology, Bangalore-78, India
Dept.of Mathematics, VSK University,Bellary Karnataka
Don Bosco Institute of Technology, Bangalore-78, India
The harmonic index of a connected graph $G$, denoted by $H(G)$, is defined as $H(G)=sum_{uvin 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.
http://toc.ui.ac.ir/article_7389_3e9ec295be34a42ee71a0570cc2fbfa9.pdf
harmonic index
Graph operations
Topological indices
graphs
eng
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
2015-12-01
4
4
15
31
7590
A dynamic domination problem in trees
William Klostermeyer
klostermeyer@hotmail.com
1
Christina Mynhardt
kieka@uvic.ca
2
School of Computing
University of North Florida
Department of Mathematics and Statistics University of Victoria
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.
http://toc.ui.ac.ir/article_7590_fbf0dbf66e3b8321a9266cd46dabc47a.pdf
graph protection
eternal domination
Domination Number
Independence number
eng
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
2015-12-01
4
4
33
41
7767
The resistance distance and the Kirchhoff index of the $k$-th semi total point graphs
Denglan Cui
909721364@qq.com
1
Yaoping Hou
yphou@hunnu.edu.cn
2
Department of Mathematics
Hunan Nornal University
Changsha, Hunan 410081
Department of Mathematics Hunan Normal University Changsha, Hunan,410081
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).$
http://toc.ui.ac.ir/article_7767_d003df08d9fc1d3ea3e0f98ad110cc1b.pdf
Resistance distance
Kirchhoff index
derived graph
eng
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
2015-12-01
4
4
43
53
7654
Broadcast domination in Tori
Kian Wee Soh
skw45610@gmail.com
1
Khee-Meng Koh
matkohkm@nus.edu.sg
2
Dept of Mathematics, National University of Singapore
Department of Mathematics
National University of Singapore
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}$.
http://toc.ui.ac.ir/article_7654_d69d40ef7aab331d7b142121c88012e9.pdf
Broadcast
Dominating broadcast
Broadcast domination
Torus
Radial graph
eng
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
2015-12-01
4
4
55
61
7807
A classification of finite groups with integral bi-Cayley graphs
Majid Arezoomand
arezoomand@math.iut.ac.ir
1
Bijan Taeri
b.taeri@cc.iut.ac.ir
2
Departmant of Mathematical Sciences, Isfahan University of Technology, Isfahan, Iran
Department of Mathematics, Isfahan University of Technology, Isfahan, Iran
The bi-Cayley graph of a finite group $G$ with respect to a subset $Ssubseteq G$, which is denoted by $BCay(G,S)$, is the graph with vertex set $Gtimes{1,2}$ and edge set ${{(x,1), (sx,2)}mid xin G, sin 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$.
http://toc.ui.ac.ir/article_7807_741eee48891d7eafd3a189c9e3afd5fb.pdf
Bi-Cayley graph
Integer Eigenvalues
Representations of finite groups