Generalized graph cordiality

Oliver Pechenik; Jennifer Wise

Discussiones Mathematicae Graph Theory (2012)

  • Volume: 32, Issue: 3, page 557-567
  • ISSN: 2083-5892

Abstract

top
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₄-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₄-cordial except K_{m,n} where m,n ≡ 2(mod 4). All paths are V₄-cordial except P₄ and P₅. All cycles are V₄-cordial except C₄, C₅, and Cₖ, where k ≡ 2(mod 4). All ladders P₂ ☐ Pₖ are V₄-cordial except C₄. All prisms are V₄-cordial except P₂ ☐ Cₖ, where k ≡ 2(mod 4). All hypercubes are V₄-cordial, except C₄. 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.

How to cite

top

Oliver Pechenik, and Jennifer Wise. "Generalized graph cordiality." Discussiones Mathematicae Graph Theory 32.3 (2012): 557-567. <http://eudml.org/doc/270879>.

@article{OliverPechenik2012,
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₄-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₄-cordial except K\_\{m,n\} where m,n ≡ 2(mod 4). All paths are V₄-cordial except P₄ and P₅. All cycles are V₄-cordial except C₄, C₅, and Cₖ, where k ≡ 2(mod 4). All ladders P₂ ☐ Pₖ are V₄-cordial except C₄. All prisms are V₄-cordial except P₂ ☐ Cₖ, where k ≡ 2(mod 4). All hypercubes are V₄-cordial, except C₄. 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. },
author = {Oliver Pechenik, Jennifer Wise},
journal = {Discussiones Mathematicae Graph Theory},
keywords = {graph labeling; cordial graph; A-cordial; quasigroup; -cordial},
language = {eng},
number = {3},
pages = {557-567},
title = {Generalized graph cordiality},
url = {http://eudml.org/doc/270879},
volume = {32},
year = {2012},
}

TY - JOUR
AU - Oliver Pechenik
AU - Jennifer Wise
TI - Generalized graph cordiality
JO - Discussiones Mathematicae Graph Theory
PY - 2012
VL - 32
IS - 3
SP - 557
EP - 567
AB - 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₄-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₄-cordial except K_{m,n} where m,n ≡ 2(mod 4). All paths are V₄-cordial except P₄ and P₅. All cycles are V₄-cordial except C₄, C₅, and Cₖ, where k ≡ 2(mod 4). All ladders P₂ ☐ Pₖ are V₄-cordial except C₄. All prisms are V₄-cordial except P₂ ☐ Cₖ, where k ≡ 2(mod 4). All hypercubes are V₄-cordial, except C₄. 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.
LA - eng
KW - graph labeling; cordial graph; A-cordial; quasigroup; -cordial
UR - http://eudml.org/doc/270879
ER -

References

top
  1. [1] I. Cahit, Cordial graphs: a weaker version of graceful and harmonious graphs, Ars Combin. 23 (1987) 201-207. Zbl0616.05056
  2. [2] J.A. Gallian, A dynamic survey of graph labeling, Electron. J. Combin. 18 (2011). Zbl0953.05067
  3. [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. Zbl0499.05049
  4. [4] M. Hovey, A-cordial graphs, Discrete Math. 93 (1991) 183-194, doi: 10.1016/0012-365X(91)90254-Y. Zbl0753.05059
  5. [5] G. McAlexander, Undergraduate thesis, (Mary Baldwin College, c.2007). 
  6. [6] A. Riskin, ℤ²₂-cordiality of complete and complete bipartite graphs, (http://arxiv.org/abs/0709.0290v1), September 2007. 

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.