Preservers of graph and digraph cordiality

1. Introduction

Let ${\mathcal{G}}_n$ denote the set of all simple loopless undirected graphs on the vertex set $V=\{v_1,v_2,\dots ,v_n\}$. Let $G=(V,E)$ be an undirected graph in ${\mathcal{G}}_n$ with vertex set $V$ and edge set $E$. A $(0,1)$-labeling of the vertex set is a mapping $f:V\to \{0,1\}$ and is said to be friendly if approximately one half of the vertices are labeled 0 and the others labeled 1. An induced labeling of the edge set is a mapping $g:E\to \{0,1\}$ where for an edge $uv,g(uv)=\hat{g}(f(u),f(v)$ for some $\hat{g}:\{0,1\}\times \{0,1\}\to \{0,1\}$ and is said to be cordial if $f$ is friendly and about one half the edges of $G$ are labeled 0 and the others labeled 1, that is, both $f$ and $g$ are friendly. A graph, $G$, is called cordial if there exists a cordial induced labeling of the edge set of $G$.

Let $|\mathcal{X}|$ denote the cardinality of the set $\mathcal{X}$, so that $|g^{-1}(0)|$ denotes the number of edges labeled $0$ if $g:E\to \{0,1\}$ is the labeling of the edges.

In this article we consider not only cordial undirected graphs but also use a cordial labeling of directed graphs that is not merely a cordial labeling of the underlying undirected graph. It was defined and studied in [1].

We shall consider three classes of graphs: Those that are cordial with an induced edge labeling consisting of the sum modulo 2 of the labels of the end vertices (see [3]); those that are cordial with an induced edge labeling consisting of the product of the labeling of the end vertices (see [5]) and those that are $(2,3)$-orientable (see[1]), that is, graphs that may be oriented such that if each arc of the directed graph is labeled as the label of the terminal vertex minus the label of the initial vertex, and we have that about one third of the arcs are labeled 0, about one third labeled 1 and the remaining one third labeled -1.

2. Preliminaries

We begin with formal definitions of the terms from the introduction.

For digraphs we have a similar definition, however, as digraphs are not usually symmetric, we do not require the induced mapping $g$ to be symmetric:

Note that in the above definitions, if $\hat{g}$ is the binary mapping corresponding to one of the binary operations on $\mathcal{A}$ or $\mathcal{B}$ we indicate that by placing that operator in the notation. For example a digraph is $(\mathcal{A},\mathcal{B},-)$-cordial indicates that the induced labeling $g$ is $g(\overrightarrow{uv})=f(v)-f(u)$. So a digraph is $(2,3,-)$-cordial means that the arc labelings are $f(v)-f(u)$ for the arc $\overrightarrow{uv}$. In this specific case we usually drop the minus sign and write $(2,3)$-cordial. A graph with an $\mathcal{A}$-friendly vertex labeling is product cordial if it is $(\mathcal{A},\times )$-cordial (see [5]). Unless specified otherwise, product cordial graphs have the vertex set labeled with $\{0,1\}$.

3. Extremes of cordial graphs

In this section we shall exhibit examples of graphs that are the smallest or largest (edgewise) of cordial/noncordial graphs.

3.1. $(Z_2,+)$-cordial/Non-cordial graphs

3.1.1. Smallest $(Z_2,+)$-cordial/Non-cordial graphs

It is easily shown that the graph with one edge and all graphs with three edges are $(Z_2,+)$-cordial. However, the connected graph with two edges (a 2-path or a 2-star) is $(Z_2,+)$-cordial while the graph $2K_2$ is not and the complete graph on $n\ge 4$ vertices is not $(Z_2,+)$-cordial..

3.1.2. Largest $(Z_2,+)$-cordial/Non-cordial graphs

If $n\ge 4$, $K_n$ is not $(Z_2,+)$-cordial. So how large can a graph be and be $(Z_2,+)$-cordial? That is: How many edges can a $(Z_2,+)$-cordial graph on $n$ vertices contain?

Let $f$ be a friendly labeling of $K_n$. Since the labeling of the vertices of a complete graph is independent of the visual location of the vertex, we may assume that the vertices labeled 0 are located on the right half and the vertices labeled 1 are on the left. The vertices labeled 0 induce a graph of order $\frac{\lfloor \frac{n}{2}\rfloor (\lfloor \frac{n}{2}\rfloor -1)}{2}$ and the vertices labeled 1 induce a subgraph of order $\frac{\lceil \frac{n}{2}\rceil (\lceil \frac{n}{2}\rceil -1)}{2}$, or visa versa. In either case there are precisely $\frac{\lfloor \frac{n}{2}\rfloor (\lfloor \frac{n}{2}\rfloor -1)}{2}+\frac{\lceil \frac{n}{2}\rceil (\lceil \frac{n}{2}\rceil -1)}{2}$ edges labeled 0 and the others labeled 1.

So if $n$ is even, say $n=2k$, there are $k^2-k$ edges labeled 0 and $k^2$ edges labeled 1. Thus to have a $(Z_2,+)$-cordial graph one must delete at least $k-1$ edges joining vertices that are labeled differently. Thus, when $n=2k$ is even, there can be at most $2k^2-2k+1$ edges in a $(Z_2,+)$-cordial graph.

If $n$ is odd, say $n=2k+1$, there are $k^2+k$ edges labeled 1 and $k^2$ edges labeled 0. Thus to get a graph that is $(Z_2,+)$-cordial one must delete at least $k-1$ edges connecting vertices labeled differently. Thus, when $n=2k+1$ is odd, there can be at most $2k^2+1$ edges in a $(Z_2,+)$-cordial graph.

The added “+1” in the formulas accounts for the fact that for a cordial graph the cardinality of the two sets $g^{-1}(0)$ and $g^{-1}(1)$ may differ by 1.

3.2. Product cordial/non-cordial graphs

3.2.1. Smallest $({\mathcal{Z}}_2,\times )$-cordial/non-cordial graphs

It is easily shown that all graphs with one, two, or three edges are $(Z_2,\times )$-cordial. There are two graphs with four edges that are not $(Z_2,\times )$-cordial, the four cycle and a three cycle with an attached edge.

3.2.2. Largest $(Z_2,\times )$-cordial/non-cordial graphs

For a labeling of the vertices of a graph on $n$ vertices to be friendly, at most $\lceil \frac{n}{2}\rceil$ vertices can be labeled 1. Thus, at most $\frac{\lceil \frac{n}{2}\rceil (\lceil \frac{n}{2}\rceil -1)}{2}$ edges can be labeled 1 for any product cordial graph on $n$ vertices. Thus, a $({\mathcal{Z}}_2,\times )$-cordial graph on $n$ vertices can have at most at most $\lceil \frac{n}{2}\rceil (\lceil \frac{n}{2}\rceil -1)$ edges since $\frac{\lceil \frac{n}{2}\rceil (\lceil \frac{n}{2}\rceil -1)}{2}<\frac{1}{2}\frac{n(n-1)}{2}-1$ if $n\ge 4$.

3.3. $(2,3)$-orientable/non-orientable graphs

3.3.1. Smallest $(2,3)$-orientable/non-orientable graphs

Note that the graph consisting of three mutually non incident arcs is $(2,3)$-cordial in the set of digraphs on seven or more vertices but not in the set of digraphs on six vertices. Thus the need for using nonisolated vertices in the above definition to avoid ambiguity. All other graphs consisting of the union of three edge graphs are $(2,3)$-orientable. There are a total of five non isomorphic graphs of three edges. See Figure 1 for the $(2,3)$-orientable ones and Figure 2 for the non orientable one.

3.3.2. Largest $(2,3)$-orientable/non-orientable graphs

It was shown in [1] that the only complete graphs that are $(2,3)$-orientable are for $n\le 5$. For $n\ge 6$, Santana in [6] showed that for given $n\ge 6$ the maximum number of edges in a $(2,3)$-orientable graph is $$\begin{array}{}\text{(1)}& {\displaystyle (\genfrac{}{}{0ex}{}{n}{2})–\left\{{\displaystyle (\genfrac{}{}{0ex}{}{\lceil \frac{n}{2}\rceil }{2})+{\displaystyle (\genfrac{}{}{0ex}{}{\lfloor \frac{n}{2}\rfloor }{2})}}\right\}+\lceil \frac{1}{2}\left({\displaystyle (\genfrac{}{}{0ex}{}{n}{2})–\left\{{\displaystyle (\genfrac{}{}{0ex}{}{\lceil \frac{n}{2}\rceil }{2})+{\displaystyle (\genfrac{}{}{0ex}{}{\lfloor \frac{n}{2}\rfloor }{2})}}\right\}}\right)\rceil .}\end{array}$$ The proofs are similar to those in Section 3.1.2 above.

4. Linear operators on graphs

Let $T:{\mathcal{G}}_n\to {\mathcal{G}}_n$ be a mapping such that the image of a union of graphs is the union of the images of the graphs and that the image of the edgeless (empty) graph, $\overline{K_n}$, is the edgeless graph. Such a mapping is said to be a linear operator. Note that ${\mathcal{G}}_n$ is a semimodule over the set $\{0,1\}$ where addition is union and scalar multiplication is Boolean, that is for $X\in {\mathcal{G}}_n$, $0\cdot X=\overline{K_n}$ and $1\cdot X=X$. For convenience we use juxtaposition for multiplication and we denote $\overline{K_n}$ by $O$. So $T$ is a linear operator if for any $U,V\in {\mathcal{G}}_n$, $T(U\cup V)=T(U)\cup T(V)$ and $T(O)=O$.

Let $\mathcal{X}$ be a subset of ${\mathcal{G}}_n$. Then $T$ is said to preserve the set $\mathcal{X}$ if whenever $U\in \mathcal{X}$, $T(U)\in \mathcal{X}$. We say $T$ strongly preserves $\mathcal{X}$ if $T$ preserves $\mathcal{X}$ and $T$ preserves ${\mathcal{G}}_n\setminus \mathcal{X}$.

Proof. This follows from the fact that ${\mathcal{G}}_n$ is finite.

Since a vertex permutation merely changes the order of the vertices (an independent labeling), we have:

Note that a linear mapping on ${\mathcal{G}}_n$ is nonsingular if and only if the only graph mapped to the edgeless graph is the edgeless graph. Because this semi module uses union for addition, nonsingularity does not imply invertibility as in vector spaces over fields.

Thus, in view of the above example, we place more restrictions on $T$ in order to reasonably characterize preservers. This additional restriction is usually that $T$ preserves some other set or function, that $T$ is bijective, or, as below, that $T$ strongly preserves the set.

Proof. Suppose that $T(X)=O$ for some $X\in {\mathcal{G}}_n$. Then for any edge graph $E⊑X$ we have that $T(E)=O$. Let $H$ be the graph of: a) two parallel edges; b) a four cycle; or c) three parallel edges; one edge of which is $E$. Then, since $T(E)=O$, $T(H)=T(H\setminus E)$, a contradiction since $H$ is not: a) $({\mathcal{Z}}_2,+)$-cordial; b) $({\mathcal{Z}}_2,\times )$-cordial; or c) $(2,3)$-orientable while $H\setminus E$ is: a) $({\mathcal{Z}}_2,+)$-cordial; b) $({\mathcal{Z}}_2,\times )$-cordial: or c) $(2,3)$-orientable; respectively. Thus, in each case, $T$ is nonsingular.

Proof. Let $E$ be an edge graph and suppose that $L(E)⊒F$ where $F$ is an edge graph, $F\ne E$. Say $L(E)=Q\cup F$. Let $G$ be: a) a $({\mathcal{Z}}_2,+)$-cordial graph; b) a $({\mathcal{Z}}_2,\times )$-cordial graph; or c) a $(2,3)$-orientable graph; with the maximal number of edges such that $G⊒E$ and $G⋣F$. This choice is possible since for $n\ge 4$, the complete graph $K_n$ is not $({\mathcal{Z}}_2,+)$-cordial or $({\mathcal{Z}}_2,\times )$-cordial, and for $n\ge 6$, $K_n$ is not $(2,3)$-orientable. Then $L(G)=L(G\cup E)=L(G)\cup L(E)$. Then, $L(G)=L(G)\cup L(E)=L(G)\cup Q\cup F$, so that $L(G)=L^2(G)=L(L(G))=L(L(G)\cup L(Q)\cup L(F))=L^2(G)\cup L(F)\cup L(Q)=L(G)\cup L(F)\cup L(Q)=L(G\cup F\cup Q)$, a contradiction since $G$ is: a) a $({\mathcal{Z}}_2,+)$-cordial graph; b) a $({\mathcal{Z}}_2,\times )$-cordial graph; or c) a $(2,3)$-orientable graph, while $G\cup F\cup Q$ cannot be: a) a $({\mathcal{Z}}_2,+)$-cordial graph; b) a $({\mathcal{Z}}_2,\times )$-cordial graph; or c) a $(2,3)$-orientable graph; respectively, since it has too many edges. Thus $L$ maps edge graphs to edge graphs.

Proof. By Lemma 4.5, $L$ maps edge graphs to edge graphs. Thus, $L$ is not bijective if and only if the image of two edge graphs are equal. Suppose that $E$ and $F$ are distinct edge graphs such that $L(E)=L(F)$. Let $G$ be: a) a $({\mathcal{Z}}_2,+)$-cordial graph; b) a $({\mathcal{Z}}_2,\times )$-cordial graph; or c) a $(2,3)$-orientable graph; with the maximal number of edges such that $G⊒E$ and $G⋣F$. Then $L(G)=L(G\cup E)=L(G)\cup L(E)=L(G)\cup L(F)=L(G\cup F)$ a contradiction since $G$ is: a) a $({\mathcal{Z}}_2,+)$-cordial graph; b) a $({\mathcal{Z}}_2,\times )$-cordial graph; or c) a $(2,3)$-orientable graph, while $G\cup F$ cannot be: a) a $({\mathcal{Z}}_2,+)$-cordial graph; b) a $({\mathcal{Z}}_2,\times )$-cordial graph; or c) a $(2,3)$-orientable graph; respectively, since it has too many edges.. Thus $L$ is bijective on the set of edge graphs and since $L$ is linear $L$ is bijective on ${\mathcal{G}}_n$.

An interesting fact about idempotent maps on finite sets is that they are bijective if and only if they are the identity:

Proof. Assume that $\mathrm{\Phi }$ is bijective. Let $A\in \mathcal{K}$ and suppose that $\mathrm{\Phi }(A)=B$. Then, $\mathrm{\Phi }(B)=\mathrm{\Phi }(\mathrm{\Phi }(A))={\mathrm{\Phi }}^2(A)=\mathrm{\Phi }(A)$ (since $\mathrm{\Phi }$ is idempotent). So that $\mathrm{\Phi }(A)=\mathrm{\Phi }(B)$. Therefore $A=B$ since $\mathrm{\Phi }$ is bijective and hence, $\mathrm{\Phi }(A)=A$ for all $A\in \mathcal{K}$.

Note that because union is the addition in ${\mathcal{G}}_n$, any bijective map on ${\mathcal{G}}_n$ maps edge graphs to edge graphs and preserves $|E(G)|$, the number of edges in a graph

The next theorem uses the following lemma from [2]:

Proof. By Lemma 4.2, every vertex permutation strongly preserves the set of $({\mathcal{Z}}_2,+)$-cordial graphs, the set of $({\mathcal{Z}}_2,\times )$-cordial graphs and the set of $(2,3)$-orientable graphs. So we now assume that $T$ strongly preserves: a) the set of $({\mathcal{Z}}_2,+)$-cordial graphs; b)the set of $({\mathcal{Z}}_2,\times )$-cordial graphs, or c) the set of $(2,3)$-orientable graphs. Let $L=T^d$ where $d$ is chosen so that $L$ is idempotent. By Lemma 4.6, $L$ is bijective and hence the identity mapping. Now, suppose that $T(X)=T(Y)$. Then $T^{d-1}(T(X))=T^{d-1}(T(Y))$ so that $L(X)=T^d(X)=T^{d-1}(T(X))=T^{d-1}(T(Y))=T^d(Y)=L(Y)$. Since $L$ is the identity, we have $X=Y$. That is $T$ is injective and hence, by Lemma 4.1, $T$ is bijective. Since addition is union, the image of any edge graph is a edge graph. Thus, for any graph, $|E(G)|=|E(T(G))|$. That is, $T$ preserves $|E(G)|$.

Case 1. $T$ preserves the set of $({\mathcal{Z}}_2,+)$-cordial; graphs.

Let $E$ and $F$ be incident edges, so that $E\cup F$ is a 2-star (2-path) and suppose that $T(E\cup F)$ is a pair of non incident (parallel) edges. Then $E\cup F$ is $({\mathcal{Z}}_2,+)$-cordial while its image is not, a contradiction. That is $T$ maps 2-stars to 2-stars. By Lemma 4.8, $T$ is a vertex permutation.

Case 2. $T$ preserves the set of $({\mathcal{Z}}_2,\times )$-cordial; graphs.

Let $E$ and $F$ be incident edges, so that $E\cup F$ is a 2-star (2-path) and suppose that $T(E\cup F)$ is a pair of non incident (parallel) edges. Let $K$ be the edge joining the vertices of $E\cup F$ that forms a triangle. Let $G=E\cup F\cup K$. Then there are $3(n-3)$ edges that are adjacent to G. There are only three possible images of $G$ since $T$ is bijective and the image of any edge graph is an edge graph. $T(G)$ is either a 2-star with a non-incident edge, a three path or three mutually parallel edges (a $3K_2$ ). If $T(G)$ is a 2-star with a non-incident edge, there is only one edge added to $T(G)$ that results in a non $({\mathcal{Z}}_2,\times )$-cordial graph. If $T(G)$ is a $3K_2$, no edge added to $T(G)$ results in a non $({\mathcal{Z}}_2,\times )$-cordial graph, and if $T(G)$ is a three path, there are exactly three edges which, when any one is added to $T(G)$ would result in a non $({\mathcal{Z}}_2,\times )$-cordial graph. Since $G$ together with any one of the $3(n-3)$ edges adjacent to $G$ is a non $({\mathcal{Z}}_2,\times )$-cordial graph, so must its image be. Since we have shown that this is impossible, it follows that $T$ maps 2-stars to 2-stars. By Lemma 4.8, $T$ is a vertex permutation.

Case 3. $T$ preserves the set of $(2,3)$-orientable graphs.

Let $E$ and $F$ be incident edges, so that $E\cup F$ is a 2-star (2-path) and suppose that $T(E\cup F)$ is a pair of non incident (parallel) edges. Let $H$ be an edge graph such that the image of $H$ is an edge graph parallel to both $T(E)$ and $T(F)$. Then, $E\cup F\cup H$ is $(2,3)$-orientable while $T(E\cup F\cup H)$, being three parallel edges, is not $(2,3)$-orientable, a contradiction. That is $T$ maps 2-stars to 2-stars. By Lemma 4.8, $T$ is a vertex permutation.