2012
1
1
1
51
Note on edge distancebalanced graphs
2
2
Edge distancebalanced 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.
1

1
6


M.
Tavakoli
Iran
m_tavakoli@ferdowsi.um.ac.ir


H.
YousefiAzari
Iran
hyousefi@ut.ac.ir


Ali Reza
Ashrafi
Iran
ashrafi@kashanu.ac.ir
Edge distancebalanced
vertex distancebalanced
graph operation
[M. Aouchiche and P. Hansen (2010). on a conjecture about the Szeged index. European J . Combin.. 31, 16621666## A. T. Balaban, P. V. Khadikar and S. Aziz (2010). Comparison of topological indices based on iterated `sum' versus `product' operations. Iran. J. Math. Chem.. 1, 4360## T. Doslic (2008). VertexWeighted Wiener polynomials for composite graphs,. Ars Math. Contemp.. 1, 6680## K. Handa (1999). Bipartite graphs with balanced (a,b)partitions. Ars Combin.. 51, 113119## A. Ilic, S. Klavzar and M. Milanovic (2010). on distancebalanced graphs. European J. Combin.. 31, 733737## W. Imrich, S. Klavzar (2000). Product Graphs: Structure and Recognition. Wiley, New York, USA. ## J. Jerebic, S. Klavzar, D. F. Rall (2008). Distancebalanced graphs. Ann. Combin.. 12, 7179## M. H. Khalifeh, H. YousefiAzari, A. R. Ashrafi (2008). The hyperWiener index of graph operations. Comput. Math. Appl.. 56, 14021407## M. K. Khalifeh, H. YousefiAzari, A. R. Ashrafi and S. G. Wagner (2009). Some new results on distancebased graph invariants. European J. Combin.. 30, 11491163## D. Stevanovic (2001). Hosoya polynomial of composite graphs. Discrete Math.. 235, 237244## M. Tavakoli and H. YousefiAzari (2010). Computing PI and hyperWiener indices of corona product of some graphs. Iran. J. Math. Chem.. 1, 131135## W. Yan, B.Y Yang, Y.N Yeh (2007). The behavior of Wiener indices and polynomials of graphs under five graph decorations. Appl. Math. Lett.. 20, 290295## Y. N. Yeh and I. Gutman (1994). On the sum of all distances in composite graphs. Discrete Math.. 135, 359365## ]
$k$Tuple total domination and mycieleskian graphs
2
2
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$.
1

7
13


Adel
P. Kazemi
UMA
(University of Mohaghegh Ardabili)
UMA
(University of Mohaghegh Ardabili)
Iran
adelpkazemi@yahoo.com
$k$tuple total dominating set
ktuple total domination number
$m$Mycieleskian graph
[F. Harary, T. W. Haynes (2000). Double domination in graphs. Ars Combin.. 55, 201213## T. W. Haynes, S. T. Hedetniemi and P. J. Slater (1998). Fundamentals of Domination in Graphs. Marcel Dekker, New York. ## T. W. Haynes, S. T. Hedetniemi, and P. J. Slater (1998). Domination in Graphs: Advanced Topics. Marcel Dekker, New York. ## M. A. Henning, A. P. Kazemi (2010). ktuple total domination in graphs. Discrete Applied Mathematics. 158, 10061011## M. A. Henning, A. P. Kazemi ktuple total domination in cross product graphs. Journal of Combinatorial Optimization. ## A. P. Kazemi ktuple total domination in complementary prisms. ISRN Discrete Mathematics. ## C. Tardif (2001). Fractional chromatic numbers of cones over graphs. J. Graph Theory. 38, 8794## D. B. West (2001). Introduction to Graph Theory, (2nd edition). Prentice Hall, USA. ## ]
Productcordial index and friendly index of regular graphs
2
2
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 productcordial 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 productcordial index set of $G$. In this paper, we find a relation between the friendly index and the productcordial index of a regular graph. As applications, we will determine the full productcordial index sets of torus graphs which was asked by Kwong, Lee and Ng in 2010; and those of cycles.
1

15
20


Wai Chee
Shiu
Hong Kong Baptist University
Hong Kong Baptist University
Hong Kong
wcshiu@hkbu.edu.hk


Kwong
Harris
State University of New York at Fredonia
State University of New York at Fredonia
United States of America
kwong@fredonia.edu
friendly labeling
friendly index set
productcordial index
productcordial index set
Torus
[J.A. Bondy and U.S.R. Murty (1976). Graph Theory with Applications. Macmillan (Publisher). ## M. Gao (2010). The edge difference sets of the direct product of two paths. MSc thesis, Fuzhou Unviersity. ## H. Kwong and SM. Lee (2008). On friendly index sets of generalized books. J. Combin. Math. Combin. Comput.. 66, 4358## H. Kwong, SM. Lee and H.K. Ng (2008). On friendly index sets of 2regular graphs. Discrete Math.. 308, 55225532## H. Kwong, SM. Lee and H.K. Ng (2010). On productcordial index sets of cylinders. Congr. Numer.. 206, 139150## SM. Lee and H.K. Ng (2008). On friendly index sets of bipartite graphs. Ars Combin.. 86, 257271## E. Salehi (2010). PClabeling of a graph and its PCset. Bull. Inst. Combin. Appl.. 58, 112121## E. Salehi and D. Bayot (2010). The friendly index set of P_m X P_n. Util. Math.. 81, 121130## E. Salehi and SM. Lee (2006). On friendly index sets of trees. Congr. Numer.. 178, 173183## W.C. Shiu and H. Kwong (2008). Full friendly index sets of P_2 X P_n. Discrete Math.. 308, 36883693## W.C. Shiu and M.H. Ling (2007). Extreme friendly indices of C_m X C_n. Congr. Numer.. 188, 175182## W.C. Shiu and M.H. Ling (2010). Full friendly index sets of Cartesian products of two cycles,. Acta Math. Sin. (Engl. Ser.). 26, 12331244## W.C. Shiu and F.S. Wong (2009). Extreme friendly indices of C_m X P_n. Congr. Numer.. 197, 6575## W.C. Shiu and F.S. Wong (2012). Full friendly index sets of cylinder graphs. Australas. J. Combin.. 52, 141162## F.S. Wong (2010). Full friendly index sets of the Cartesian product of cycles and
paths. M. Phil. Thesis, Department of Mathematics,
Hong Kong Baptist University. ## ]
Minimal, vertex minimal and commonality minimal CNdominating graphs
2
2
We define minimal CNdominating graph $mathbf {MCN}(G)$, commonality minimal CNdominating graph $mathbf {CMCN}(G)$ and vertex minimal CNdominating 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.
1

21
29


Anwar Saleh
Alwardi
University of Mysore
University of Mysore
India
a_wardi@hotmail.com


N. D.
Soner
University of Mysore
University of Mysore
India
ndsoner@yahoo.co.in
CNMinimal Dominating (Graph)
commonality minimal CNdominating (graph)
vertex minimal CNdominating (graph)
[Anwar Alwardi, N. D. Soner and Karam Ebadi (2011). On the Common neighbourhood domination number. Journal Of Computer And Mathematical Sciences. 2 (3) , 574556## F. Harary (1969). Graph theory. AddisonWesley Publishing Co., Reading, Mass.Menlo Park, Calif.London,. ## T. W. Haynes, S. T. Hedetniemi and P. J. Slater (1998). Fundamentals of domination in graphs. Monographs and Textbooks in Pure and Applied Mathematics, Marcel Dekker, Inc.. 208## S. M. Hedetneimi, S. T. Hedetneimi, R. C. Laskar, L. Markus and P. J. Slater (2006). Disjoint dominating sets in graphs.. Proc. Int. Conf. on Disc. Math., IMIIISc. , 88101## V. R. Kulli and B. Janakiram (1995). The Minimal Dominating Graph. 28, 1215## V. R. Kulli, B. Janakiram and K. M. Niranjan (1996). The commonality minimal Dominating Graph. Indian J. Pure. appl. Math.. 27, 193196## V. R. Kulli, B. Janakiram and K. M. Niranjan (2002). The Vertex Minimal Dominating Graph. Acta Ciencia Indica.. 28, 435440## V. R. Kulli, B. Janakiram and K. M. Niranjan (2004). The Dominating Graph. Graph Theory Notes of New York, New York Academy of Sciences. 46, 58## H. B. Walikar, B. D. Acharya and E. Sampathkumar (1979). Recent developments in the theory of domination in graphs. Mehta Research instutute, Alahabad, MRI Lecture Notes in Math.. 1## ]
A note on star coloring of central graph of bipartite graph and corona graph of complete graph with path and cycle
2
2
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.
1

31
34


V. J.
Vernold
Anna University of Technology Tirunelveli
Anna University of Technology Tirunelveli
India
vernoldvivin@yahoo.in


M.
Venkatachalam
R.V.S Faculty of Engineering
R.V.S Faculty of Engineering
India
venkatmaths@gmail.com
central graph
corona graph
star coloring
[Michael O. Albertson, Glenn G. Chappell, H. A. Kierstead, Andr'{e} K"{u}ndgen and Radhika Ramamurthi (2004). Coloring with no 2colored $P_4$'s. The Electronic Journal of Combinatorics, Paper $#$ R26, 13. 11## Branko Gr"{u}nbaum (1973). Acyclic colorings of planar graphs. Israel J. Math.. 14, 390408## Guillaume Fertin, Andr'{e} Raspaud and Bruce Reed (2004). Star coloring of graphs. J. Graph Theory (3). 47, 163182## Thomas F. Coleman and JinYi Cai (1986). he cyclic coloring problem and estimation of sparse Hessian matrices. SIAM J. Alg. Disc. Math.. 7, 221235## Thomas F. Coleman and Jorge J. Mor'{e} (1984). Estimation of sparse Hessian matrices and graph coloring problems. Mathematical
Programming (3). 28, 243270## Vivin J. Vernold (2007). Harmonious coloring of total graphs, $n$leaf, central graphs and circumdetic graphs. Ph.D. Thesis,
Bharathiar University,Coimbatore, India.. ## Vivin J. Vernold, M. Venkatachalam and Ali M.M. Akbar (2009). A note on achromatic coloring of star graph families. Filomat (3). 23, 251255## Vivin J. Vernold and M. Venkatachalam he $b$chromatic number of corona graphs. Utilitas Mathematica (to appear).. ## ]
Complexity indices for the travelling salesman problem and data mining
2
2
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 nonweighted 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.
1

35
43


Dragos
Cvetković
Serbia
ecvetkod@etf.rs
Travelling Salesman Problem
Spectral clustering algorithms
Hamiltonian cycle
[B. Ashok and T.K. Patra (2010). Locating phase transitions in computationally hard problems. J. Physics, to appear. ## D. Cvetkovi' c, M. v Cangalovi' c and V. Kovav cevi' cVujv
ci' c (1999). Semidefinite programming methods for the symmetric
travelling salesman problem. Integer Programming and
Combinatorial Optimization, Proc. 7th Internat. IPCO Conf.Graz,
Austria, June 1999, Lecture Notes Comp. Sci. 1610, Springer,
Berlin. , 126136## D. Cvetkovi' c, M. v Cangalovi' c and V. Kovav cevi' cVujv
ci' c (1999). Complexity indices for the travelling salesman problem
based on a semidefinite relaxation. SYMOPIS '99, Proc. XXVI
Yugoslav Symp. Operations Research, Beograd. , 177180## D. Cvetkovi' c, M. v Cangalovi' c and V. Kovav cevi' cVujv
ci' c (2004). Optimization and highly informative graph invariants. Two Topics in Mathematics, ed. B.Stankovi' c, Zbornik radova
10(18), Matemativ cki institut SANU, Beograd. , 539## D. Cvetkovi'c, P. Rowlinson and S. K. Simi'c (2009). An Introduction to the Theory of Graph Spectra. Cambridge
University Press, Cambridge. ## D. Cvetkovi' c and S.K. Simi' c (2011). Graph spectra in computer
science. Linear Algebra Appl.. 434, 15451562## M. Fiedler (1973). Algebraic connectivity of graphs. Czech. J. Math.. 23 (98) , 298305## G. Gutin and A. Punnen (2002). The Travelling Salesman
Problem and Its Variations. Kluwer Academic Publishers,
Dordrecht. ## E.L. Lawler, J.K. Lenstra, A.H.G. Rinnoy Kan and D.B. Shmoys (1985). The Traveling Salesman Problem. John Wiley and Sons,
Chichester  New York  Brisbane  Toronto  Singapore. ## K. Ko, P. Orponen, U. Sch" oning and O. Watanabe (1986). What is a
hard instance of a computational problem ?. Structure in
Complexity Theory. Conf. 1986, Lecture Notes in Computer Science,
Springer. , 197217## U. von Luxburg (2007). A tutorial on spectral clustering. Stat.
Comput.. 17, 395416## C.R. Reeves and A.V. Eremeev (2004). Statistical analysis of local
search landscapes. J. Oper. Res. Soc.. 55, 687693## B.D. Reyck and W. Herroelen (1996). On the use of the complexity index as
a measure of complexity in activity networks. Europ. J. Oper.
Res.. 91, 347366## R. Sawilla (2008). A survey of data mining of graphs using spectral
graph theory. Defence R&D Canada, Ottawa, Technical Memorandum
TM 2008317, Ottawa. ## ]
On the total domatic number of regular graphs
2
2
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 $r1$, and that for 3regular 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))$.
1

45
51


H.
Aram
Azarbaijan University of Tarbiat Moallem
Azarbaijan University of Tarbiat Moallem
Iran
h.aram@azer.edu


S. M.
Sheikholeslami
Azarbaijan University of Tarbiat Moallem
Azarbaijan University of Tarbiat Moallem
Iran
s.m.sheikholeslami@azaruniv.edu


L.
Volkmann
RWTHAachen University
RWTHAachen University
Germany
volkm@math2.rwthaachen.de
total dominating set
total domination number
total domatic number
Regular graph
[N. Alon (1990). Transversal numbers of uniform hypergraphs. Graphs Combin.. 6, 14## S. Arumugam and A. Thuraiswamy (1998). Total domatic number of a graph. Indian J. Pure Appl. Math.. 29, 513515## E. A. Bender and E. R. Canfield (1978). The asymptotic number of labeled
graphs with given degree sequences. J. Combin. Theory Ser. A. 24, 296307## I. Bouchemakh and S. Ouatiki (2009). On the domatic and the total domatic numbers of
the 2section graph of the orderinterval hypergraph of a finite
poset. Discrete Math.. 309, 36743679## E. J. Cockayne, R. M. Dawes, S. T. Hedetniemi (1980). Total domination in graphs. Networks. 10, 211219## P. Dankelmann, N. J. Calkin (2004). The Domatic Number of Regular Graphs. Ars Combin.. 73, 247255## T. W. Haynes, S. T. Hedetniemi, P. J. Slater (1998). Fundamentals of Domination in Graphs. Marcel Dekker, Inc., New York. ## T. W. Haynes, S. T. Hedetniemi, P. J. Slater, editors (1998). Domination in Graphs,
Advanced Topics. Marcel Dekker, Inc., New York. ## D. B. West (2000). Introduction to Graph Theory. PrenticeHall, Inc. ## N. C. Wormald (1999). Models of Random Regular Graphs. In: Surveys in
Combinatorics 1999 (J.D. Lamb and D.A. Preece, eds.),
London Mathematical Society Lecture Notes Series , Cambridge
University Press, Cambridge. 267, 239298## B. Zelinka (1988). Total domatic number of cacti. Math. Slovaca. 38, 207214## B. Zelinka (1989). Total domatic number and degrees of vertices of a graph. Math. Slovaca. 39, 711## ]