Discussiones Mathematicae Graph Theory 32(3) (2012)
557-567

doi: 10.7151/dmgt.1626

## Generalized Graph Cordiality

Oliver Pechenik and Jennifer Wise
Department of Mathematics University of Illinois Urbana, IL, 61801 |

## Abstract

Hovey introduced A-cordial labelings in [4] as a simultaneous generalization of cordial and harmonious labelings. If A is an abelian group, then a labeling f: V(G) → A of the vertices of some graph G induces an edge-labeling on G; the edge uv receives the label f(u) + f(v). A graph G is *A-cordial* if there is a vertex-labeling such that (1) the vertex label classes differ in size by at most one and (2) the induced edge label classes differ in size by at most one.
Research on A-cordiality has focused on the case where A is cyclic. In this paper, we investigate V_{4}-cordiality of many families of graphs, namely complete bipartite graphs, paths, cycles, ladders, prisms, and hypercubes. We find that all complete bipartite graphs are V_{4}-cordial except K_{m,n} where m,n ≡ 2(mod 4). All paths are V_{4}-cordial except P_{4} and P_{5}. All cycles are V_{4}-cordial except C_{4}, C_{5}, and C_{k}, where k ≡ 2(mod 4). All ladders P_{2} ^{[¯]} P_{k} are V_{4}-cordial except C_{4}. All prisms are V_{4}-cordial except P_{2} ^{[¯]} C_{k}, where k ≡ 2(mod 4). All hypercubes are V_{4}-cordial, except C_{4}.

Finally, we introduce a generalization of A-cordiality involving digraphs and quasigroups, and we show that there are infinitely many Q-cordial digraphs for every quasigroup Q.

**Keywords:** graph labeling, cordial graph, *A*-cordial, quasigroup

**2010 Mathematics Subject Classification:** 05C78, 05C25.

## References

[1] | I. Cahit, * Cordial graphs: a weaker version of graceful and harmonious graphs*, Ars Combin. ** 23** (1987) 201--207. |

[2] | J.A. Gallian, * A dynamic survey of graph labeling*, Electron. J. Combin. ** 18** (2011) }. |

[3] | R.L. Graham and N.J.A. Sloane, * On additive bases and harmonious graphs*, SIAM J. Algebraic Discrete Methods ** 1** (1980) 382--404, doi: 10.1137/0601045. |

[4] | M. Hovey, * {**A*}, Discrete Math. ** 93** (1991) 183--194, doi: 10.1016/0012-365X(91)90254-Y. |

[5] | G. McAlexander, Undergraduate thesis, (Mary Baldwin College, c.2007). |

[6] | A. Riskin, * **ℤ*_{2}^{2}-cordiality of complete and complete bipartite graphs, (http://arxiv.org/abs/0709.0290v1), September 2007. |

Received 30 March 2011

Revised 30 September 2011

Accepted 30 September 2011