# Cordial Labeling of 4-regular graphs

My group is working on *Cordial Labeling of 4-regular graphs. We were wondering if someone here knows whether this study has been done before. If not, can someone help me how to know if the given 4-regular graph admits a cordial labeling or not.

A function f:V→{0,1} is said to be a cordial labeling if each edge uv has the label │f(u)-f(v)│ such that, (1)The number of vertices labeled ‘0’ and the number of vertices labeled ‘1’ differ by at most “one” denoted as ││V1│-│V0││≤1. (2)The number of edges labeled ‘0’ and the number of edges labeled ‘1’ differ by at most “one” denoted as ││E1│-│E0││≤1. A graph which admits cordial labelings is called cordial.

My second question is, If i was given a 4-regular graph, how will I know if it admits a cordial labeling.

• If you want to get a useful answer, you might want to define what is meant by cordial labeling. Also when you say "the given 4-regular graph", are you referring to a particular graph? or do you mean a given 4-regular graph? – Anthony Quas Aug 25 '16 at 9:16
• A function f:V→{0,1} is said to be a cordial labeling if each edge uv has the label │f(u)-f(v)│ such that, (1)The number of vertices labeled ‘0’ and the number of vertices labeled ‘1’ differ by at most “one” denoted as ││V1│-│V0││≤1. (2)The number of edges labeled ‘0’ and the number of edges labeled ‘1’ differ by at most “one” denoted as ││E1│-│E0││≤1. A graph which admits cordial labeling is called cordial. i'm sorry, i mean, a given 4-regular graph.. – Melanie Atendido Aug 25 '16 at 9:18
• @MelanieAtendido, you should add this definition in the post. Also, please help us understand your second question about "the given 4-regular" graph. It is very vague. – Amir Sagiv Aug 25 '16 at 9:20
• I'm sorry, I edited it. – Melanie Atendido Aug 25 '16 at 9:28
• Since a 4-regular graph has an even number of edges, it seems to me that $||E_0|-|E_1||\le 1$ implies $|E_0|=|E_1|$. Correct? – Brendan McKay Aug 25 '16 at 12:18

Eulerian graphs with $e$ edges cannot be cordial unless $e$ is a multiple of $4$ so don't bother looking at $4$-regular graphs with an odd number of vertices. (This is in Cahit's original paper that is freely available online).