All trees are six-cordial

Published: 2017-04-10  |  Journal: Electronic Journal of Graph Theory and Applications, Volume 5, 2017

Authors

DOI: 10.5614/ejgta.2017.5.1.3

ISSN: 2338-2287

Publisher: The Institute for Research and Community Services (LPPM) ITB

Abstract

For any integer $k>0$, a tree $T$ is $k$-cordial if there exists a labeling of the vertices of $T$ by $\mathbb{Z}_k$, inducing edge-weights as the sum modulo $k$ of the labels on incident vertices to a given edge, which furthermore satisfies the following conditions: \begin{enumerate} \item Each label appears on at most one more vertex than any other label. \item Each edge-weight appears on at most one more edge than any other edge-weight. \end{enumerate} Mark Hovey (1991) conjectured that all trees are $k$-cordial for any integer $k$. Cahit (1987) had shown earlier that all trees are $2$-cordial and Hovey proved that all trees are $3,4,$ and $5$-cordial. We show that all trees are six-cordial by an adjustment of the test proposed by Hovey to show all trees are $k$-cordial.

Keith Driscoll, Elliot Krop, Michelle Nguyen

Department of Mathematics, Clayton State University, 2000 Clayton State Blvd. Morrow, Georgia, 30260 USA

keithdriscoll@clayton.edu, elliotkrop@clayton.edu, ngannguyen@clayton.edu

For any integer k > 0, a tree T is k-cordial if there exists a labeling of the vertices of T by Zk, inducing edge-weights as the sum modulo k of the labels on incident vertices to a given edge, which furthermore satisfies the following conditions:

  • 1. Each label appears on at most one more vertex than any other label.
  • 2. Each edge-weight appears on at most one more edge than any other edge-weight.

Mark Hovey (1991) conjectured that all trees are k-cordial for any integer k. Cahit (1987) had shown earlier that all trees are 2-cordial and Hovey proved that all trees are 3, 4, and 5-cordial. We show that all trees are six-cordial by an adjustment of the test proposed by Hovey to show all trees are k-cordial.

Keywords: graph labeling, cordial, k-cordial, trees Mathematics Subject Classification : 05C78 DOI:10.5614/ejgta.2017.5.1.3

1. Introduction

All graphs will be finite and simple. For basic graph theoretic notation and definitions, we refer the reader to D. West [9]. For a survey of graph labeling problems and results, see Gallian [3].

For any tree T and any integer k > 0, a k-cordial labeling of T is a function f : V (T) → Zk inducing an edge-weighting also denoted by f, defined by f(uv) = f(u) + f(v) (mod k) for any edge (uv) of T, which satisfy the following conditions:

Received: 18 October 2016, Revised 14 January 2017, Accepted: 30 January 2017.

  • 1. Each label appears on at most one more vertex than any other label.
  • 2. Each weight appears on at most one more edge than any other edge-weight.

In other words, if for any a ∈ Zk we define va and ea as the number of vertices and edges, respectively, which are labeled a, then the above conditions can be rewritten as

  • 1. |va − vb| ≤ 1 for any distinct a, b ∈ Zk
  • 2. |ea − eb| ≤ 1 for any distinct a, b ∈ Zk

Cahit [1] was the first to define 2-cordial labelings (which he called cordial) as a simplification of graceful and harmonious labelings. Motivated by the Graceful Tree Conjecture of Rosa [8] and the Harmonious Tree Conjecture (HTC) of Graham and Sloane [5], he showed that all trees are 2-cordial. The extension of the definition to groups is due to Hovey [6] who also showed that all trees are 3, 4, and 5-cordial. Hovey conjectured that trees are k-cordial for all k and that all graphs are 3-cordial. In the last twenty-five years there has been little progress towards a solution to either conjecture. However, Cichacz, Gorlich, and Tuza [2] extended this problem to hypergraphs while ¨ Pechenik and Wise [7] considered the existence of cordial labelings for the smallest non-cyclic group V4.

It should be noted that a solution to Hovey's first conjecture implies the HTC.

2. Definitions and Facts

The following two simple properties can be found in [5].

Lemma 2.1. For any k > 0, if f is k-cordial labeling of a graph G, then f + a is a k-cordial labeling of G for any a ∈ Zk.

Lemma 2.2. For any k > 0, if f is k-cordial labeling of a graph G, then −f is a k-cordial labeling of G.

Definition 1. A caterpillar is a tree T such that for a maximum path P, all vertices are of distance at most one from P.

The next result can be found in [6].

Theorem 2.1. Caterpillars are k-cordial for all k > 0.

The proof of the above theorem is obtained by the sequential labeling of Grace [4]. We include its description since we use variants of this labeling throughout the paper.

Algorithm 1. k-cordial labelings of caterpillars

Given a caterpillar T, draw T as a planar bigraph with partite sets A and B. Choose any nonnegative integer ` and label the vertices of A sequentially by `, . . . , ` + |A|, starting at the top (bottom). Next label the vertices of B sequentially by ` + |A| + 1, . . . , ` + |A| + |B| starting at the top (bottom). Reduce all labels modulo k to obtain a k-cordial labeling.

The following is consequence of Grace's algorithm:

Proposition 2.1. If T is a rooted caterpillar with k vertices (not counting the root) for some positive integer k, longest path P, and root r at distance 1 from an endpoint of P, then T is k-cordial with every weight appearing exactly once.

Proof. We label the vertices of T by drawing the caterpillar as a bipartite graph and applying Grace's algorithm begining by labeling the root 0. Since the root is either the first or last vertex of its part, proceed in Grace's algorithm by labeling the rest of the vertices in the part sequentially. The only repeated label will be zero on the final vertex in the part not containing the root. Since the labeling is sequential, all weights are represented.

3

Figure 1. Rooted Caterpillar as in Proposition 2.1

The following fact can be easily verified.

Proposition 2.2. Every tree on at most six vertices is a caterpillar.

Hovey [6] defined A-cordiality of rooted forests for any abelian group A and studied the particular case when A is cyclic. In all but one instance, we apply his definition for the special case when the rooted forest is a rooted tree. Note that in the following definition, the root set is not considered a subset of the vertex set of the rooted forest. Thus, a rooted forest F of order k has k vertices and a set of roots R that are not the vertices of F and where the size of R is the same as the number of components of F.

Definition 2. For any integer k > 0, a rooted forest F with vertex set V , edge set E, and root set R is k-cordial if for every labeling g : R → Zk and every ` ∈ Zk, there is a function f : V → Zk satisfying

  • 1. |vi − vj | ≤ 1 for all i, j ∈ Zk
  • 2. |ei − ej | ≤ 1 for all i, j ∈ Zk where neither i nor j is `
  • 3. 0 ≤ e` − ei ≤ 2 for all i ∈ Zk

Theorem 2.2 (Hovey [6]). For any k > 0, if all trees and rooted forests with k vertices are kcordial, then all trees are k-cordial.

Lemma 2.3 (Hovey [6]). If all trees on mk vertices are k-cordial, then so are all trees T with mk ≤ |T| ≤ mk + b k 2 c + 1.

Proof. Attaching a leaf to a tree with mk + j vertices allows for k − j labels on the pendant vertex and forbids j − 1 weights on the pendant edge, when j > 0. Such a labeling exists whenever k − j > j − 1. When j = 0 any label is allowed and there is a choice for a weight.

Definition 3. For any tree T we say T is split at roots v1, . . . , vm if T can be written as a union of a tree T0 and rooted trees T1, . . . , Tm, for some positive integer m, with roots v1, . . . , vm, so that for any distinct i, j ∈ {0, . . . , m}, Ti ∩ Tj is either vi or vj .

Figure 2. Splitting a Tree

Note that when splitting a tree, one has the choice of placing branches starting at the root, in T0 or in a rooted tree.

Figure 3. Another Splitting

Proposition 2.3. Every tree on at least 5 vertices can be split into a tree and either

  • 1. a rooted tree with five vertices
  • 2. the rooted tree taken from {T 00, T000, Tiv, Tv}
  • 3. the rooted forest F 0

Proof. Let T be a tree on at least 5 vertices and let P = {v0, v1, . . . , vp} be a longest path in T. We attempt to split T at vi for i = 1, 2, 3, 4, 5. Notice that if T cannot be split to a rooted tree with 5 vertices, then for some i, 1 ≤ i ≤ 4, there is a split at vi that produces a rooted tree that has less than 5 vertices, and every split at vi+1 produces a rooted tree with more than 5 vertices. We call such a pair of vertices with indices (i, i + 1) critical, such a split at vi deficient and such a split at vi+1 excessive.

We only need consider critical pairs of vertices with indices (2, 3),(3, 4), and (4, 5). For the (2, 3) critical pair, it is easy to see that one can produce the rooted trees T 00 and T 000 by splitting at v2. For the (3, 4) critical pair, we can produce T iv and T v by splitting at v3. For the (4, 5) critical pair, one can produce rooted forest F 0 by splitting at v4.

Proposition 2.4. Every tree on at least 6 vertices can be split into a tree and either

  • 1. a rooted tree with six vertices
  • 2. the rooted tree taken from {T 0 , T0 2 , T0 3 , T0 4}
  • 3. the rooted forest taken from {F, F2, F3, F4}

Proof. The argument is similar to that in Proposition 2.3. Let P = {v0, . . . , vp} be a longest path of T and consider critical pairs with indices (2, 3),(3, 4),(4, 5), and (5, 6). There can be no critical pair with indices(2, 3). Critical pairs with indices(3, 4) produce either T 0 , F2, F3, or F4 when splitting at v3. Critical pairs with indices (4, 5) produce F, T0 2 , T0 3 , or T 0 4 when splitting the tree at v4. Critical pairs with indices (5, 6) produce F when splitting the tree at v5.

3. Six-Cordial Trees

Theorem 2.2 implies that for any integer k > 0, if all trees and rooted forests with k vertices are k-cordial, then all trees are k-cordial. This yields a method to check if trees are k-cordial for any integer k. We shorten and simplify this test for the case k = 6.

Theorem 3.1. Every tree is 6-cordial

Proof. We induct on the order of any tree T. If |T| ≤ 6, then by Proposition 2.2 and Theorem 2.1, T is 6-cordial. Next suppose all trees on 6(m − 1) vertices are 6-cordial. By Lemma 2.3 it is enough to show that all trees on 6(m − 1) + 5 vertices and all trees on 6m vertices are 6-cordial. Let T be a tree on 6m vertices. We apply Proposition 2.4 and consider case (i). That is, suppose T splits into a tree T0 on 6(m − 1) vertices and a rooted tree T1 with root v, on six vertices. We consider the degrees of v in T0.

If deg(v) = 1, we can apply Lemma 2.1 to "rotate" the labels of T0 so that the root vertex takes the label 0. If w is the minority weight of T0, we label the caterpillar T1 by Grace's algorithm with the root neighbor labeled w.

If deg(v) = 2, we apply Proposition 2.1 and notice that we only need to show the following rooted trees 6-cordial:

If deg(v) = 3, we apply Proposition 2.1 and notice that we only need to show the following rooted trees 6-cordial:

If deg(v) = 4, 5, 6, we apply Proposition 2.1 and notice that we only need to show the following rooted tree 6-cordial:

For the representations of the rooted trees a through h above, we define the level `0 as the root. For any i > 0, the level `i is defined to be those vertices of distance i from the root, ordered from left to right as in the representation above. Using this notation, we provide a 6-cordial labeling for each rooted tree, so that either every weight appears once or for every weight there is a labeling of each rooted tree with that weight serving as a majority weight. For each case above, our labeling will be on vertices starting with the root and continuing to subsequent levels, from left to right. We end each labeling by listing which weight is in the majority. These labeling can be found in List 1 at the end of the proof.

Suppose T splits into T0 on 6(m − 1) vertices and one of the above rooted trees T1. By induction, we can label T0 6-cordially with some minority weight w. However, we have shown that no matter the value of w, we can make w a majority weight of T1 or there is a labeling of T1 with no majority weight. Pasting T back together with this labeling produces a 6-cordial labeling of T.

Next, we consider case (ii) of Proposition 2.4. We label the rooted trees T 0 , T0 2 , T0 3 , T0 4 so that no label or weight appears more than once, and for every label there is a labeling with that label not present. These labelings can be found in List 2 at the end of the proof.

Since T0 is of order 6m+1, we can label it 6-cordially by the induction hypothesis and Hovey's lemma. This means that no weight on T0 is in the minority and one label is in the majority. For the minority label in one of the cordial labelings of the rooted tree T 0 , we choose the majority label of T0. Pasting T back together produces a 6-cordial labeling of T.

We now consider case (iii) of Proposition 2.4. We label the rooted forests F, F2, F3, F4 so that zero appears on the left root and consider all other possible labels on the other root. These labelings can be found in List 3 at the end of the proof.

For trees on 6(m −1) + 5 vertices, we can use many of the previous labelings on trees with 6m vertices. We argue as in the case of 6m vertices.

Let T be a tree on 6(m − 1) + 5 vertices. We apply Proposition 2.3 and consider case (i). That is, suppose T splits into a tree T0 on 6(m − 1) vertices and a rooted tree T1 with root v, on five

vertices. We consider the degrees of v in T0.

If deg(v) = 1, we can apply Lemma 2.1 to "rotate" the labels of T0 so that the root vertex takes the label 0. If w is the minority weight of T0, we label the caterpillar T1 by Grace's algorithm with the root neighbor labeled w.

If deg(v) = 2, we consider the following trees:

If deg(v) = 3, we consider the next two trees:

If deg(v) = 4 we only need to consider the following tree:

If deg(v) = 5 we have the following tree:

To show 6-cordial labelings we argue, whenever possible, that the rooted trees above are rooted subgraphs of rooted trees on 6 vertices for which we have already shown labelings in which each weight appeared in the majority. In this case, if T splits into T0 and such a rooted tree T1, then T0 can be labeled 6-cordially with some minority weight w. We have shown that we can make w a majority weight in a rooted tree Tr on six vertices containing T1 as a subgraph. When we remove the edge e of Tr to make it T1, notice that if the weight on e was w, then no weight appears in the majority in this labeling of T1. If the weight on e was not w, then this weight was not in the minority in T0. In either case, pasting T back together with this labeling produces a 6-cordial labeling of T.

For each of the above rooted trees, we describe how it is a rooted subtree of a rooted tree which we have labeled or produce a new labeling. When we provide new labelings, we produce two 6-cordial labelings with no repeated vertex label and one minority weight, which will be different in the two labelings. If a minority weight of T0 is one of the two minority weights in the labelings of T1, then we use the other. If the minority weight of T0 is neither of the two minority weights in the labelings of T1, we use either labeling. We follow the notation in the labelings of the previous cases. These descriptions can be found in List 4 at the end of the proof.

Next, we consider case (ii) of Proposition 2.3. We label the rooted trees T 00, T000, Tiv, Tv so that no label or weight appears more than once, and for every label there is a labeling with that label not present. These labelings can be found in List 5 at the end of the proof.

Since T0 is of order 6m+1, we can label it 6-cordially by the induction hypothesis and Hovey's lemma. This means that no weight on T0 is in the minority and one label is in the majority. For the minority label in one of the cordial labelings of the rooted tree T 0 , we choose the majority label of T0. Pasting T back together produces a 6-cordial labeling of T.

Finally, for case (iii) of Proposition 2.3, notice that the rooted forest F 0 is a rooted subforest of F. Hence, as in the case of the rooted trees of order 5, we can apply the labelings of F.

List 1:

  • a. 0, 4, 5, 2, 1, 0, 3; majority weight = 0.
  • a. 0, 1, 4, 0, 5, 3, 2; majority weight = 1.

  • a. 0, 2, 5, 1, 3, 4, 0; majority weight = 2.
  • a. 0, 2, 3, 5, 0, 4, 1; majority weight = 3.
  • a. 0, 2, 3, 5, 1, 4, 0; majority weight = 4.
  • a. 0, 4, 5, 1, 2, 0, 3; majority weight = 5.
  • b. 0, 0, 3, 4, 5, 1, 2; no majority weight.
  • c. 0, 0, 3, 1, 4, 2, 5; no majority weight.
  • d. 0, 0, 5, 2, 3, 4, 1; majority weight = 0.
  • d. 0, 0, 5, 1, 3, 4, 2; majority weight = 1.
  • d. 0, 2, 3, 0, 5, 4, 1; majority weight = 2.
  • d. 0, 0, 5, 1, 2, 3, 4; majority weight = 3.
  • d. 0, 5, 4, 1, 2, 3, 0; majority weight = 4.
  • d. 0, 0, 3, 1, 4, 5, 2; majority weight = 5.
  • e. 0, 2, 0, 4, 5, 3, 1; majority weight = 0.
  • e. 0, 1, 0, 4, 3, 2, 5; majority weight = 1.
  • e. 0, 2, 3, 5, 0, 1, 4; majority weight = 2.
  • e. 0, 5, 3, 1, 2, 0, 4; majority weight = 3.
  • e. 0, 5, 4, 2, 1, 0, 3; majority weight = 4.
  • e. 0, 5, 0, 2, 3, 4, 1; majority weight = 5.
  • f. 0, 0, 3, 5, 1, 2, 4; majority weight = 0.
  • f. 0, 2, 3, 1, 4, 5, 0; majority weight = 1.
  • f. 0, 3, 2, 4, 0, 1, 5; majority weight = 2.
  • f. 0, 2, 1, 3, 5, 0, 4; majority weight = 3.
  • f. 0, 4, 3, 5, 1, 2, 0; majority weight = 4.
  • f. 0, 4, 3, 5, 2, 1, 0; majority weight = 5.
  • g. 0, 0, 2, 3, 5, 4, 1; majority weight = 0.
  • g. 0, 1, 2, 4, 0, 3, 5; majority weight = 1.
  • g. 0, 0, 1, 3, 2, 4, 5; majority weight = 2.
  • g. 0, 0, 1, 3, 4, 2, 5; majority weight = 3.
  • g. 0, 0, 2, 3, 4, 5, 1; majority weight = 4.
  • g. 0, 5, 1, 2, 0, 3, 4; majority weight = 5.
  • h. 0, 3, 5, 0, 4, 1, 2; majority weight = 0.
  • h. 0, 1, 2, 0, 3, 5, 4; majority weight = 1.
  • h. 0, 3, 4, 2, 5, 0, 1; majority weight = 2.
  • h. 0, 2, 4, 1, 3, 5, 0; majority weight = 3.
  • h. 0, 2, 3, 1, 4, 5, 0; majority weight = 4.
  • h. 0, 3, 5, 4, 0, 1, 2; majority weight = 5.

List 2:
T': 0, 2, 3, 5, 1, 4; minority label = 0.
T': 0, 2, 0, 3, 4, 5; minority label = 1.
T': 0, 1, 0, 3, 5, 4; minority label = 2.
T': 0, 4, 0, 1, 2, 5; minority label = 3.
T': 0, 1, 0, 2, 5, 3; minority label = 4.
T': 0, 2, 0, 1, 4, 3; minority label = 5.
T_2': 0, 4, 2, 1, 5, 3; minority label = 0.
T_2^{7}: 0, 5, 3, 2, 0, 4; minority label = 1.
T_2': 0, 1, 5, 4, 3, 0; minority label = 2.
T_2': 0, 2, 4, 1, 0, 5; minority label = 3.
T_2': 0, 2, 3, 5, 0, 1; minority label = 4.
T_2': 0, 0, 3, 2, 1, 4; minority label = 5.
T_3': 0, 3, 1, 4, 5, 2; minority label = 0.
T_3': 0, 4, 2, 5, 0, 3; minority label = 1.
T_3': 0, 0, 4, 1, 3, 5; minority label = 2.
T_3': 0, 5, 1, 2, 0, 4; minority label = 3.
T_3': 0, 3, 1, 5, 0, 2; minority label = 4.
T_3': 0, 0, 2, 1, 3, 4; minority label = 5.
T'_4:0,4,1,5,2,3; minority label = 0.
T'_4:0,5,2,0,3,4; minority label = 1.
T'_4: 0, 5, 1, 0, 3, 4; minority label = 2.
T'_4:0,5,1,0,2,4; minority label = 3.
T'_4:0,5,1,0,2,3; minority label = 4.
T'_4:0,4,1,0,2,3; minority label = 5.
    List 3:
    Labels for F:
0, 0, 4, 0, 1, 3, 5, 2; no majority weight.
0, 1, 0, 1, 3, 4, 2, 5; majority weight = 0.
0, 1, 5, 0, 2, 3, 1, 4; majority weight = 1.
0, 1, 2, 5, 0, 4, 1, 3; majority weight = 2.
0, 1, 4, 2, 1, 5, 3, 0; majority weight = 3.
0, 1, 2, 5, 0, 4, 1, 3; majority weight = 2.

0, 1, 4, 2, 1, 5, 3, 0; majority weight = 3.

0, 1, 4, 3, 1, 0, 2, 5; majority weight = 4.

0, 1, 5, 2, 0, 4, 3, 1; majority weight = 5.

0, 2, 3, 4, 1, 2, 5, 0; majority weight = 0.

0, 2, 4, 5, 1, 2, 0, 3; majority weight = 1.

0, 2, 1, 0, 3, 2, 4, 5; majority weight = 2.

0, 2, 0, 2, 3, 5, 4, 1; majority weight = 3.

0, 2, 2, 4, 5, 0, 3, 1; majority weight = 4.

  • , 2, 5, 4, 2, 1, 3, 0; majority weight = 5.
  • , 3, 0, 1, 3, 4, 2, 5; majority weight = 0.
  • , 3, 1, 2, 0, 4, 5, 3; majority weight = 1.
  • , 3, 4, 5, 1, 2, 0, 3; majority weight = 2.
  • , 3, 3, 4, 0, 1, 5, 2; majority weight = 3.
  • , 3, 4, 3, 0, 5, 2, 1; majority weight = 4.
  • , 3, 5, 4, 0, 2, 1, 3; majority weight = 5.
  • , 4, 0, 2, 1, 3, 5, 4; majority weight = 0.
  • , 4, 1, 2, 4, 5, 3, 0; majority weight = 1.
  • , 4, 2, 3, 0, 1, 5, 4; majority weight = 2.
  • , 4, 3, 4, 0, 1, 5, 2; majority weight = 3.
  • , 4, 4, 0, 1, 3, 5, 2; majority weight = 4.
  • , 4, 5, 2, 0, 1, 3, 4; majority weight = 5.
  • , 5, 0, 1, 2, 3, 4, 5; majority weight = 0.
  • , 5, 1, 3, 0, 2, 4, 5; majority weight = 1.
  • , 5, 2, 3, 5, 0, 4, 1; majority weight = 2.
  • , 5, 3, 0, 1, 2, 4, 5; majority weight = 3.
  • , 5, 4, 3, 0, 2, 5, 1; majority weight = 4.
  • , 5, 5, 1, 2, 4, 0, 3; majority weight = 5.

Labels for F2 :

Roots 0 and 1:

, 1, 3, 0, 1, 2, 4, 5; no majority weight

Roots 0 and 3:

, 3, 5, 4, 3, 2, 0, 1; no majority weight

Roots 0 and 5:

, 5, 3, 2, 1, 0, 4, 5; no majority weight

Roots 0 and 4:

  • , 4, 1, 0, 4, 2, 3, 5; majority weight 1
  • , 4, 1, 0, 5, 2, 3, 4; majoirty weight 2
  • , 4, 3, 0, 4, 2, 1, 5; majority weight 3
  • , 4, 3, 0, 5, 4, 1, 2; majority weight 4
  • , 4, 5, 0, 4, 2, 1, 3; majority weight 5
  • , 4, 3, 1, 4, 5, 0, 2; majority weight 0

Roots 0 and 0:

  • , 0, 4, 0, 3, 1, 2, 5; majority weight 1
  • , 0, 1, 2, 3, 4, 0, 5; majority weight 2
  • , 0, 0, 2, 4, 1, 3, 5; majority weight 3
  • , 0, 1, 0, 3, 4, 2, 5; majority weight 4
  • , 0, 2, 0, 1, 5, 3, 4; majority weight 5
  • , 0, 3, 5, 4, 1, 2, 0; majority weight 0

Roots 0 and 2:

  • , 2, 1, 2, 4, 0, 5, 3; majority weight 1
  • , 2, 3, 0, 1, 2, 4, 5; majority weight 2
  • , 2, 3, 2, 4, 0, 5, 1; majority weight 3
  • , 2, 1, 4, 3, 2, 0, 5; majority weight 4
  • , 2, 5, 3, 2, 1, 0, 4; majority weight 5
  • , 2, 3, 4, 5, 0, 1, 2; majority weight 0

Labels for F3 :

  • , 1, 0, 1, 5, 4, 2, 3; no majority weight
  • , 2, 4, 0, 1, 2, 3, 5; no majority weight
  • , 3, 0, 1, 3, 2, 4, 5; no majority weight
  • , 4, 2, 0, 5, 4, 3, 1; no majority weight
  • , 5, 4, 3, 1, 2, 0, 5; no majority weight
  • , 0, 0, 1, 4, 5, 2, 3; no majority weight

Labels for F4 :

  • , 0, 2, 4, 0, 5, 1, 3; no majority weight
  • , 1, 4, 5, 2, 3, 1, 0; no majority weight
  • , 2, 3, 2, 1, 1, 4, 5; no majority weight
  • , 3, 5, 4, 0, 1, 3, 2; no majority weight
  • , 4, 4, 3, 1, 2, 5, 0; no majority weight
  • , 5, 3, 4, 0, 5, 2, 1; no majority weight

List 4:

  • i. This tree is a rooted subtree of the tree in a.
  • j. This tree is a rooted subtree of the tree in d.
  • k. This tree is a rooted subtree of the tree in a.
  • `. 0, 2, 3, 1, 4, 5; minority weight = 1
  • `. 0, 4, 3, 5, 2, 1; minority weight = 5
  • m. 0, 3, 4, 2, 1, 5; minority weight = 2
  • m. 0, 3, 2, 4, 5, 1; minority weight = 4
  • n. This tree is a rooted subtree of the tree in d.
  • o. This tree is a rooted subtree of the tree in f.

p. 0, 3, 4, 5, 1, 2; minority weight = 2
p. 0, 3, 2, 1, 5, 4; minority weight = 4
q. This tree is a rooted subtree of the tree in h.
r. 0, 1, 2, 3, 4, 5; minority weight = 0
r. 0, 0, 1, 2, 3, 4; minority weight = 5
    List 5:
    T
      00 :
0, 1, 2, 3, 4; minority labels are 5, 0.
0, 0, 1, 5, 2; minority labels are 3, 4.
0, 0, 5, 4, 3; minority labels are 1, 2.
    T
      000 :
0, 0, 1, 2, 3; minority labels are 4, 5.
0, 5, 1, 2, 4; minority labels are 0, 3.
0, 0, 3, 4, 5; minority labels are 1, 2.
    T
      iv :
0, 2, 1, 4, 5; minority labels are 0, 3.
0, 0, 1, 4, 3; minority labels are 2, 5.
0, 0, 2, 3, 5; minority labels are 1, 4.
    T
      v
        :
0, 0, 2, 1, 5; minority labels are 3, 4.
0, 1, 4, 3, 0; minority labels are 2, 5.
0, 5, 3, 2, 4; minority labels are 0, 1.

References

  • [1] I. Cahit, Cordial graphs: a weaker version of graceful and harmonious graphs, Ars Combin. 23 (1987), 201–207.
  • [2] S. Cichacz, A. Gorlich, Z. Tuza, Cordial labeling of hypertrees, ¨ Discrete Math. 313 (22) (2013), 2518–2524.
  • [3] J.A. Gallian, A dynamic survey of graph labeling, Elec. J. Combin., #DS6, accessed December 7, 2015, http://www.combinatorics.org/Surveys/ds6.pdf.
  • [4] T. Grace, On sequencial labelings of graphs, Journal of Graph Theory 7 (2) (1983), 195–201.
  • [5] R.L. Graham and N.J.A. Sloane, On additive bases and harmonious graphs, SIAM J. Algebraic Discrete Methods 1 (1980), 382–404.

  • [6] M. Hovey, A-cordial graphs, Discrete Math. 93 (1991), 183–194.
  • [7] O. Pechenik and J. Wise, Generalized graph cordiality, Discussiones Mathematicae Graph Theory 32 (2012), 557–567.
  • [8] A. Rosa, On certain valuations of the vertices of a graph, Theory of Graphs (Internat. Sympos., Rome, 1966), New York: Gordon and Breach (1967), 349–355.
  • [9] D.B. West, Introduction to Graph Theory, second edition, Prentice-Hall (2001).