# Extreme edge-friendly indices of complete bipartite graphs

Document Type : Research Paper

Author

Hong Kong Baptist University

Abstract

Let $G=(V,E)$ be a simple graph‎. ‎An edge labeling $f:E\to \{0,1\}$ induces a vertex labeling $f^+:V\to Z_2$ defined by $f^+(v)\equiv \sum\limits_{uv\in E} f(uv)\pmod{2}$ for each $v \in V$‎, ‎where $Z_2=\{0,1\}$ is the additive group of order 2‎. ‎For $i\in\{0,1\}$‎, ‎let‎ ‎$e_f(i)=|f^{-1}(i)|$ and $v_f(i)=|(f^+)^{-1}(i)|$‎. ‎A labeling $f$ is called edge-friendly if‎ ‎$|e_f(1)-e_f(0)|\le 1$‎. ‎$I_f(G)=v_f(1)-v_f(0)$ is called the edge-friendly index of $G$ under an edge-friendly labeling $f$‎. ‎Extreme values of edge-friendly index of complete bipartite graphs will be determined‎.

Keywords

Main Subjects

#### References

[1] K. L. Collins and M. Hovey, Most graphs are edge cordial, Ars Combin., 30 (1990) 289–295.

[2] H. Kwong, S. M. Lee and H. K. Ng, On friendly index sets of 2-regular graphs, Discrete Math., 308 (2008) 5522–5532.

[3] H. Kwong and S. M. Lee, On friendly index sets of generalized books, J. Combin. Math. Combin. Comput., 66 (2008) 43–58.

[4] S. M. Lee and H. K. Ng, A conjecture on edge cordial trees, Amer. Math. Soc., 9 (1988) 286–287.

[5] S. M. Lee and H. K. Ng, On friendly index sets of bipartite graphs, Ars Combin., 86 (2008) 257–271.

[6] E. Salehi and S. M. Lee, On friendly index sets of trees, Congr. Numer., 178 (2006) 173–183.

[7] W. C. Shiu and M. H. Ho, Full friendly index sets and full product-cordial index sets of some permutation Petersen graphs, J. Comb. Number Theory, 5 (2013) 227–244.

[8] W. C. Shiu and M. H. Ho, Full friendly index sets of slender and flat cylinder graphs, Trans. Comb., 2 no. 4 (2013) 63–80.

[9] W. C. Shiu and H. Kwong, Full friendly index sets of ${P}_2times{P}_n$, Discrete Math., 308 (2008) 3688–3693.

[10] W. C. Shiu and H. Kwong, Product-cordial index and friendly index of regular graphs, Trans. Comb., 1 no. 1 (2012) 15–20.

[11] W. C. Shiu and S. M. Lee, Full friendly index sets and full product-cordial index sets of twisted cylinders, J. Comb. Number Theory, 3 (2012) 209–216.

[12] W. C. Shiu and M. H. Ling, Full friendly index sets of Cartesian products of two cycles, Acta Math. Sin. (Engl. Ser.), 26 (2010) 1233–1244.

[13] W. C. Shiu and F. S. Wong, Full friendly index sets of cylinder graphs, Australas. J. Combin., 52 (2012) 141–162.

[14] D. Sinha and J. Kaur, Full friendly index set-I, Discrete Appl. Math., 161 (2013) 1262–1274.

[15] D. Sinha and J. Kaur, Full friendly index set-II, J. Combin. Math. Combin. Comput., 79 (2011) 65–75.

[16] D. West, Introduction to Graph Theory,Prentice Hall, Inc., Upper Saddle River, NJ, 1996.

### History

• Receive Date: 30 September 2015
• Revise Date: 11 January 2016
• Accept Date: 12 January 2016
• Published Online: 01 September 2016