-1
$\begingroup$

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.

Thanks in advance.

please help, it will be much appreciated.

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.

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Anthony Quas Aug 25 '16 at 9:16
  • $\begingroup$ 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.. $\endgroup$ – Melanie Atendido Aug 25 '16 at 9:18
  • 1
    $\begingroup$ @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. $\endgroup$ – Amir Sagiv Aug 25 '16 at 9:20
  • $\begingroup$ I'm sorry, I edited it. $\endgroup$ – Melanie Atendido Aug 25 '16 at 9:28
  • 1
    $\begingroup$ 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? $\endgroup$ – Brendan McKay Aug 25 '16 at 12:18
2
$\begingroup$

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).

$\endgroup$
  • $\begingroup$ Do you know what is the use/sense of graph labelings such as labeling like this, cordial labeling? Or what/where that is applies to? And why is it that the graph should be labeled (0,1) to be considered cordial? I mean, will it affect anything? or will have an error if it's not 0 and 1? Thanks. $\endgroup$ – Melanie Atendido Sep 4 '16 at 16:11
  • 1
    $\begingroup$ There are hundreds of different types of graph labelling, some of which are motivated by a particular real-world application, while others seem to be totally made up just in order to have something to study. I think you'd have to research the origins of cordial labelling to see whether it is interesting and useful to you or not. I don't do anything with graph labellings myself. $\endgroup$ – Gordon Royle Sep 5 '16 at 3:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.