Menu
Let \(G = (V, E)\) be a graph with vertex set \(V\) and edge set \(E\). An edge labeling \(f: E \to Z_{2}\) induces a vertex labeling \(f^{+} : V \to Z_{2}\) defined by \( f^{+}(v) \equiv \sum_{uv \in E} f(uv) \pmod 2 \), for each vertex \(v \in V\). For \(i \in Z_{2}\), let \( v_{f}(i) = |\{v \in V : f^+(v) = i\}| \) and \( e_{f}(i) = |\{e \in E : f(e) = i\}| \). An edge labeling \(f\) of a graph \(G\) is said to be edge-friendly if \( |e_{f}(1) – e_{f}(0)| \le 1 \). The set \(\{v_f(1) – v_f(0) : f \text{ is an edge-friendly labeling of } G\}\) is called the full edge-friendly index set of \(G\). In this paper, we shall determine the full edge-friendly index sets of one point union of cycles.
In this paper, all graphs are simple and connected. We refer to [1] for terms and notation that are not defined in this paper.
Since graph labelings was first introduced by Rosa, various labeling concepts have been introduced [2]. For example, cordial labeling, edge-friendly labeling, harmonious labeling, felicitous labeling, odd harmonious labeling and even harmonious labeling, semi-magic labeling, etc. Most graph labeling methods can be traced to the method introduced by Rosa [3] in 1967, or Graham and Sloane [4] in 1980.
Let \(G=(V,E)\) be a graph with vertex set \(V\) (or \(V(G)\)) and edge set \(E\) (or \(E(G)\)). A labeling \(f: E\to \mathbf{Z}_{2}\) induces a vertex labeling \(f^{+} : V\rightarrow \mathbf{Z}_{2}\) defined by \(f^{+}(v) \equiv \sum\limits_{uv\in E}f(uv)\pmod 2\), for each vertex \(v\in V\). Here \(\mathbf{Z}_2\) is the field of order 2.
For \(i\in \mathbf{Z}_{2}\), let \(v_{f}(i) = |\{v\in V\): \(f^+(v) = i\}|\) and \(e_{f}(i) = |\{e\in E\) : \(f(e) = i\}|\). The number \(v_f(1)-v_f(0)\) is denoted by \(I_f(G)\) and is called the edge-friendly index of \(f\).
An edge labeled by \(i\) is called an \(i\)-edge (under \(f\)). A vertex labeled by \(i\) is called an \(i\)-vertex (under \(f\)). In this paper, an edge labeling (or a \((0,1)\)-edge labeling) means an edge labeling whose codomain is \(\mathbf{Z}_2\). An edge labeling \(f\) of a graph \(G\) is said to be edge-friendly if \(| e_{f}(1) – e_{f}(0) |\le 1\).
Definition 1. The full edge-friendly index set of \(G\), denoted by FEFI\((G)\), is the set {\(I_f(G)\) :f is an edge-friendly labeling of G}.
The concept of full edge-friendly index set was introduced in [5]. Since \(v_f(1)+v_f(0)=|V|\), \[\label{eq-index}I_f(G)=2v_f(1)-|V|=|V|-2v_f(0).\tag{1}\] So the edge-friendly index of \(f\) of \(G\) is determined by the value of \(v_f(1)\).
Definition 2. Let \(f\) be an edge labeling of a graph \(G\) of order \(p\) and size \(q\). We fix the sequence of vertices \(V=\{v_1, v_2, \dots, v_p\}\) and the sequence of edges \(E=\{e_1,e_2,\dots, e_q\}\) of \(G\). The vector \(f(E)=(f(e_1), f(e_2), \dots, f(e_q))\in \mathbf{Z}_2^q\) is called an edge labeling vector of \(f\), where \(\mathbf{Z}_2^n\) denotes the Cartesian product of \(n\) copies of \(\mathbf{Z}_2\). Similarly, \[f^+(V)=(f^+(v_1), f^+(v_2),\dots, f^+(v_p))\in \mathbf{Z}_2^p\] is called a vertex labeling vector of \(f\).
For any (row) vector \(X\in \mathbf{Z}_2^n\), \(X^T\) denotes the transpose of \(X\).
Let \(M\) be the incidence matrix of a graph \(G\) according to fixed sequences of vertices and edges. Let \(f\) be an edge-labeling of \(G=(V,E)\). It is easy to see that \[f^+(V)^T=Mf(E)^T,\] which is a column vector of length \(p\) over \(\mathbf{Z}_2\).
For a vector \(X\in \mathbf{Z}_2^p\), the number of \(1\)’s in \(X\) is denoted by \(wt(X)\), the Hamming weight of \(X\). Hence, if \(f\) is an edge-friendly labeling of a graph \(G\), then \(wt(f^+(V))\) is \(v_f(1)\). For convenience, we will identify \(f\) with \(f(E)^T\). Hence \(v_f(1)=wt(f^+(V))=wt((Mf)^T)\).
Let \(H_i\) be a graph and \(v_i\in V(H_i)\) be fixed, \(1\le i\le t\). A one point union of \(H_i\), \(1\le i\le t\), is the graph obtained from the disjoint union of \(H_i\) by merging all \(v_i\) into a single vertex which is called the merged vertex or core vertex. So there will be many different one point unions of \(H_i\)’s.
If \(H_i=C_{n_i}\) is a cycle of order \(n_i\ge 3\), then all one point unions of \(H_i\), \(1\le i\le t\), are isomorphic. So we denote the one point union of \(C_{n_i}\), \(1\le i\le t\), by \(\biguplus\limits_{k=1}^t C_{n_k}\) for \(t\ge 2\). In this paper, we shall study the full edge-friendly index set of the graph \(\biguplus\limits_{k=1}^t C_{n_k}\).
For \(1\le k\le t\), let \(C_{n_k}=v_{k,1}v_{k,2}\cdots v_{k, n_{k}-1}v_{k, n_k}v_{k,1}\). Let \(e_{k, j}=v_{k, j}v_{k, j+1}\) for \(1\le j\le n_k\), where \(v_{k, n_k+1}=v_{k, 1}\). Let \(v_{k,1}\in V(C_{n_k})\) be the chosen vertex to be merged. We denote the core vertex of the graph \(G_t=\biguplus\limits_{k=1}^t C_{n_k}\) by \(c\) (or \(v_{0,0}\)). Note that \(G_t\) is of order \(\left(\sum\limits_{k=1}^t n_k\right) -t+1\) and of size \(\sum\limits_{k=1}^t n_k\). Following is the one point union of \(C_3\), \(C_4\) and \(C_6\), i.e., \(C_3\uplus C_4 \uplus C_6\).
In the rest of the paper, we will use the notation defined above.
In this section, necessary and sufficient conditions that give the extrema values of \(v_f(0)\) or \(v_f(1)\) are obtained. Following is Lemma 2.1 of [5,6].
Lemma 1. Let \(f\) be any edge labeling of a graph \(G=(V,E)\), then \(v_f(1)\) must be even.
Suppose there are \(s\) odd numbers among \(n_1,\dots, n_t\), where \(0\le s\le t\). Without loss of generality, we may assume that \(n_1, \dots, n_s\) are odd and the others are even. Note that, \(s=0\) means that there is no odd number; \(s=t\) means that there is no even number. Now \[\label{eq-order} v_f(1)+v_f(0)=|V(G_t)|=\sum_{k=1}^s n_k +\sum_{k=s+1}^t n_k -t+1\equiv s-t+1\pmod{2}.\tag{2}\] It is obvious that \(|V(G_t)|\ge v_f(0)\ge 0\) for any edge labeling \(f\) of \(G_t\). By Lemma 1 and the equation above, we have \[\label{eq-v0} v_f(0)\equiv s-t+1\pmod{2}.\tag{3}\] Hence \(v_f(0)\ge 1\) if \(t-s\) is even for any edge labeling \(f\) of \(G_t\). A natural question is that whether there is an edge-friendly labeling of \(G_t\) attaining the lower bound and whether there is an edge-friendly labeling of \(G_t\) attaining the upper bound.
Lemma 2. Suppose there are \(s\) odd numbers among \(n_1,\dots, n_t\). There is an edge-friendly labeling \(f\) of \(G_t\) such that
\(v_f(0)=1\) if and only if \(t-s\) is even;
\(v_f(0)=0\) if and only if \(t-s\) is odd.
Proof. The necessity of (1) and (2) come from Eq. (3).
Note that \(G_t\) is Eulerian. Let \(R\) be an Euler tour of \(G_t\). We label the edge of \(G_t\) by 0 and 1 alternatively along \(R\). Clearly the induced label of each vertex except the core is 1 and the label of the core \(c\) is \((t-s)~\mod{2}\). Hence we have the sufficiency of (1) and (2). 0◻
Obtaining the maximum value of \(v_f(0)\) is equivalent to obtaining the minimum value of \(v_f(1)\). ◻
Remark 1. If there are \(r\) numbers among \(n_1,\dots, n_t\) such that the sum of these numbers is \(\lfloor |E(G_t)|/2\rfloor\), then the sum of the remaining numbers is \(\lceil |E(G_t)|/2\rceil\). So, the statement ‘there are \(r\) numbers among \(n_1,\dots, n_t\) such that the sum of these numbers is \(\lfloor |E(G_t)|/2\rfloor\)’ is equivalent to the statement ‘there are \(r\) numbers among \(n_1,\dots, n_t\) such that the sum of these numbers is \(\lceil|E(G_t)|/2\rceil\)’.
Lemma 3. There is an edge-friendly labeling \(f\) of \(G_t\) such that \(v_f(1)=0\) if and only if there are \(r\) numbers among \(n_1,\dots, n_t\) such that the sum of these numbers is \(\lfloor |E(G_t)|/2\rfloor\).
Necessity. Consider the subgraph \(E_i\) induced by all \(i\)-edges of \(G_t\) under \(f\), \(i=0,1\). Since there is no 1-vertex, each cycle of \(G_t\) is entirely edge-labelled by 1’s or entirely edge-labelled by 0’s. Hence \(E_1\) is a one point union of some subcycles of \(G_t\). Hence \(E_0\) is also a one point union of some subcycles of \(G_t\), namely \(E_0\) is the one point union of \(r\) subcycles. Since \(f\) is edge-friendly, \(|E(E_0)|=\lfloor |E(G_t)|/2\rfloor\) or \(\lceil |E(G_t)|/2\rceil\). Thus we have the necessary condition by Remark 1.
[Sufficiency] Suppose there are \(r\) numbers among \(n_1,\dots, n_t\) such that the sum of such numbers is \(\lfloor |E(G_t)|/2\rfloor\). We label the edges of the corresponding cycles by 0 and label the other edges of \(G_t\) by 1. Thus this labeling is an edge-friendly labeling and the labels of all vertices are 0’s. ◻
The main results are given in this section. For a given one point union of cycles \(G_t=\biguplus\limits_{i=1}^t C_{n_i}\), we fix the sequences of vertices and edges with respect to the lexicographic order. Thus the incident matrix of \(G_t\) is \[M=\begin{pmatrix} Z_1 & Z_2 & \cdots & Z_{t-1} & Z_t\\ B_1 & O & \cdots & \cdots & O \\ O & B_2 & \ddots & \vdots & O\\ \vdots & \vdots & \ddots & \ddots & \vdots\\ O & O & \cdots & B_{t-1} & O\\ O & O & \cdots & O & B_{t} \end{pmatrix},\] where \(B_k=\left(\begin{matrix} 1 & 1 & 0 & \cdots & 0 & 0 & 0\\ 0 & 1 & 1 & \cdots & 0 & 0 & 0\\ 0 & 0 & 1 & \ddots & 0 & 0 & 0\\ \vdots & \vdots & \ddots & \ddots & \ddots & \vdots &\vdots\\ 0 & 0 & 0 & \cdots & 1 & 1 & 0\\ 0 & 0 & 0 & \cdots & 0 & 1 & 1\end{matrix}\right)_{(n_k-1)\times n_k}\) , \(Z_k=\left(\begin{matrix} 1 & 0 & \cdots & 0 & 1\end{matrix}\right)_{1\times n_k}\), and each \(O\) is a zero matrix of certain size, \(1\le k\le t\).
We define some notation and recall some known results first. For positive \(l\), let \(1_l\) be the row vector of length \(l\) whose entries are 1’s, and \(0_l\) be the row vector of length \(l\) whose entries are 0’s. Let \(\alpha_{2l}=(1,0, 1,0,\dots, 1,0)\in\mathbf{Z}_2^{2l}\) and \(\beta_{2l}=(0,1,0,1\dots, 0,1)\in\mathbf{Z}_2^{2l}\). For convenience, we let \(1_0\), \(0_0\), \(\alpha_{0}\) and \(\beta_0\) be the empty rows.
Let \(p=|V(G_t)|=\left(\sum\limits_{k=1}^t n_k\right) -t+1\). From (2), we have \(p\equiv s-t+1\pmod{2}\), where \(s\) is defined in Section 2. So \(t-s\) is odd if and only if \(p\) is even. From now on, we shall use \(q=\sum\limits_{k=1}^t n_k=|E(G_t)|\). For each edge labeling \(f=(Y_1, Y_2, \dots, Y_t)^T\), where \(Y_k\in \mathbf{Z}_2^{n_k}\), \(1\le k\le t\), we have \[Mf=\begin{pmatrix} \sum\limits_{k=1}^t Z_kY_k^T, & B_1Y_1^T, & \dots, & B_tY_t^T\end{pmatrix}^T.\] From (1) we have \[\begin{aligned} \text{FEFI}(G_t) & =\{2v_f(1)-p : f \text{ is an edge-friendly labeling of } G_t\}\\ &\subseteq \{4j-p : 0\le j\le \lfloor p/2\rfloor\} \end{aligned}\] For each possible value \(2j\) of the number of \(1\)-vertices, we want to find an edge-friendly labeling \(f\) such that \(v_f(1)=2j\).
We deal with some special cases first.
Theorem 1. Suppose all \(n_1,\dots, n_t\) are even.
Suppose there are \(r\) numbers among \(n_1,\dots, n_t\) such that the sum of these numbers is \(q/2\), then
\({\rm FEFI}(G_t)=\{4j-p : 0\le j\le p/2\}\) if \(t\) is odd;
\({\rm FEFI}(G_t)=\{4j-p : 0\le j\le (p-1)/2\}\) if \(t\) is even.
Suppose the sum of any combination of integers \(n_1,\dots, n_t\) is not equal to \(q/2\).
\({\rm FEFI}(G_t)=\{4j-p : 1\le j\le p/2\}\) if \(t\) is odd;
\({\rm FEFI}(G_t)=\{4j-p : 1\le j\le (p-1)/2\}\) if \(t\) is even.
Proof. For each \(i\) and
\(l\), \(1\le
i\le t\) and \(1\le l\le
n_i/2\), let \(Y_{i,l}=( 1_l, 0_l,
\alpha_{n_i-2l})\in \mathbf{Z}_2^{n_i}\). Thus, \(B_iY_{i,l}^T=( 0_{l-1},
1, 0_{l-1}, 1_{n_i-2l})^T\) and \(Z_iY_{i,l}^T=1\). Hence \[\label{eq-wt0}wt(B_iY_{i,l}^T)=n_i-2l+1.\tag{4}\]
For \(1\le k\le t\), let \(f=(Y_{1, n_1/2}, \dots, Y_{k-1,n_{k-1}/2}, Y_{k,
l}, Y_{k+1, 1}, \dots, Y_{t, 1})^T\). Thus,
\(Mf=(t\mod 2, B_1Y^T_{1, n_1/2}, \dots,
B^T_{k-1}Y_{k-1, n_{k-1}/2}, B^T_kY_{k,l}, B^T_{k+1}Y_{k+1,1}, \dots,
B^T_tY_{t,1})^T\). By (4) \[\label{eq-wt} v_f(1)=wt(Mf) =(t\mod 2)+
\sum\limits_{i=1}^{k-1} 1 + (n_k-2l+1)+\sum\limits_{i=k+1}^{t}
(n_i-1)\tag{5}\]
Without loss of generality, we assume \(\sum\limits_{k=1}^r n_k=q/2\). Thus \(\sum\limits_{k=r+1}^t n_k=q/2\). Since either \(r\) or \(t-r\) is at most \(t/2\). We may assume that \(r\le \lfloor t/2 \rfloor\) and \(t-r\ge\lceil t/2 \rceil\).
(1a) Suppose \(t\) is odd.
Step 1: For a fixed \(k\), \(1\le k \le
t\), let \(l\) be an integer
such that \(1\le l\le n_k/2\).
Let \(f\) be defined above, then (5) becomes
\[v_f(1)=wt(Mf)=1+\sum\limits_{i=k+1}^t n_i
+2k+n_k-2l-t= p-\sum_{i=1}^{k-1}n_i-2l+2k.\] For a fixed \(k\), when \(l\) runs through from \(1\) to \(n_k/2\), the range of \(v_f(1)\) is an increasing arithmetic
sequence with common difference \(2\)
from \(p-\sum\limits_{i=1}^kn_i +2k\)
to \(p-\sum\limits_{i=1}^{k-1}n_i-2+2k\). Thus
when \(k\) runs through from 1 to \(t\), the range of \(v_f(1)\) is an increasing arithmetic
sequence with common difference \(2\)
from \(p-\sum\limits_{i=1}^{t}n_i+2t=t+1\) to
\(p\).
Step 2: Let \(R\) be the Euler tour starts from the core \(c\) and travels the cycles \(C_{n_1}\), \(C_{n_2}\), \(\dots\), \(C_{n_t}\) in order. Denote \(R=u_1u_2u_3\cdots u_{\frac{q}{2}}u_{\frac{q}{2}+1}u_{\frac{q}{2}+2} \cdots u_{q}u_1\), where \(u_1=c\). In this case \(u_{\frac{q}{2}+1}=c\). There may have some \(u_i\)’s equal to \(c\). Let \(g=( 1_{\frac{q}{2}}, 0_{\frac{q}{2}})^T\), then \(v_g(1)=0\).
Step 3: Now we swap the labels of \(u_iu_{i+1}\) and \(u_{\frac{q}{2}+2i-1}u_{\frac{q}{2}+2i}\), \(1\le i\le \lfloor \frac{q}{2}\rfloor\), where the indices are taken in modulo \(q\). For each case, the number of 1-vertices increases by 2 if \(i=1\) or \(c\) is not incident with neither \(u_iu_{i+1}\) nor \(u_{\frac{q}{2}+2i-1}u_{\frac{q}{2}+2i}\); and may not change if \(c\) is incident with either \(u_iu_{i+1}\) or \(u_{\frac{q}{2}+2i-1}u_{\frac{q}{2}+2i}\) for \(i\ne 1\). The last case can occur at most \(2r-1\) times. So the number of 1-vertices increases by 2 at least \(\frac{q}{2}-2r+1\ge 2t -2\lfloor t/2\rfloor+1\ge t+1\) times. Thus, the number of 1-vertices runs through each even integers from 0 to \(t+1\) under the above swapping.
So we obtain all the possible values of the number of 1-vertices.
(1b) Suppose \(t\) is even.
Perform Step 1 as Case (1a). Now (5) becomes \[v_f(1)=wt(Mf) =0+\sum\limits_{i=k+1}^t n_i +2k+n_k-2l-t= p-\sum_{i=1}^{k-1}n_i-2l+2k-1.\] Similar to Case (1a), when \(k\) and \(l\) run through all possible values, \(v_f(1)\) runs through \(p-1\), \(p-3\), …, \(t\).
Perform Steps 2 and 3 as Case (1a). We obtain that the number of 1-vertices runs through each even integers from 0 to \(t\).
So we obtain all the possible values of the number of 1-vertices.
By Lemma 3, \(1\le v_f(1)\le p\) for any edge-friendly labeling \(f\). Without loss of generality, we assume that \(n_1\ge n_2 \ge \cdots \ge n_t\) and \(\sum\limits_{k=1}^r n_k< q/2 <\sum\limits_{k=r+1}^t n_k\). Here \(r \le \lfloor t/2\rfloor\).
(2a) Suppose \(t\) is odd. Do the same Step 1 as Case (1a) to obtain the edge labeling \(f\). Thus, we obtain that \(v_f(1)\) runs through \(p\), \(p-2\), …, \(p-\sum\limits_{i=1}^t n_i +2t=t+1\).
Let \(R\) be an Euler tour as in Case (1a). In this case, \(u_{\frac{q}{2}+1}\ne c\). Constructing the edge labeling \(g\) as in Case (1a), we get that \(v_g(1)=2\), since \(g^+(u_1)=g^+(c)=1\).
Do the same Step 3 as in Case (1a). Here we obtain that the number of 1-vertices runs through each even integers from 2 to \(t+1\).
So we obtain all the possible values of the number of 1-vertices.
(2b) Suppose \(t\) is even. By a similar procedure and argument, we obtain all possible values of the number of 1-vertices.
Hence this completes the proof. ◻
Theorem 2. Suppose all \(n_1,\dots, n_t\) are odd.
Suppose there are \(r\)
numbers among \(n_1,\dots, n_t\) such
that the sum of these numbers is \(\lfloor
q/2\rfloor\), then
\({\rm FEFI}(G_t)=\{4j-p : 0\le j\le
(p-1)/2\}\).
Suppose the sum of any combination of integers \(n_1,\dots, n_t\) is not equal to \(\lfloor q/2\rfloor\), then
\({\rm FEFI}(G_t)=\{4j-p : 1\le j\le
(p-1)/2\}\).
Proof. Recall that \(\alpha_{2l}=(1,0,\dots, 1,0)\in\mathbf{Z}_2^{2l}\) and \(\beta_{2l}=(0,1,\dots, 0,1)\in\mathbf{Z}_2^{2l}\); \(1_0\), \(0_0\), \(\alpha_{0}\) and \(\beta_0\) are the empty rows (see the beginning of this section).
For a fixed \(i\), \(1\le i \le \lceil t/2\rceil\), let \(l\) be an integer such that \(1\le l\le (n_i-1)/2\). Let \(Y_{i,l}=( 1_{l}, 0_{l-1}, \beta_{n_i+1-2l})\in \mathbf{Z}_2^{n_i}\), then \(B_iY_{i,l}^T=( 0_{l-1}, 1, 0_{l-1}, 1_{n_i-2l})^T\) and \(Z_iY_{i,l}^T=0\). Hence \(wt(B_iY_{i,l}^T)=n_i-2l+1\).
For a fixed \(i\), \(\lceil t/2\rceil+1 \le i \le t\), let \(l\) be an integer such that \(1\le l\le (n_i-1)/2\). Let \(Y_{i,l}=(0, 1_{l}, 0_{l}, \alpha_{n_i-1-2l})\in \mathbf{Z}_2^{n_i}\), then \(B_iY_{i,l}^T=(1, 0_{l-1}, 1, 0_{l-1}, 1_{n_i-1-2l})^T\) and \(Z_iY_{i,l}^T=0\). Hence \(wt(B_iY_{i,l}^T)=n_i-2l+1\).
Step 1: Let \(f=(Y_{1, (n_1-1)/2}, \dots, Y_{k-1,(n_{k-1}-1)/2}, Y_{k, l}, Y_{k+1, 1}, \dots, Y_{t, 1})^T\), where \(1\le k\le t\) and \(1\le l\le (n_k-1)/2\). Clearly \(f\) is edge-friendly. \[\begin{aligned} v_f(1)=wt(Mf)& =\sum\limits_{i=1}^{k-1} 2 + (n_k-2l+1)+\sum\limits_{i=k+1}^{t} (n_i-1)\\ & = p-\sum_{i=1}^{k-1} n_i -2l+3k-2. \end{aligned}\] One may check that when \(k\) and \(l\) run through all possible values, \(v_f(1)\) runs through \(p-1\), \(p-3\), …, \(p-\sum\limits_{i=1}^t n_i +3t-1=2t\).
Step 2: For \(1\le i\le \lceil t/2\rceil\), we define \(Y_{i, (n_i+1)/2}=( 1_{(n_i+1)/2}, 0_{(n_i-1)/2})\), then \(B_iY_{i, (n_i+1)/2}^T=( 0_{(n_i-1)/2}, 1, 0_{(n_i-3)/2})^T\) and \(Z_iY_{i, (n_i+1)/2}^T=1\). Hence \(wt(B_iY_{i, (n_i+1)/2}^T)=1\).
For \(\lceil t/2\rceil+1 \le i \le t\), we define \(Y_{i, (n_i+1)/2}=( 1_{(n_i-1)/2}, 0_{(n_i+1)/2})\). Here \(B_iY_{i, (n_i+1)/2}^T=( 0_{(n_i-3)/2}, 1, 0_{(n_i-1)/2})^T\) and \(Z_iY_{i, (n_i+1)/2}^T=1\). Hence \(wt(B_iY_{i, (n_i+1)/2}^T)=1\).
For each \(k\), \(1\le k\le t\), let \(f_k=(Y_{1, (n_1+1)/2}, \dots, Y_{k,(n_{k}+1)/2}, Y_{k+1, (n_{k+1}-1)/2}, \dots, Y_{t, (n_t-1)/2})^T\). Note that, \(f_t=(Y_{1, (n_1+1)/2}, \dots, Y_{t,(n_{t}+1)/2})^T\). Clearly \(f_k\) is edge-friendly. Suppose \(k\) is even. We have \(v_{f_k}(1)=wt(Mf_k)=(\{\sum_{i=1}^k 1\mod 2\}+k)+2(t-k)=(0+k)+2(t-k)=2t-k\).
One may check that when \(k\) runs through all even numbers from \(2\) to \(t\), \(v_{f_k}(1)\) runs through all even numbers from \(2t-2\) down to \(t\).
Now we shall perform some steps similar to Steps 2 and 3 in the proof of Theorem 1 to obtain the remaining possible values of the number of 1-vertices.
Without loss of generality, we assume that \(\sum\limits_{k=1}^r n_k=\lfloor q/2\rfloor\). Here \(r\le \lfloor t/2 \rfloor\).
Let \(R=u_1u_2u_3\cdots u_{\lfloor q/2\rfloor}u_{\lfloor q/2\rfloor+1}u_{\lfloor q/2\rfloor+2} \cdots u_{q}u_1\) be the Euler tour starts from the core \(u_1=c\) and travels the cycles \(C_{n_1}\), \(C_{n_2}\), \(\dots\), \(C_{n_t}\) in order. By convention \(u_{q+1}=u_1\).
Step 3: Define \(g=( 1_{\lfloor q/2\rfloor}, 0_{\lceil q/2\rceil})^T\). Now \(v_g(1)=0\).
Step 4:
When \(q=4m+1\), where \(m\ge 2\). Note that \(u_{2m+1}=c\), \(4m+1=\sum\limits_{i=1}^t n_i\ge 3t\) and \(t\) is odd. Swap the labels of \(u_iu_{i+1}\) and \(u_{2m+2i-1}u_{2m+2i}\), \(1\le i\le m+1\). The number of 1-vertices increases by 2 at least \((m+1)-(r-1)\) times, since the first swapping increases \(v_g(1)\) by 2.
Next, swap the labels of \(u_{m+1+i}u_{m+2+i}\) and \(u_{2i-1}u_{2i}\), \(1\le i\le m-1\). So the number of 1-vertices increases by 2 at least \(m-1-r\) times.
By the same argument as Step 3 in the proof of Theorem 1, the number of 1-vertices increases by 2 at least \(2m+1-2r\ge (3t-1)/2+1-t=(t+1)/2\) times totally. Thus, the number of 1-vertices runs through each even integer from 0 to \(t+1\) under the above swapping.
When \(q=4m+3\), where \(m\ge 2\) (in this case \(q\) cannot be 7). Note that \(u_{2m+2}=c\), \(4m+3=\sum\limits_{i=1}^t n_i\ge 3t\) and \(t\) is odd.
Swap the labels of \(u_iu_{i+1}\) and \(u_{2m+2i}u_{2m+2i+1}\), \(1\le i\le m+1\). Next, swap the labels of \(u_{m+1+i}u_{m+2+i}\) and \(u_{2i-1}u_{2i}\), \(1\le i\le m\).
Totally, the number of 1-vertices increases by 2 at least \((2m+1)-2r+1\ge (3t-3)/2+2-t= (t+1)/2\) times. Thus, the number of 1-vertices runs through each even integer from 0 to \(t+1\) under the above swapping.
When \(q=4m\), where \(m\ge 3\) (in this case \(q\) cannot be 8). Note that \(u_{2m}=c\), \(4m=\sum\limits_{i=1}^t n_i\ge 3t\) and \(t\) is even.
Swap the labels of \(u_iu_{i+1}\) and \(u_{2m+2i-1}u_{2m+2i}\), \(1\le i\le m\). Next, swap the labels of \(u_{m+i}u_{m+i+1}\) and \(u_{2i-1}u_{2i}\), \(1\le i\le m-1\).
Totally, the number of 1-vertices increases by 2 at least \((2m-1)-2r+1\ge 3t/2-t= t/2\) times. Thus, the number of 1-vertices runs through each even integer from 0 to \(t\) under the above swapping.
When \(q=4m+2\), where \(m\ge 1\). Note that \(u_{2m+1}=c\), \(4m+2=\sum\limits_{i=1}^t n_i\ge 3t\) and \(t\) is even.
Swap the labels of \(u_iu_{i+1}\) and \(u_{2m+2i}u_{2m+2i+1}\), \(1\le i\le m+1\). Next, swap the labels of \(u_{m+1+i}u_{m+i+2}\) and \(u_{2i-1}u_{2i}\), \(1\le i\le m\).
Totally, the number of 1-vertices increases by 2 at least \((2m+1)-2r+1\ge 3t/2+1-t= t/2+1\) times. Thus, the number of 1-vertices runs through each even integer from 0 to \(t+2\) under the above swapping.
Without loss of generality, we assume that \(n_1\ge n_2 \ge \cdots \ge n_t\) and \(\sum\limits_{k=1}^r n_k< q/2 <\sum\limits_{k=r+1}^t n_k\). Here \(r \le \lfloor t/2\rfloor\). We do the same procedure as Case 1. The only difference is \(v_g(1)=2\). Hence the number of 1-vertices at least runs through each even integer from 2 to \(t\) under the above swapping.
This completes the proof. ◻
Example 1. Consider the graph \(C_5 \uplus C_3\uplus C_3 \uplus C_3 \uplus C_3\). Here \(t=5\), \(p=13\), \(q=17\), \(m=4\) and \(r=2\). Let \(R=u_1u_2\cdots u_{17}u_1\) be an Euler tour of the graph, where \(u_1=u_6=u_9=u_{12}=u_{15}=c\). For \(1\le i\le 17\), let \(e_i=u_iu_{i+1}\), where \(u_{18}=u_1\).
The procedure of Steps 2 listed below: \[\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c} & e_1 & e_2 & e_3 & e_4 & e_5 & e_6 & e_7 & e_8 & e_9 & e_{10} & e_{11} & e_{12} & e_{13} & e_{14} & e_{15} & e_{16} & e_{17} & v(1)\\\hline f_1 & 1 & 1 & 1 & 0 & 0 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 10\\ f_2 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 8\\ f_3 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & 8\\ f_4 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 & 6\\ f_5 & 1 & 1 & 1 & 0 & 0 & 1 & 1 & 0 & 1 & 1 & 0 & 1 & 0 & 0 & 1 & 0 & 0 & 6\\ \end{array}\]
The procedure of swapping (Steps 3 and 4) listed below start from
\(g=( 1_8, 0_9)\).
\[\begin{array}{c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c}
& e_1 & e_2 & e_3 & e_4 & e_5 & e_6 & e_7
& e_8 & e_9 & e_{10} & e_{11}& e_{12} & e_{13}
& e_{14} & e_{15} & e_{16} & e_{17} & v(1)\\\hline
g & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 &
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &
0\\\hline
& 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1
& 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &
2\\
& 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1
& 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 &
4\\
& 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1 & 1
& 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 &
6\\
& 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 1
& 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 &
6\\
& 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 1
& 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 &
6\\\hline
& 1 & 0 & 0 & 0 & 0 & 0 & 1 & 1 & 1
& 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 &
8\\
& 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1
& 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 &
10\\
& 1 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1
& 0 & 1 & 0 & 1 & 0 & 1 & 0 & 1 &
10\\\hline
\end{array}\]
Example 2. Consider the graph \(C_3\uplus C_3\). Here \(t=2\), \(p=5\), \(q=6\), \(m=1\) and \(r=1\). Let \(R=u_1u_2\cdots u_{6}u_1\) be an Euler tour of the graph, where \(u_1=u_4=c\). For \(1\le i\le 6\), let \(e_i=u_iu_{i+1}\), where \(u_{7}=u_1\).
The procedure of Steps 3 and 4 listed below start from \(g=( 1_3, 0_3)\). \[\begin{array}{c|c|c|c|c|c|c|c} & e_1 & e_2 & e_3 & e_4 & e_5 & e_6 & v(1) \\\hline g & 1 & 1 & 1 & 0 & 0 & 0 & 0\\\hline & 0 & 1 & 1 & 1 & 0 & 0 & 2\\ & 0 & 0 & 1 & 1 & 0 & 1 & 4\\\hline & 1 & 0 & 0 & 1 & 0 & 1 & 4\\\hline \end{array}\]
Lemma 4. Let \(G\) and \(H\) be two graphs with only one common vertex \(u\). Suppose \(f_G\) and \(f_H\) be two edge-friendly labelings of \(G\) and \(H\), respectively. If \((f_G^+(u), f_H^+(u))\ne (1,1)\), then there is an edge-friendly labeling \(h\) of \(G\uplus H\) such that \(v_h(1)=v_{f_G}(1)+v_{f_H}(1)\). If \((f_G^+(u), f_H^+(u))=(1,1)\), then there is an edge-friendly labeling \(h\) of \(G\uplus H\) such that \(v_h(1)=v_{f_G}(1)+v_{f_H}(1)-2\).
Proof. Let \(h\) be the combined labeling of \(f_G\) and \(f_H\). We obtain the lemma easily. ◻
Theorem 3. Let \(p\) and \(q\) be the order and the size of \(G_t\), respectively.
Suppose there are \(r\) numbers among \(n_1,\dots, n_t\) such that the sum of these numbers is \(\lfloor q/2\rfloor\), then \({\rm FEFI}(G_t)=\{4j-p : 0\le j\le \lfloor p/2\rfloor\}\).
Suppose there are no \(r\) numbers among \(n_1,\dots, n_t\) such that the sum of these numbers are \(\lfloor q/2\rfloor\), then \({\rm FEFI}(G_t)=\{4j-p : 1\le j\le \lfloor p/2\rfloor\}\).
Proof. Without loss of generality, we assume that \(n_1, \dots, n_{s}\) are even and \(n_{s+1},\dots, n_t\) are odd, where \(0\le s\le t\). When \(s = 0\) or \(s = t\), we get the results using Theorem 1 and Theorem 2.
By Lemma 3, it suffices to find an edge-friendly labeling \(f\) of \(G_t\) such that \(v_f(1)\) runs through all even numbers in \([2, p]\).
Let \(G=\biguplus\limits_{i=1}^{s} C_{n_i}\) and \(H=\biguplus\limits_{i=s+1}^{t} C_{n_i}\). Let \(p_G\) and \(p_{H}\) be orders of \(G\) and \(H\), respectively. Note that \(p_H\) is odd and \(p=p_G+p_H-1\).
By Theorem 1 there is an edge-friendly labeling \(f_G\) of \(G\) such that \(v_{f_G}(1)\) at least runs through all even numbers of \([2, p_G]\), and by Theorem 2 there is an edge-friendly labeling \(f_H\) of \(H\) such that \(v_{f_H}(1)\) at least runs through all even numbers of \([2, p_H-1]\).
By Lemma 4, in the worst case, there is an edge-friendly labeling \(h\) of \(G\uplus H\) such that \(v_h(1)\) runs through all even numbers of \([4, p_G+p_H-1-2]=[4, p-2]\).
Now we only need to find an edge-friendly labeling \(g\) of \(G\uplus H\) such that \(v_g(1)\) is \(p\) when \(p\) is even, or \(p-1\) when \(p\) is odd, or else, \(v_g(1)\) is 2 (see 1⃝ and 2⃝ below).
Let \(R=u_1u_2u_3\cdots u_{\lfloor q/2\rfloor}u_{\lfloor q/2\rfloor+1}u_{\lfloor q/2\rfloor+2} \cdots u_{q}u_1\) be the Euler tour of \(G_t\) starts from the core \(u_1=c\). Note that \(q=p+t-1\) and \(\deg(c)=2t\).
When \(q\) is even, \(p\equiv t-1\pmod{2}\). Define \(g=(1,0,1,0,\dots, 1,0)^T\in\mathbf{Z}_2^q\), then \(g^+(c)=t\mod 2\). Hence \(v_g(1)=\begin{cases}p &\textit{if $t$ is odd,}\\ p-1&\textit{if $t$ is even,}\end{cases}=\begin{cases}p &\textit{if $p$ is even,}\\ p-1&\textit{if $p$ is odd.}\end{cases}\)
When \(q\) is odd, \(p\equiv t\pmod{2}\). Define \(g=(1,0,1,0,\dots, 1,0,1)^T\in\mathbf{Z}_2^q\), then \(g^+(c)=t+1\mod 2\). Hence \(v_g(1)=\begin{cases}p-1 &\textit{if $t$ is odd,}\\ p&\textit{if $t$ is even,}\end{cases}=\begin{cases}p-1 &\textit{if $p$ is odd,}\\ p &\textit{if $p$ is even.}\end{cases}\)
Suppose \(u_{\lfloor q/2\rfloor+1}\ne c\). Define \(g=( 1_{\lfloor q/2\rfloor}, 0_{\lceil q/2\rceil})^T\). Thus only \(g^+(c)=g^+(u_{\lfloor q/2\rfloor+1})=1\). Hence \(v_g(1)=2\).
Suppose \(u_{\lfloor q/2\rfloor+1}= c\), then \(u_2\ne c\) and \(u_{\lfloor q/2\rfloor+2}\ne c\). Define \(g=(0, 1_{\lfloor q/2\rfloor}, 0_{\lceil q/2\rceil-1})^T\). Thus only \(g^+(u_2)=g^+(u_{\lfloor q/2\rfloor+2})=1\). Hence \(v_g(1)=2\).
This completes the proof. ◻
We denote the graph \(G_t\) by \(C_n^{(t)}\) when \(n_1=\cdots=n_t=n\). When \(n=3\), \(C_3^{(t)}\) is called the Dutch \(t\)-windmill graph. By Theorem 3, we have the following corollaries.
Corollary 1. Suppose \(n\ge 3\) and \(t\ge 2\). Now, the order of \(C_n^{(t)}\) is \(p=nt-t+1\).
Suppose \(n\) is odd, then \[{\rm FEFI}(C_n^{(t)})=\begin{cases} \{4j-p : 1\le j\le (p-1)/2\} &\textit{ if $t$ is odd};\\ \{4j-p : 0\le j\le (p-1)/2\} &\textit{ if $t$ is even}. \end{cases}\]
Suppose \(n\) is even, then \[{\rm FEFI}(C_n^{(t)})=\begin{cases} \{4j-p : 1\le j\le p/2\} &\textit{ if $t$ is odd};\\ \{4j-p : 0\le j\le (p-1)/2\} &\textit{ if $t$ is even}. \end{cases}\]
Corollary 2. For \(t\geq 2\), \[{\rm FEFI}(C_{3}^{(t)})=\begin{cases} \{4j-2t-1 : 1\leq j\leq t\} & \text{ if $t$ is odd};\\ \{4j-2t-1 : 0\leq j\leq t\} & \text{ if $t$ is even}. \end{cases}\]
The first author was partially supported by National Natural Science Foundation of China (No: 12371344).
The authors have no relevant financial or non-financial interests to disclose.
All authors contributed to the study conception and design. Material preparation and analysis were performed by all the authors. The first draft of the manuscript was written by Zhen-Bin Gao and all authors commented on previous versions of the manuscript. All authors read and approved the final manuscript.