Full friendly index sets of mC_n

Abstract

Let G be a connected simple graph with vertex set V(G) and edge set E(G). A binary vertex labeling f:V(G)\to {\mathbb{Z}}_2, is said to be friendly if the number of vertices with different labels differs by at most one. Each vertex friendly labeling f induces an edge labeling f^{\ast }:E(G)\to {\mathbb{Z}}_2, defined by f^{\ast }(xy)= f(x)+f(y) for each xy\in E(G). Let e_{f^{\ast }}(i)=\{e\in E(G):f^{\ast }(e)= i\}. The full friendly index set of G, denoted by FFI(G), is the set \{e_{f^{\ast }}(1)-e_{f^{\ast }}(0):f\text{is}\text{friendly}\}. In this paper, we determine the full friendly index set of a family of cycle union graphs which are edge subdivisions of P_2\times P_n.

Graphical abstract

Keywords

vertex labeling / friendly labeling / full friendly index set / partition / bisection

References

[1] Gallian J A . A dynamic survey of graph labeling. Electronic Journal of Combinatorics, 2009, 19 : 1– 219

[2] Cahit I . Cordial graphs: a weaker version of graceful and harmonious graphs. Ars Combinatoria, 1987, 23 : 201– 207

[3] Hovey M . A-cordial graphs. Discrete Mathematics, 1991, 93( 2−3): 183– 194

[4] Chartrand G , Lee S M , Zhang P . Uniformly cordial graphs. Discrete Mathematics, 2006, 306( 8−9): 726– 737

[5] Shiu W C , Kwong H . Full friendly index sets of P2×Pn. Discrete Mathematics, 2008, 308( 16): 3688– 3693

[6] Hou J , Yan J . Max-Bisections of H-free graphs. Discrete Mathematics, 2020, 343( 1): 111590–

[7] Liu Q , Dong X , Chen H , Wang Y . IncPregel: an incremental graph parallel computation model. Frontiers of Computer Science, 2018, 12( 6): 1076– 1089

[8] Wang Z , Chen Q , Suo B , Pan W , Li Z . Reducing partition skew on MapReduce: an incremental allocation approach. Frontiers of Computer Science, 2019, 13( 5): 960– 975

[9] Xu B . Graph partitions: recent progresses and some open problems. Advances in Mathematics (China), 2016, 45 : 1– 20

[10] Sinha D , Kaur J . Full friendly index set-I. Discrete Applied Mathematics, 2013, 161( 9): 1262– 1274

[11] Shiu W C , Ling M H . Full friendly index sets of Cartesian products of two cycles. Acta Mathematica Sinica-English Series, 2010, 26( 7): 1233– 1244

[12] Shiu W C , Wong F S . Full friendly index sets of cylinder graphs. Australasian Journal of Combinatorics, 2012, 52 : 141– 162

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

[14] Shiu W C , Ho M H . Full friendly index sets of slender and flat cylinder graphs. Transactions on Combinatorics, 2013, 2( 4): 63– 80

Acknowledgements

We would like to thank the referees for providing some very helpful suggestions for revising this paper. This work was supported partly by the National Natural Science Foundation of China (Grant Nos. 11801149, 11801148). S. Wu was also partially supported by the Doctoral Fund of Henan Polytechnic University (B2018-55).

RIGHTS & PERMISSIONS

2022 Higher Education Press