Hosoya and Merrifield-Simmons indices of some classes of corona of two graphs
Mohammad
Reyhani
Islamic Azad University, Yazd branch
author
Saeid
Alikhani
Yazd University
author
Mohammad
Iranmanesh
Yazd University
author
text
article
2012
eng
Let $G=(V,E)$ be a simple graph of order $n$ and size $m$. An $r$-matching of $G$ is a set of $r$ edges of $G$ which no two of them have common vertex. The Hosoya index $Z(G)$ of a graph $G$ is defined as the total number of its matchings. An independent set of $G$ is a set of vertices where no two vertices are adjacent. The
Merrifield-Simmons index of $G$ is defined as the total number of the independent sets of $G$. In this paper we obtain Hosoya and Merrifield-Simmons indices of corona of some graphs.
Transactions on Combinatorics
University of Isfahan
2251-8657
1
v.
4
no.
2012
1
7
http://toc.ui.ac.ir/article_1946_94db2778225c932d0361b35eb33357ba.pdf
dx.doi.org/10.22108/toc.2012.1946
Determinants of adjacency matrices of graphs
Alireza
Abdollahi
University of Isfahan
author
text
article
2012
eng
We study the set of all determinants of adjacency matrices of graphs with a given number of vertices. Using Brendan McKay's data base of small graphs, determinants of graphs with at most $9$ vertices are computed so that the number of non-isomorphic graphs with given vertices whose determinants are all equal to a number is exhibited in a table. Using an idea of M. Newman, it is proved that if $G$ is a graph with $n$ vertices, $m$ edges and $\{d_1,\dots,d_n\}$ is the set of vertex degrees of $G$, then $\gcd(2m,d^2)$ divides the determinant of the adjacency matrix of $G$, where $d=\gcd(d_1,\dots,d_n)$. Possible determinants of adjacency matrices of graphs with exactly two cycles are obtained.
Transactions on Combinatorics
University of Isfahan
2251-8657
1
v.
4
no.
2012
9
16
http://toc.ui.ac.ir/article_2041_b9579dd3348af7ab9be7b60997202498.pdf
dx.doi.org/10.22108/toc.2012.2041
A simple approach to order the multiplicative Zagreb indices of connected graphs
Mehdi
Eliasi
Department of Mathematics and Computer Science , Faculty of Khansar, Khansar, Iran
author
text
article
2012
eng
The first ($\Pi_1$) and the second $(\Pi_2$) multiplicative Zagreb indices of a connected graph $G$, with vertex set $V(G)$ and edge set $E(G)$, are defined as $\Pi_1(G) = \prod_{u \in V(G)} {d_u}^2$ and $\Pi_2(G) = \prod_{uv \inE(G)} {d_u}d_{v}$, respectively, where ${d_u}$ denotes the degree of the vertex $u$. In this paper we present a simple approach to order these indices for connected graphs on the same number of vertices. Moreover, as an application of this simple approach, we extend the known ordering of the first and the second multiplicative Zagreb indices for some classes of connected graphs.
Transactions on Combinatorics
University of Isfahan
2251-8657
1
v.
4
no.
2012
17
24
http://toc.ui.ac.ir/article_2146_61a92ef69e13895fcd946bfe86a93cd7.pdf
dx.doi.org/10.22108/toc.2012.2146
On label graphoidal covering number-I
Ismail
Sahul Hamid
DEPARTMENT OF MATHEMATICS
THE MADURA COLLEGE
MADURAI, TAMIL NADU
author
Arumugaperumal
Anitha
Department of Mathematics
Thiagarajar Engineering College
Madurai
author
text
article
2012
eng
Let $G=(V, E)$ be a graph with $p$ vertices and $q$ edges. An acyclic graphoidal cover of $G$ is a collection $\psi$ of paths in $G$ which are internally-disjoint and cover each edge of the graph exactly once. Let $f: V\rightarrow \{1, 2, \ldots, p\}$ be a bijective labeling of the vertices of $G$. Let $\uparrow\!G_f$ be the directed graph obtained by orienting the edges $uv$ of $G$ from $u$ to $v$ provided $f(u)< f(v)$. If the set $\psi_f$ of all maximal directed paths in $\uparrow\!G_f$, with directions ignored, is an acyclic graphoidal cover of $G$, then $f$ is called a \emph{graphoidal labeling} of $G$ and $G$ is called a label graphoidal graph and $\eta_l=\min\{|\psi_f|: f \ {\rm is\ a\ graphoidal\ labeling\ of}\ G\}$ is called the label graphoidal covering number of $G$. In this paper we characterize graphs for which (i) $\eta_l=q-m$, where $m$ is the number of vertices of degree 2 and (ii) $\eta_l= q$. Also, we determine the value of label graphoidal covering number for unicyclic graphs.
Transactions on Combinatorics
University of Isfahan
2251-8657
1
v.
4
no.
2012
25
33
http://toc.ui.ac.ir/article_2271_ac97bba24799ba01acbe600e2d71d194.pdf
dx.doi.org/10.22108/toc.2012.2271
Toeplitz graph decomposition
Samira
Hossein Ghorban
PhD Student
author
text
article
2012
eng
Let $n,\,t_1,\,\ldots,\,t_k$ be distinct positive integers. A Toeplitz graph $G=(V, E)$ is a graph with $V =\{1,\ldots,n\}$ and $E= \{(i,j)\mid |i-j|\in \{t_1,\ldots,t_k\}\}$. In this paper, we present some results on decomposition of Toeplitz graphs.
Transactions on Combinatorics
University of Isfahan
2251-8657
1
v.
4
no.
2012
35
41
http://toc.ui.ac.ir/article_2168_7210c55e7fbc299f5f866aad7d1281a5.pdf
dx.doi.org/10.22108/toc.2012.2168
On a relation between Szeged and Wiener indices of bipartite graphs
Lilly
Chen
Nankai University, Center for Combinatorics
author
Xueliang
Li
Nankai University
author
Mengmeng
Liu
Nankai University, Center for Combinatorics
author
Ivan
Gutman
University of Kragujevac
Kragujevac, Serbia
author
text
article
2012
eng
Hansen et. al., using the AutoGraphiX software package, conjectured that the Szeged index $Sz(G)$ and the
Wiener index $W(G)$ of a connected bipartite graph $G$ with $n \geq 4$ vertices and $m \geq n$ edges, obeys the relation $Sz(G)-W(G) \geq 4n-8$. Moreover, this bound would be the best possible. This paper offers a proof to this conjecture.
Transactions on Combinatorics
University of Isfahan
2251-8657
1
v.
4
no.
2012
43
49
http://toc.ui.ac.ir/article_2450_71f471bc2fe6a994e640ca1d23353d16.pdf
dx.doi.org/10.22108/toc.2012.2450
The Hosoya index and the Merrifield-Simmons index of some graphs
Asma
Hamzeh
Tarbiat Modares University
author
Ali
Iranmanesh
Department of Mathematics, Tarbiat Modares University, P. O. Box 14115-137, Tehran
author
Mohammad Ali
Hosseinzadeh
Tarbiat Modares University
author
Samaneh
Hossein-Zadeh
Tarbiat Modares University
author
text
article
2012
eng
The Hosoya index and the Merrifield-Simmons index are two types of graph invariants used in mathematical chemistry. In this paper, we give some formulas to compute these indices for some classes of corona product and link of two graphs. Furthermore, we obtain exact formulas of Hosoya and Merrifield-Simmons indices for the set of bicyclic graphs, caterpillars and dual star.
Transactions on Combinatorics
University of Isfahan
2251-8657
1
v.
4
no.
2012
51
60
http://toc.ui.ac.ir/article_2588_73c8b27f7c81747f22d33f7d5b65c9ba.pdf
dx.doi.org/10.22108/toc.2012.2588