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

RIGHTS & PERMISSIONS

Higher Education Press