Full edge-friendly index sets 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$‎. ‎The full edge-friendly index set of a graph $G$ is the set of all possible edge-friendly indices of $G$‎. ‎Full edge-friendly index sets of complete bipartite graphs will be determined‎.

Keywords

Main Subjects


[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 b o oks, J. Combin. Math. Combin. Comput., 66 (2008) 43-58.

[4] S. M. Lee and H. K. Ng, A conjecture on edge cordial trees, Abstracts 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, Extreme edge-friendly indices of complete bipartite graphs, Trans. Comb., 5 no. 3 (2016) 11-21.

[8] W. C. Shiu and M. H. Ho, Full friendly index sets and full pro duct-cordial index sets of some p ermutation Petersen graphs, J. Comb. Number Theory, 5 (2013) 227-244.

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

[10] W. C. Shiu and H. Kwong, Full friendly index sets of P2×Pn, Discrete Math., 308 (2008) 3688-3693.

[11] W. C. Shiu and H. Kwong, Pro duct-cordial index and friendly index of regular graphs, Trans. Combin., 1 no. 1 (2012) 15-20.

[12] W. C. Shiu and S. M. Lee, Full friendly index sets and full pro duct-cordial index sets of twisted cylinders, J. Comb. Number Theory, 3 (2011) 209-216.

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

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

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

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

[17] D. B. West, Introduction to Graph Theory, Prentice Hall, Inc., Upp er Saddle River, NJ, 1996.