University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
1
1
2012
03
01
Note on edge distance-balanced graphs
1
6
EN
M.
Tavakoli
m_tavakoli@ferdowsi.um.ac.ir
H.
Yousefi-Azari
hyousefi@ut.ac.ir
Ali Reza
Ashrafi
ashrafi@kashanu.ac.ir
10.22108/toc.2012.86
Edge distance-balanced graphs are graphs in which for every edge $e = uv$ the number of edges closer to vertex $u$ than to vertex $v$ is equal to the number of edges closer to $v$ than to $u$. In this paper, we study this property under some graph operations.
Edge distance-balanced,vertex distance-balanced,graph operation
http://toc.ui.ac.ir/article_86.html
http://toc.ui.ac.ir/article_86_41c9776f55f12410740dfdfe4fa080ec.pdf
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
1
1
2012
03
01
$k$-Tuple total domination and mycieleskian graphs
7
13
EN
Adel
P. Kazemi
UMA
(University of Mohaghegh Ardabili)
adelpkazemi@yahoo.com
10.22108/toc.2012.333
Let $k$ be a positive integer. A subset $S$ of $V(G)$ in a graph $G$ is a $k$-tuple total dominating set of $G$ if every vertex of $G$ has at least $k$ neighbors in $S$. The $k$-tuple total domination number $gamma _{times k,t}(G)$ of $G$ is the minimum cardinality of a $k$-tuple total dominating set of $G$. In this paper for a given graph $G$ with minimum degree at least $k$, we find some sharp lower and upper bounds on the $k$-tuple total domination number of the $m$ -Mycieleskian graph $mu _{m}(G)$ of $G$ in terms on $k$ and $gamma _{times k,t}(G)$. Specially we give the sharp bounds $gamma _{times k,t}(G)+1$ and $gamma _{times k,t}(G)+k$ for $gamma _{times k,t}(mu _1(G))$, and characterize graphs with $gamma _{times k,t}(mu _1(G))=gamma _{times k,t}(G)+1$.
$k$-tuple total dominating set,k-tuple total domination number,$m$-Mycieleskian graph
http://toc.ui.ac.ir/article_333.html
http://toc.ui.ac.ir/article_333_1c8f4a659abb4fec82b4bd7691dba941.pdf
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
1
1
2012
03
01
Product-cordial index and friendly index of regular graphs
15
20
EN
Wai Chee
Shiu
Hong Kong Baptist University
wcshiu@hkbu.edu.hk
Kwong
Harris
State University of New York at Fredonia
kwong@fredonia.edu
10.22108/toc.2012.482
Let $G=(V,E)$ be a connected simple graph. A labeling $f: Vto Z_2$ induces two edge labelings $f^+, f^*: E to Z_2$ defined by $f^+(xy) = f(x)+f(y)$ and $f^*(xy) = f(x)f(y)$ for each $xy in E$. For $i in Z_2$, let $v_f(i) = |f^{-1}(i)|$, $e_{f^+}(i) = |(f^{+})^{-1}(i)|$ and $e_{f^*}(i) = |(f^*)^{-1}(i)|$. A labeling $f$ is called friendly if $|v_f(1)-v_f(0)| le 1$. For a friendly labeling $f$ of a graph $G$, the friendly index of $G$ under $f$ is defined by $i^+_f(G) = e_{f^+}(1)-e_{f^+}(0)$. The set ${i^+_f(G);|;f mbox{ is a friendly labeling of} G}$ is called the full friendly index set of $G$. Also, the product-cordial index of $G$ under $f$ is defined by $i^*_f(G) = e_{f^*}(1)-e_{f^*}(0)$. The set ${i^*_f(G);|;f mbox{ is a friendly labeling of} G}$ is called the full product-cordial index set of $G$. In this paper, we find a relation between the friendly index and the product-cordial index of a regular graph. As applications, we will determine the full product-cordial index sets of torus graphs which was asked by Kwong, Lee and Ng in 2010; and those of cycles.
friendly labeling,friendly index set,product-cordial index,product-cordial index set,Torus
http://toc.ui.ac.ir/article_482.html
http://toc.ui.ac.ir/article_482_0f0636556a2c2f345a1e9f8e54e0934d.pdf
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
1
1
2012
03
01
Minimal, vertex minimal and commonality minimal CN-dominating graphs
21
29
EN
Anwar Saleh
Alwardi
University of Mysore
a_wardi@hotmail.com
N. D.
Soner
University of Mysore
ndsoner@yahoo.co.in
10.22108/toc.2012.497
We define minimal CN-dominating graph $mathbf {MCN}(G)$, commonality minimal CN-dominating graph $mathbf {CMCN}(G)$ and vertex minimal CN-dominating graph $mathbf {M_{v}CN}(G)$, characterizations are given for graph $G$ for which the newly defined graphs are connected. Further serval new results are developed relating to these graphs.
CN-Minimal Dominating (Graph),commonality minimal CN-dominating (graph),vertex minimal CN-dominating (graph)
http://toc.ui.ac.ir/article_497.html
http://toc.ui.ac.ir/article_497_907cf6e71495c5344706494bd6c58cf4.pdf
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
1
1
2012
03
01
A note on star coloring of central graph of bipartite graph and corona graph of complete graph with path and cycle
31
34
EN
V. J.
Vernold
Anna University of Technology Tirunelveli
vernoldvivin@yahoo.in
M.
Venkatachalam
R.V.S Faculty of Engineering
venkatmaths@gmail.com
10.22108/toc.2012.636
In this paper, we find the star chromatic number of central graph of complete bipartite graph and corona graph of complete graph with path and cycle.
central graph,corona graph,star coloring
http://toc.ui.ac.ir/article_636.html
http://toc.ui.ac.ir/article_636_96d78bc268249e8f330d8a4596ed626b.pdf
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
1
1
2012
03
01
Complexity indices for the travelling salesman problem and data mining
35
43
EN
Dragos
Cvetković
ecvetkod@etf.rs
10.22108/toc.2012.723
we extend our previous work on complexity indices for the travelling salesman problem (TSP), summarized in cite{CvCK3}, using graph spectral techniques of data mining. A complexity index is an invariant of an instance $I$ by which we can predict the execution time of an exact algorithm for TSP for $I$. We consider the symmetric travelling salesman problem with instances $I$ represented by complete graphs $G$ with distances between vertices (cities) as edge weights (lengths). Intuitively, the hardness of an instance $G$ depends on the distribution of short edges within $G$. Therefore we consider some short edge subgraphs of $G$ (minimal spanning tree, critical connected subgraph, and several others) as non-weighted graphs and several their invariants as potential complexity indices. Here spectral invariants (e.g. spectral radius of the adjacency matrix) play an important role since, in general, there are intimate relations between eigenvalues and the structure of a graph. Since hidden details of short edge subgraphs really determine the hardness of the instance, we use techniques of data mining to find them. In particular, spectral clustering algorithms are used including information obtained from the spectral gap in Laplacian spectra of short edge subgraphs.
Travelling Salesman Problem,Spectral clustering algorithms,Hamiltonian cycle
http://toc.ui.ac.ir/article_723.html
http://toc.ui.ac.ir/article_723_a83c593b06f18b6cdb9a9a465d56305d.pdf
University of Isfahan
Transactions on Combinatorics
2251-8657
2251-8665
1
1
2012
03
01
On the total domatic number of regular graphs
45
51
EN
H.
Aram
Azarbaijan University of Tarbiat Moallem
h.aram@azer.edu
S. M.
Sheikholeslami
Azarbaijan University of Tarbiat Moallem
s.m.sheikholeslami@azaruniv.edu
L.
Volkmann
RWTH-Aachen University
volkm@math2.rwth-aachen.de
10.22108/toc.2012.760
A set $S$ of vertices of a graph $G=(V,E)$ without isolated vertex is a total dominating set if every vertex of $V(G)$ is adjacent to some vertex in $S$. The total domatic number of a graph $G$ is the maximum number of total dominating sets into which the vertex set of $G$ can be partitioned. We show that the total domatic number of a random $r$-regular graph is almost surely at most $r-1$, and that for 3-regular random graphs, the total domatic number is almost surely equal to 2. We also give a lower bound on the total domatic number of a graph in terms of order, minimum degree and maximum degree. As a corollary, we obtain the result that the total domatic number of an $r$-regular graph is at least $r/(3ln(r))$.
total dominating set,total domination number,total domatic number,Regular graph
http://toc.ui.ac.ir/article_760.html
http://toc.ui.ac.ir/article_760_362cc9c41ad1def424bd149103450c49.pdf