Product-cordial index and friendly index of regular graphs

Document Type: Research Paper

Authors

1 Hong Kong Baptist University

2 State University of New York at Fredonia

Abstract

Let $G=(V,E)$ be a connected simple graph‎. ‎A labeling $f‎: ‎V\to 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‎.

Keywords

Main Subjects


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 S-M. Lee (2008). On friendly index sets of generalized books. J. Combin. Math. Combin. Comput.. 66, 43-58
H. Kwong, S-M. Lee and H.K. Ng (2008). On friendly index sets of 2-regular graphs. Discrete Math.. 308, 5522-5532
H. Kwong, S-M. Lee and H.K. Ng (2010). On product-cordial index sets of cylinders. Congr. Numer.. 206, 139-150
S-M. Lee and H.K. Ng (2008). On friendly index sets of bipartite graphs. Ars Combin.. 86, 257-271
E. Salehi (2010). PC-labeling of a graph and its PC-set. Bull. Inst. Combin. Appl.. 58, 112-121
E. Salehi and D. Bayot (2010). The friendly index set of P_m X P_n. Util. Math.. 81, 121-130
E. Salehi and S-M. Lee (2006). On friendly index sets of trees. Congr. Numer.. 178, 173-183
W.C. Shiu and H. Kwong (2008). Full friendly index sets of P_2 X P_n. Discrete Math.. 308, 3688-3693
W.C. Shiu and M.H. Ling (2007). Extreme friendly indices of C_m X C_n. Congr. Numer.. 188, 175-182
W.C. Shiu and M.H. Ling (2010). Full friendly index sets of Cartesian products of two cycles,. Acta Math. Sin. (Engl. Ser.). 26, 1233-1244
W.C. Shiu and F.S. Wong (2009). Extreme friendly indices of C_m X P_n. Congr. Numer.. 197, 65-75
W.C. Shiu and F.S. Wong (2012). Full friendly index sets of cylinder graphs. Australas. J. Combin.. 52, 141-162
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.