ISSN 2148-838X J. Algebra Comb. Discrete Appl. -(-) • 1–13 Received: 11 February 2021 Accepted: 15 October 2021 AR TI CL E IN PR ES S Journal of Algebra Combinatorics Discrete Structures and Applications Cordiality of digraphs Research Article LeRoy B. Beasley, Manuel A. Santana, Jonathan Mousley, David E. Brown Abstract: A (0,1)-labelling of a set is said to be friendly if approximately one half the elements of the set are labelled 0 and one half labelled 1. Let g be a labelling of the edge set of a graph that is induced by a labelling f of the vertex set. If both g and f are friendly then g is said to be a cordial labelling of the graph. We extend this concept to directed graphs and investigate the cordiality of sets of directed graphs. We investigate a specific type of cordiality on digraphs, a restriction of quasigroup-cordiality called (2,3)-cordiality. A directed graph is (2,3)-cordial if there is a friendly labelling f of the vertex set which induces a (1,−1,0)-labelling of the arc set g such that about one third of the arcs are labelled 1, about one third labelled -1 and about one third labelled 0. In particular we determine which tournaments are (2,3)-cordial, which orientations of the n-wheel are (2,3)-cordial, and which orientations of the n−fan are (2,3)-cordial. 2010 MSC: 05C20, 05C38, 05C78 Keywords: Tournament, Wheel graph, Fan graph, (2, 3)-cordial 1. Introduction The study of cordial graphs began in 1987 with an article by I. Cahit [2]: “Cordial Graphs: A Weaker Version of Graceful and Harmonious Graphs”. In 1991, Hovey [3] generalized this concept to A-cordial graphs where A is an abelian group. A further generalization, one that included cordiality of directed graphs, appeared in 2012 with an article by Pechenik and Wise [4], where the A was allowed to be any quasi group, not necessarily Abelian. We modify this concept to (A,A)-cordial digraphs where A is a subset of the quasigroup A. Let G = (V,E) be an undirected graph with vertex set V and edge set E. A (0, 1)-labelling of the vertex set is a mapping f : V →{0, 1} and is said to be friendly if approximately one half of the vertices are labelled 0 and the others labelled 1. An induced labelling of the edge set is a mapping g : E →{0, 1} where for an edge uv,g(uv) = ĝ(f(u),f(v)) for some ĝ : {0, 1}×{0, 1}→{0, 1} and is said to be cordial LeRoy B. Beasley (Corresponding Author), Manuel A. Santana, Jonathan Mousley, David E. Brown; De- partment of Mathematics and Statistics, Utah State University, Logan, Utah 84322-3900, U.S.A (email: leroy_beas@aol.com, manuelarturosantana@gmail.com, jonathanmousley@gmail.com, david.e.brown@usu.edu). 1 http://orcid.org/0000-0002-0575-7200 http://orcid.org/0000-0003-1055-3824 AR TI CL E IN PR ES S L. B. Beasley et. al. / J. Algebra Comb. Discrete Appl. -(-) (2023) 1–13 if f is friendly and about one half the edges of G are labelled 0 and the others labelled 1. A graph, G, is called cordial if there exists a cordial induced labelling of the edge set of G. In this article, as in [1], we define a cordial labelling of directed graphs that is not merely a cordial labelling of the underlying undirected graph. A specific type of (A,A)-cordial digraph is a (2, 3)-cordial digraph defined by Beasley in [1]. Let D = (V,A) be a directed graph with vertex set V and arc set A. Let f : V → {0, 1} be a friendly vertex labelling and let g be the induced labelling of the arc set, g : A → {0, 1,−1} where for an arc −→uv,g(−→uv) = f(v) − f(u). The labellings f and g are (2, 3)-cordial if f is friendly and about one third the arcs of D are labelled 1, one third are labelled -1 and one third labelled 0. A digraph, D, is called (2, 3)-cordial if there exist (2, 3)-cordial labellings f of the vertex set and g of the arc set of D. Note that here and what follows, the term “about” when talking about fractions of a quantity we shall mean as close is possible in integral arithmetic, so about half of 9 is either 4 or 5, but not 3 or 6. 2. Preliminaries Definition 2.1. A quasigroup is a set Q with binary operation ◦ such that given any a,b ∈Q there are x,y ∈Q such that a◦x = b and y ◦a = b. Fact: All two element quasigroups are Abelian. Proof. Suppose that Q = {a,b} is a quasi group with binary operation ◦. Then, there are x,y ∈ Q such that a◦x = a and y ◦a = a. If x = y = b then Q is Abelian. Otherwise, we must have a◦a = a. Similarly either Q is abelian or b◦ b = b. Now, suppose that a◦a = a and b◦b = b. Then there are c,d ∈Q such that a◦d = b and c◦a = b. Since a◦a = a., we must have that both c = b and d = b. That is Q is Abelian. We now formalize the terms mentioned in the introduction. We let Zk denote the set of integers {0, 1, . . . ,k} with arithmetic modulo k. Further let Z−k denote the set Zk with binary operation “−”, subtraction modulo k. Clearly, for k ≥ 3, Z−k is a nonabelian quasigroup. Definition 2.2. A Zk-labelling (or simply a k-labelling) of a finite set, X, is a mapping f : X → Zk and is said to be friendly if the labelling is evenly distributed over Zk, that is, given any i,j ∈ Zk, −1 ≤ |f−1(i)|− |f−1(j)| ≤ 1 where |X| denotes the cardinality of the set X. Definition 2.3. Let G = (V,E) be an undirected graph with vertex set V and edge set E, and let f be a friendly (0, 1)-labelling of the vertex set V . Given this friendly vertex labelling f, an induced (0, 1)- labelling of the edge set is a mapping g : E →{0, 1} where for an edge uv, g(uv) = ĝ(f(u),f(v)) for some ĝ : {0, 1}×{0, 1} → {0, 1} and is said to be cordial if g is also friendly, that is about one half the edges of G are labelled 0 and the others are labelled 1, or −1 ≤ |g−1(0)|− |g−1(1)| ≤ 1. A graph, G, is called cordial if there exists a induced cordial labelling of the edge set of G. The induced labelling g in a cordial graph is usually g(u,v) = ĝ(f(u),f(v)) = |f(v) − f(u)| [2], g(u,v) = ĝ(f(u),f(v)) = f(v)+f(u) (in Z2) [3], or g(u,v) = ĝ(f(u),f(v)) = f(v)f(u) (product cordiality) [5]. In [3], Hovey introduced A-friendly labellings where A is an Abelian group. A labelling f : V (G) →A is said to be A-friendly if given any a,b ∈ A, −1 ≤ |f−1(b)| − |f−1(a)| ≤ 1. If g is an induced edge labelling and f and g are both A-friendly Then g is said to be an A-cordial labelling and G is said to be A-cordial. When A = Zk we say that G is k-cordial. We shall use this concept with digraphs. Given an undirected graph or a digraph, G, let Ĝ denote the subgraph (or subdigraph) of G induced by its nonisolated vertices. So Ĝ never has an isolated vertex. The need for this will become apparent in Example 3.4. 2 AR TI CL E IN PR ES S L. B. Beasley et. al. / J. Algebra Comb. Discrete Appl. -(-) (2023) 1–13 In this article, we will be concerned mainly with digraphs. We let Dn denote the set of all simple directed graphs on the vertex set V = {v1,v2, . . . ,vn}. Note that the arc set of members of Dn may contain digons, a pair of arcs between two vertices each directed opposite from the other. We shall let Tn denote the set of all subdigraphs of a tournament digraph. So the members of Tn contain no digons. Let D ∈Dn, D = (V,A) where A is the arc set of D. Then D has no loops, and no multiple arcs. An arc in D directed from vertex u to vertex v will be denoted −→uv,←−vu or by the ordered pair (u,v). We also let Gn denote the set of all simple undirected graphs on the vertex set V = {v1,v2, . . . ,vn}. So all members of Tn are orientations of graphs in Gn. In [4], Pechenik and Wise introduced quasigroup cordiality. When the quasigroup is nonabelian, this type of cordiality is quite suitable for studying labellings of directed graphs. In fact, if Q is a quasigroup with any binary operation ◦ with the property that for any a,b ∈Q a◦ b = b◦a if and only if a = b, we have the best situation for directed graphs. Now the set Zk with binary operation ◦ where for a,b ∈ Zk, a ◦ b = (b − a) mod k is such a quasigroup. In our investigations we make one further restriction: we will label our vertices with only a subset of Q, not necessarily the whole set Q: Definition 2.4. Let Q be a quasigroup with binary operation ◦ and let Q be a subset of Q. Let D = (V,A) be a directed graph with vertex set V and arc set A. Let f : V → Q be a friendly Q-labelling of V and let g : A → Q be an induced arc labelling where for −→uv ∈ A, g(−→uv) = ĝ(f(u),f(v)) for some ĝ : Q × Q → Q. The mapping g is said to be (Q,Q)-cordial if g is also friendly, that is, given any a,b ∈ Q, −1 ≤ |g−1(a)| − |g−1(b)| ≤ 1. A directed graph, D, is called (Q,Q)-cordial if there exists a induced (Q,Q)-cordial labelling of the arc set of D. We now shall restrict our attention to the smallest case of (Q,Q)-cordiality that is appropriate for directed graphs, (Z2,Z−3 )-cordiality, that defined by Beasley in [1], (2, 3)-cordiality. 3. (2, 3)-orientable digraphs Let D = (V,A) be a directed graph with vertex set V and arc set A. Let f : V → {0, 1} be a friendly labelling of the vertices of D. As for undirected graphs, an induced labelling of the arc set is a mapping g : A → X for some set X where for an arc (u,v) = −→uv,g(u,v) = ĝ(f(u),f(v)) for some ĝ : {0, 1}×{0, 1} → X . As we are dealing with directed graphs, it would be desirable for the induced labelling to distinguish between the label of the arc (u,v) and the label of the arc (v,u), otherwise, the labelling would be an induced labelling of the underlying undirected graph. If we let X = {−1, 0, 1} and ĝ(f(u),f(v)) = f(v) −f(u) using real arithmetic, or arithmetic in Z3, we have an asymmetric labelling. In this case, if about one third of the arcs are labelled 0, about one third of the arcs are labelled 1 and about one third of the arcs are labelled -1 we say that the labelling is (2, 3)-cordial. Formally: Definition 3.1. Let D ∈Tn, D = (V,A), be a digraph without isolated vertices. Let f : V →{0, 1} be a friendly labelling of the vertex set V of D. Let g : A →{1, 0,−1} be an induced labelling of the arcs of D such that for any i,j ∈{1, 0,−1}, −1 ≤ |g−1(i)|− |g−1(j)| ≤ 1. Such a labelling is called a (2, 3)-cordial labelling. A digraph D ∈Tn whose subgraph Ĝ can possess a (2, 3)-cordial labelling will be called a (2, 3)-cordial digraph. An undirected graph G is said to be (2, 3)-orientable if there exists an orientation of G that is (2, 3)- cordial. In [1] the concept of (2, 3)-cordial digraphs was introduced and paths and cycles were investigated. In [6] one can find further investigation of orientations of paths and trees as well as finding the maximum number of arcs possible in a (2, 3)-cordial digraph. In this article we continue this investigation, showing 3 AR TI CL E IN PR ES S L. B. Beasley et. al. / J. Algebra Comb. Discrete Appl. -(-) (2023) 1–13 which tournaments, which orientations of the wheel graphs, and which orientations of the fan graphs are (2, 3)-cordial. Definition 3.2. Let D = (V,A) be a digraph with vertex labelling f : V → {0, 1} and with induced arc labelling g : A → {0, 1,−1}. Define Λf,g : Dn → N3 by Λf,g(D) = (α,β,γ) where α = |g−1(1)|,β = |g−1(−1)|, and γ = |g−1(0)|. Let D ∈Tn and let DR be the digraph such that every arc of D is reversed, so that −→uv is an arc in DR if and only if −→vu is an arc in D. Let f be a (0, 1)-labelling of the vertices of D and let g(−→uv) = f(v)−f(u) so that g is a (1,−1, 0)-labelling of the arcs of D. Let f be the complementary (0, 1)-labelling of the vertices of D, so that f(v) = 0 if and only if f(v) = 1. Let g be the corresponding induced arc labelling of D, g(−→uv) = f(v) −f(u). Lemma 3.3. Let D ∈ Tn with vertex labelling f and induced arc labelling g. Let Λf,g(D) = (α,β,γ). Then 1. Λf,g(DR) = (β,α,γ). 2. Λf,g(D) = (β,α,γ), and 3. Λf,g(D R) = Λf,g(D). Proof. If an arc is labelled 1,−1, 0 respectively then reversing the labelling of the incident vertices gives a labelling of −1, 1, 0 respectively. If an arc −→uv is labelled 1,−1, 0 respectively, then −→vu would be labelled −1, 1, 0 respectively. Example 3.4. Now, consider a graph, Xn in Gn consisting of three parallel edges and n-6 isolated vertices. Is Xn (2, 3)-orientable? If n = 6, the answer is no, since any friendly labelling of the six vertices would have either no arcs labelled 0 or two arcs labelled 0. In either case, the orientation would never be (2, 3)-cordial. That is X6 is not (2, 3)-orientable, however with additional vertices like X7 the graph is (2, 3)-orientable. Thus, for our investigation here, we will use the convention that a graph, G, is (2, 3)-orientable/(2, 3)- cordial if and only if the subgraph of G induced by its nonisolated vertices, Ĝ, is (2, 3)-orientable/(2, 3)- cordial. 3.1. (2, 3)-orientations of a complete graph-tournaments It is an easy exercise to show that every 3-tournament is (2, 3)-cordial and that two of the four non isomorphic 4-tournaments are (2, 3)-cordial. See Figures 2 and 3. Note that the 4-tournaments that are not (2, 3)-cordial may require more than a cursory glance to verify that they are not (2, 3)-cordial. Lemma 3.5. Every 5-tournament is (2, 3)-cordial. Proof. Let T ∈D5 be a tournament. Then there are two vertices, without loss of generality, v1 and v2, whose total out degree is four. (And hence the total in-degree of v1 and v2 is also four.) Let f be the vertex labelling and let f(v1) = f(v2) = 1 and f(v3) = f(v4) = f(v5) = 0. Let g be the arc labelling g(−−→vivj) = f(vj) − f(vi). Then, the arc between v1 and v2 is labelled 0, as are the three arcs between v3,v4 and v5. Thus there are four arcs labelled 0. The three arcs from v1 or v2 to vertices v3,v4 or v5 are labelled 1 and the three arcs from v3,v4 or v5 to vertices v1 or v2 are labelled -1. In Figure 1 is an example of the labelling described above. Thus Λf,g(T) = (3, 3, 4). That is T is (2, 3)-cordial. Lemma 3.6. If n ≥ 6 and T ∈Dn is a tournament on n vertices then T is not (2, 3)-cordial. 4 AR TI CL E IN PR ES S L. B. Beasley et. al. / J. Algebra Comb. Discrete Appl. -(-) (2023) 1–13 0 0 11 0 0 0 0 −1 1 −1 1 −11 0 v1v2 v3 v4 v5 Figure 1. A (2,3)-cordial labelling of a 5-tournament Proof. We divide the proof into two cases: Case 1. n is even. Let n = 2k. We shall show that there must be more arcs labelled 0 than is allowed in any (2, 3)-cordial digraph with n(n−1) 2 arcs. For any vertex labelled 0, there are k − 1 other vertices also labelled 0 so that there are k − 1 arcs labelled 0 that either begin or terminate at that vertex. Also there are k such vertices so there are k(k − 1)/2 arcs between pairs of vertices each labelled 0. (Note, since each arc is adjacent to two vertices we have divided the total number by 2 to get the number of distinct arcs labelled 0.) There are also k(k − 1)/2 arcs between pairs of vertices each labelled 1. Thus we must have k(k − 1) arcs labelled 0. Now, there must be at most one third the number of arcs labelled 0, so we must have 3k(k − 1) ≤ n(n−1) 2 + 2 = 4k 2−2k+4 2 . That is, we must have k2 − 2k − 2 ≤ 0. But that only happens if k ≤ 2. So if k ≥ 3 or n ≥ 6, T is not (2, 3)-cordial. Case 2. n is odd. Let n = 2k + 1. Without loss of generality, we may assume that there are k vertices labelled 0 and k + 1 vertices labelled 1. Thus there are 1 2 k(k−1) arcs labelled 0 that connect two vertices labelled 0 and 1 2 (k + 1)k arcs labelled 0 that connect two vertices labelled 1. Thus there are at least k2 arcs labelled 0. To be (2, 3)-cordial we must have that 3k2 ≤ n(n−1) 2 + 2, or k2−k−2 ≤ 0. That happens only if k ≤ 2. But, since n is odd, n ≥ 7 so k ≥ 3. Thus, T is not (2, 3)-cordial. Lemma 3.7. The tournaments T4,3 and T4,4 of Figure 3 are not (2, 3)-cordial. Proof. Since T4,4 is the reversal of T4,3, by Lemma 3.3 we only need show that T4,3 is not (2, 3)-cordial. Further, by Lemma 3.3 we may assume that the upper left vertex of T4,3 in Figure 3 is labelled 0. Since any permutation of the other three vertices results in an isomorphic graph we may assume that the upper 5 AR TI CL E IN PR ES S L. B. Beasley et. al. / J. Algebra Comb. Discrete Appl. -(-) (2023) 1–13 0 0 1 and 0 0 1 1 0 −1 0 1 −1 Figure 2. (2,3)-cordial labellings of 3- tournaments T4,3 : (2,2,2,0) Not (2,3)-cordial T4,4 : (3,1,1,1) Not (2,3)-cordial 0 1 1 0 1 −1 −1 0 0 1 T4,1 : (2,2,1,1) 0 1 0 1 1 0 0 1 −1 −1 T4,2 : (3,2,1,0) Figure 3. (2,3)-cordial labellings of two 4-tournaments and two non (2,3) cordial 4-tournaments with their out-degree sequences. right vertex is labelled 0 and the bottom two are labelled 1. This results in one arc labelled 1, three arcs labelled −1 and two arcs labelled 0. Thus T4,3 is not (2, 3)-cordial. Theorem 3.8. Let T be an n-tournament. Then T is (2, 3)-cordial if and only if n ≤ 5 and T is not isomorphic to T4,3 or T4,4. Proof. Lemmas 3.7, 3.5 and 3.6 together with Figures 2 and 3 establish the theorem. 6 AR TI CL E IN PR ES S L. B. Beasley et. al. / J. Algebra Comb. Discrete Appl. -(-) (2023) 1–13 We end this section with a couple of observations we label as corollaries: Corollary 3.9. The property of being (or not being) (2, 3)-cordial is not closed under vertex deletion. Proof. Every tournament on k vertices is a vertex deletion of a tournament on k + 1 vertices. Thus, T4,3, which is not (2, 3)-cordial, is a vertex deletion of a tournament on 5 vertices, which is (2, 3)-cordial, and this tournament is a vertex deletion of a tournament on 6 vertices, which is not (2, 3)-cordial. Corollary 3.10. The property of being (or not being) (2, 3)-cordial is not closed under arc contraction. Proof. As in the above corollary, every tournament on k vertices is an arc contraction of a tournament on k + 1 vertices. Thus, T4,3, which is not (2, 3)-cordial, is an arc contraction of a tournament on 5 vertices, which is (2, 3)-cordial, and this tournament is an arc contraction of a tournament on 6 vertices, which is not (2, 3)-cordial. 3.2. (2, 3)-orientations of wheel graphs A wheel graph on n vertices consists of an (n− 1)-star together with edges joining the non central vertices in a cycle. A 6-wheel is shown in Figure 4. Since we are not concerned with digraphs that contain digons, we shall assume that n ≥ 4 in this section. An orientation of the wheel graph with the central vertex being a source/sink is called an out/in- wheel. If the outer cycle of the wheel is oriented in a directed cycle the wheel is called a cycle-wheel. If the n-wheel is oriented such that it is both an out-wheel and a cycle-wheel it is called an n-cycle-out-wheel. See Figure 5. v1 v2 v3v4 v5 v6 Figure 4. A 6-wheel graph. Definition 3.11. Let Wn = (V,A) be an n-wheel digraph with central vertex vn and with vertex labelling f : V → {0, 1}. Let g be the induced arc labelling g : A → {0, 1,−1} where g(−→uv) = f(v) − f(u). Let 7 AR TI CL E IN PR ES S L. B. Beasley et. al. / J. Algebra Comb. Discrete Appl. -(-) (2023) 1–13 v1 v2 v3v4 v5 v6 Figure 5. A 6-cycle-out-wheel graph. S be the set of arcs incident with the central vertex and let T be the set of arcs not incident with the central vertex. Define ΛSf,g to be the real triple Λ S f,g(D) = (αS,βS,γS) where αS = |g −1(1) ∩ S|,βS = |g−1(−1) ∩S|, and γS = |g−1(0) ∩S| and ΛTf,g to be the real triple Λ T f,g(D) = (αT ,βT ,γT ) where αT = |g−1(1) ∩ T |,βT = |g−1(−1) ∩ T |, and γT = |g−1(0) ∩ T |. Since S ∪ T = A, the set of all arcs of D, αS + αT = α,βS + βT = β, and γS + γT = γ, where Λf,g(D) = (α,β,γ). Theorem 3.12. Let −→ Wn be an n-cycle-out-wheel graph with central vertex vn. Then −→ Wn is not (2, 3)- cordial. Proof. We proceed with two cases, the case that n is even then the case that n is odd. Let −→ Wn = (V,A) and let f : V → {0, 1} be a vertex labelling and g : A → {0, 1,−1} be the induced arc labelling, g(−→uv = f(v) −f(u). Suppose that f and g is a (2, 3)-cordial labelling. Case 1: n = 2k. Without loss of generality, we may assume that f(vn) = 0. Thus, αS = k,βS = 0 and γS = k − 1. Further, since the orientation is cyclic, αT = βT . Since α − 1 ≤ β ≤ α + 1 we have αT + k− 1 = αT + αS − 1 = α− 1 ≤ β = βT + βS = βT = αT . Thus k− 1 ≤ 0 or k ≤ 1, a contradiction since n ≥ 4. Case 2: n = 2k + 1. Without loss of generality we may assume that f(vn) = 0. Since either k or k + 1 of the non central vertices must be labelled 0, we have two possibilities: αS = k or αS = k + 1. Subcase 1. αS = k Here we have γS = k and βS = 0. Further, αT = βT since −→ W is cyclic. Since the labelling is (2, 3)-cordial, α−1 ≤ β ≤ α+ 1. Thus k+αT −1 = αS = αT −1 = α−1 ≤ β = βS +βT = αT . That is k − 1 ≤ 0 or k ≤ 1, a contradiction since n ≥ 4. Subcase 2. αS = k + 1 Here we have γS = k−1 and βS = 0. Further, αT = βT since −→ W is cyclic. Since the labelling is (2, 3)-cordial, α−1 ≤ β ≤ α + 1. Thus k + αT = k + 1 + αT −1 = αS + αT −1 = α−1 ≤ β = βS + βT = αT . That is k ≤ 0, a contradiction since n ≥ 4. 8 AR TI CL E IN PR ES S L. B. Beasley et. al. / J. Algebra Comb. Discrete Appl. -(-) (2023) 1–13 In all cases we have arrived at a contradiction thus we must have that −→ W is not (2, 3)-cordial. Lemma 3.13. Let C be an undirected cycle with a (0, 1)-vertex labelling. Then, there is an even number of edges in C whose incident vertices are labelled differently. Proof. We may assume that the vertex v1 is labelled 0. Going around the cycle, the labelling goes from 0 to 1 then back again to zero. This two step change must happen a fixed number of times then return to vertex v1. Thus there are an equal number of changes in labelling from 0 to 1 and from 1 to 0. That is, the total number of changes is an even number. Theorem 3.14. Let Wn be the undirected wheel graph on n vertices. Then, Wn is not (2, 3)-orientable if and only if n = 2k for some integer k, 4 does not divide n, and 2n− 2 = 3z for some integer z. Proof. Let −→ Wn be an orientation of the wheel graph on n vertices with central vertex vn. Let AH be the set of arcs incident with vn, and let AR be the arcs not incident with vn. Then A = AH ∪AR. Let f be a friendly vertex labelling and g the induced arc labelling of −→ Wn. Define , λf,H(x) = |g−1(x) ∩AH|, and λf,R(x) = |g−1(x) ∩AR|, Define λf (x) = λf,H(x) + λf,R(x), that is λf (x) = |g−1(x)|. We begin by showing for n = 2k for some integer k, k = 2` + 1 for some integer `, and 2n− 2 = 3z for some integer z that Wn is not (2, 3)-orientable. In this case, We may assume that f(vn) = 0 and λf,H(1) +λf,H(−1) = k, an odd integer. By Lemma 3.13 the number of arcs that are not incident with vn and labelled either 1 or −1 is even. Thus λf (1) + λf (−1) = (λf,H(1) + λf,H(−1)) + (λf,R(1) + λf,R(−1)) is the sum of an even integer and an odd integer, so that λf (1) + λf (−1) is an odd integer. But since the total number of arcs is 2n− 2 = 3z, if −→ Wn is (2, 3)-cordial, we must have λf (1) + λf (−1) = 2z, an even integer, a contradiction. Thus, in this case Wn is not (2, 3)-orientable. We now show that for all other cases Wn is (2, 3)-orientable. We divide the proof into three cases, those being whether the total number of edges in Wn is a multiple of three, one more than a multiple of three, or two more than a multiple of three. Case 1. 2n− 2 = 3z for some integer z. Subcase 1.1. n = 2k and k = 2`. In this case, let f be the labelling such that the labelling of the cycle has 2(z − k 2 ) edges incident with vertices labelled differently. Orient all arcs not incident with vn clockwise around the cycle. Orient half the arcs incident with vn that are labelled 1 away from vn, and half toward vn. In this case, λf,H(0) = k − 1, and λf,H(1) = λf,H(−1) = k2 = `. Further, λf,R(1) = λf,R(−1) = z− k2 . Thus, λf (1) = λf (−1) = λf,H(1) + λf,R(1) = ` + z− k 2 = z. Thus, we must also have λf (0) = z, and that Wn is (2, 3)-orientable. Subcase 1.2. n = 2k + 1. In this case proceed as in Subcase 1.1, labelling the vertices not incident with vn with an even number of 1’s (either k or k + 1). Let ` be half of this even number. Then, we produce a (2, 3)-cordial orientation of Wn the same as in Subcase 1.1. Case 2. 2n− 2 = 3z + 1 for some integer z. Subcase 2.1. n = 2k, k = 2`. In this case, let f be the labelling such that the labelling of the cycle has 2(z−k 2 ) edges incident with vertices labelled differently. Orient all arcs not incident with vn clockwise around the cycle. Orient half the arcs incident with vn that are labelled 1 away from vn, and half toward vn. In this case, λf,H(0) = k − 1,λf,H(1) = λf,H(−1) = k2 = `. Further, λf,R(1) = λf,R(−1) = z − k 2 . Thus, λf (1) = λf (−1) = λf,H(1) + λf,R(1) = ` + z− k2 = z. Thus, we must also have λf (0) = z + 1, and that Wn is (2, 3)-orientable. Subcase 2.2. n = 2k, k = 2`+1 In this case, let f be the labelling such that the labelling of the cycle has 2(z− k−1 2 ) edges incident with vertices labelled differently. Orient ` of the arcs incident with vn that are labelled 1 away from vn, and ` + 1 of those arcs toward vn. In this case, λf,H(0) = k−1,λf,H(1) = ` and λf,H(−1) = ` + 1. Further, λf,R(1) = λf,R(−1) = z− k2 = z = `. Thus, λf (1) = λf,H(1) + λf,R(1) = ` + z − ` = z, and λf (−1) = λf,H(−1) + λf,R(−1) = ` + 1 + z − ` = z + 1. Thus, we must also have λf (0) = 2n− 2 − (z) − (z + 1) = z, and thus Wn is (2, 3)-orientable. 9 AR TI CL E IN PR ES S L. B. Beasley et. al. / J. Algebra Comb. Discrete Appl. -(-) (2023) 1–13 Subcase 2.3. n = 2k + 1. In this case proceed as in Subcase 2.1 labelling the vertices not incident with vn with an even number of 1’s (either k or k + 1 depending upon whether k is even or odd). Let ` be half of this even number. Then, we produce a (2, 3)-cordial orientation of Wn the same as in Subcase 2.1. Case 3. 2n− 2 = 3z + 2 for some integer z. Subcase 3.1. n = 2k, k = 2`. In this case, let f be the labelling such that the labelling of the cycle has 2(z−k 2 ) edges incident with vertices labelled differently. Orient all arcs not incident with vn clockwise around the cycle. Orient half the arcs incident with vn that are labelled 1 away from vn, and half toward vn. In this case, λf,H(0) = k − 1,λf,H(1) = λf,H(−1) = k2 = `. Further, λf,R(1) = λf,R(−1) = z − k 2 . Thus, λf (1) = λf (−1) = λf,H(1) + λf,R(1) = ` + z− k2 = z. Thus, we must also have λf (0) = z + 1, and that Wn is (2, 3)-orientable. Subcase 3.2. n = 2k, k = 2` + 1 In this case, let f be the labelling such that the labelling of the cycle has 2(z − k−1 2 ) edges incident with vertices labelled differently. Orient ` of the arcs incident with vn that are labelled 1 away from vn, and ` + 1 toward vn. In this case, λf,H(0) = k− 1,λf,H(1) = ` and λf,H(−1) = ` + 1. Further, λf,R(1) = λf,R(−1) = z − k2 = z = `. Thus, λf (1) = λf,H(1) + λf,R(1) = ` + z − ` = z, and λf (−1) = λf,H(−1) + λf,R(−1) = ` + 1 + z − ` = z + 1. Thus, we must also have λf (0) = z, and that Wn is (2, 3)-orientable. Subcase 3.3. n = 2k + 1. In this case proceed as in Subcase 3.1 labelling the vertices not incident with vn with an even number of 1’s (either k or k + 1 depending upon whether k is even or odd. Let ` be half of this even number. Then, we produce a (2, 3)-cordial orientation of Wn the same as in Subcase 3.1. We have now established the theorem. 3.3. (2, 3)-orientations of fan graphs A fan graph is isomorphic to a wheel graph with one edge of the cycle deleted. Thus, by deleting one properly chosen arc from the cycle of a (2, 3)-oriented n-wheel graph we obtain an orientation of the n-fan graph that is (2, 3)-cordial. Note that if there are at least as many arcs labelled x (x = 1,−1 or 0) as any other labelling, the properly chosen arc would be in the set of arcs labelled x. Thus there is only one case to consider, the case where 2n− 2 = 3z,n = 2k and k = 2` + 1 for some z,k, and `. Theorem 3.15. Let n ≥ 5 and let Fn be the n-fan graph with central vertex v1, that is the edges not on the cycle are all incident to v1. Let −→ F be a cyclic-out orientation of Fn. Then −→ F is not (2, 3)-cordial. Proof. As for wheel graphs, the number of arcs labelled 1 on the cycle is equal to the number of arcs labelled −1 and there are at least two arcs labelled 1 on the interior of the cycle. Thus, the number of arcs labelled 1 in −→ F is at least two more that the arcs labelled −1 in −→ F . That is −→ F is not (2, 3)-cordial. Theorem 3.16. Let Fn be the fan graph on n vertices, 2n−3 = 3z + 2, n = 2k and k = 2` + 1 for some integers k,`, and z. Then there is an orientation of Fn that is (2, 3)-cordial. Proof. Let α = z−`+ 1, and define f : V →{0, 1} by f(v2i−1) = 0, i = 1, . . . ,α, f(v2i) = 1, i = 1, . . . ,α, f(v2α+i) = 1, i = 1, . . . ,k−α, and f(vk+α+i) = 0, i = 1, . . . ,k−α, Note that (k−α) + (k + α) = 2k = n, so all vertices are labelled. Orient the cycle clockwise, so that the oriented cycle is −−→v1v2, −−→v2v3, . . . , −−−−→vn−1vn,−−→vnv1. See Figure 6 where the vertex labellings are outside the cycle. Now, orient ` of the inner arcs from v1 to arcs labelled 1 (except for v2 which is not an inner arc) away from v1 and the remaining ` such arcs inward so that we get −→ Fn = (V,A). Let g : A →{0, 1,−1} be the induced labelling, g(−→uv) = f(v)−f(u). Then there are α arcs labelled 1 on the cycle, α arcs labelled −1 on the cycle, ` of the inner arcs are labelled −1 and ` of the inner arcs are labelled 1. Thus, in all of −→ Fn there are α + ` = z + 1 arcs labelled −1, α + ` = z + 1 arcs labelled 1 and (hence) z arcs labelled 0. That is, this orientation of Fn is (2, 3)-cordial. 10 AR TI CL E IN PR ES S L. B. Beasley et. al. / J. Algebra Comb. Discrete Appl. -(-) (2023) 1–13 v1 v2 v3 v4 v2α−1 v2α v2α+1 vs−1 vsvs+1vn−1vn . . . · · · ... s = k + α 0 01 1 0 1 1 1 1 000 Figure 6. Fn with oriented cycle arcs. 3.4. Extremes of (2, 3)-cordiality As seen in section 3, complete graphs are not (2, 3)-orientable if n ≥ 6. So the question arises: How large can a (2, 3)-orientable graph be (how many edges)? Or: How large can a (2, 3)-cordial digraph be? That question was fully answered by M. A. Santana in [6] For completeness we shall include the proofs of his results. Theorem 3.17. [6, Theorem 3.1] Every simple directed graph is (2, 3)-cordial if and only if there exists a friendly vertex labelling such that about 1 3 of the edges are connected by vertices of the same label. Proof. Let G be a graph such that there exists a friendly labelling on G such that about 1 3 of the edges are connected by vertices of the same label. This would mean about 2 3 of the edges are connected by vertices of different labels, and therefore arcs may be assigned such that G is cordial. Now let H be a graph such that there does not exist a friendly labelling on H such that about 1 3 of the edges are connected by vertices of the same label then there will be no way H can be cordial since only then could about one third of the edges be labelled 0. Santana’s application of Theorem 3.17 is Theorem 3.18. [6, Theorem 4.2] Given a directed graph G = (V,E) with vertex set V and n = |V | with n ≥ 6, and edge set E, the maximum size of E such that G is cordial for any given n is |E|max = ( n 2 ) −Z + ⌈ 1 2 ((n 2 ) −Z )⌉ Z = ( dn 2 e 2 ) + ( bn 2 c 2 ) . (1) 11 AR TI CL E IN PR ES S L. B. Beasley et. al. / J. Algebra Comb. Discrete Appl. -(-) (2023) 1–13 00 0 1 1 1 Figure 7. A complete graph. Dashed lines represent edges labelled zero regardless of arc orien- tation F. rom section 3 we have that for any tournament with n ≤ 5 there exists a cordial labelling, save for the case when n = 4 thus we begin with a complete graph with n ≥ 6. Recall that the number of edges on a complete graph is ( n 2 ) . Due to our cordial labelling the number of edges with an induced labelling of 0 will be our Z. This is because it will be the number of edges connected by two vertices of the same label, as shown in Figure 7. If n is even that will mean that Z = 2 (n 2 2 ) , i.e., it will be the number of edges on two complete graphs each on n 2 vertices represented by the labellings of ones and zeros. The floor and ceiling function in (1) simply account for the odd case. For every tournament with n ≥ 6 vertices, Z > 1 3 ( n 2 ) . Therefore some of the arcs labelled zero will need to be removed to get a cordial graph. How many arcs need to be removed is going to be equal to how much greater Z is than the number of half the number of arcs not labelled zero. By the definition of a directed cordial graph we know that Z can be larger than α or β and we can still have a cordial graph, hence the ceiling function. As mentioned in the introduction, the smallest non (2, 3)-cordial digraph is an orientation of Xn, three parallel arcs. A question may be asked: What is the minimum number of arcs in a non (2, 3)-cordial digraph that has no isolated vertices? 4. Conclusions In this article, we have shown that the only tournaments that are (2, 3)-cordial are when n ≤ 5 and then not for two 4-tournaments. Except for one case when n is even, the n-wheel graph has an orientation that is (2, 3)-cordial and that at least one orientation of any wheel graph is not (2, 3)-cordial. Further, we show that every fan graph has a (2, 3)-cordial orientation, and there is always an orientation of the n-fan that is not (2, 3)-cordial. References [1] L. B. Beasley, Cordial digraphs, arXiv:2212.05142. 12 https://arxiv.org/abs/2212.05142 AR TI CL E IN PR ES S L. B. Beasley et. al. / J. Algebra Comb. Discrete Appl. -(-) (2023) 1–13 [2] I. Cahit, Cordial graphs: A weaker version of graceful and harmonious graphs, Ars Comb. 23 (1987) 201–207. [3] M. Hovey, A-cordial graphs, Discrete Math. 93(2-3) (1991) 183–194. [4] O. Pechenik, J. Wise, Generalized graph cordiality, Discuss. Math. Graph Theory 32(3) (2012) 557– 567. [5] E. Salehi, PC-labelling of a graph and its PC-set, Bull. Ins.t Comb. Appl. 58 (2010) 112–121. [6] M. A. Santana, J. M. Mousley, D. E. Brown, L. B. Beasley, (2, 3) cordial trees and paths, arXiv:2012.10591. 13 https://mathscinet.ams.org/mathscinet-getitem?mr=886954 https://mathscinet.ams.org/mathscinet-getitem?mr=886954 https://doi.org/10.1016/0012-365X(91)90254-Y https://doi.org/10.7151/dmgt.1626 https://doi.org/10.7151/dmgt.1626 http://salehi.faculty.unlv.edu/PCL1.pdf https://doi.org/10.48550/arXiv.2012.10591 https://doi.org/10.48550/arXiv.2012.10591 Introduction Preliminaries (2,3)-orientable digraphs Conclusions References