A graph \(G\) is \(H\)-saturated if \(G\) does not have \(H\) as a subgraph but \(G + uv\) has at least one copy of \(H\) for any edge \(uv \notin E(G)\). The smallest number of edges of all \(H\)-saturated graphs of order \(n\) is called \(H\)-saturation number and is denoted by \(sat(n; H)\). In this paper, we establish the existence of \(C_{4}\)-saturated graphs with prescribed the number of edges in some length that is close to \(sat(n; C_{4})\).
We let \(G = (V(G), E(G))\) be a simple graph. The order of \(G\) is \(n = |V(G)|\) and the size of \(G\) is \(m = |E(G)|\). The complement of \(G\) is denoted by \(\overline{G}\). A cycle of \(n\) vertices is denoted by \(C_{n}\). A path of \(n\) vertices is denoted by \(P_{n}\). A complete \(k\)-partite graph with the partite sets of \(n_{1}, n_2, n_3, …, n_{k}\) vertices is denoted by \(K_{n_{1},n_2,n_3, …, n_{k}}\). When \(k = 2\), the graph \(K_{n_{1}, n_{2}}\) is called complete bipartite. A star is a complete bipartite \(K_{n_{1}, n_{2}}\) when \(1 \in \{n_{1}, n_{2}\}\). For graphs \(G\) and \(H\), we say that \(G\) is \(H\)-saturated if \(G\) does not have \(H\) as a subgraph but \(G + uv\) has a copy of \(H\) as a subgraph for any \(uv \notin E(G)\). The smallest size (the number of edges) of all \(H\)-saturated graphs of \(n\) vertices is called the \(H\)-saturation number and is denoted by \(sat(n; H)\). On the other hand, the largest size of all \(H\)-saturated graphs of \(n\) vertices is called the \(H\)-extremal number and is denoted by \(ex(n; H)\).
In 1907, Mantel [12] proved that graphs with maximum size that do not have a copy of \(K_{3}\) as a subgraph is the complete bipartite whose the two partite sets have equally likely the number of vertices. That is:
Theorem 1.1. [12] For a natural number \(n \geq 3\), we have that \[\begin{aligned} ex(n; K_{3}) = \left\lfloor \frac{n^2}{4} \right\rfloor. \end{aligned}\]
Further, a \(K_{3}\)-saturated graph \(G\) of order \(n\) satisfies \(|E(G)| = ex(n; K_{3})\) if and only if \(G\) is the complete bipartite graph \(K_{\lfloor \frac{n}{2}\rfloor, \lceil \frac{n}{2} \rceil}\).
In 1941, Turán [14] extended Theorem 1.1 by establishing \(K_{p}\)-saturated graphs, for any integer \(p \geq 3\), with the largest size.
Theorem 1.2. [14] For natural numbers \(n \geq p \geq 3\), we have that \[\begin{aligned} |E(G)| \leq ex(n; K_{p}) = \left(1 – \frac{1}{p – 1} \right)\frac{n^2}{2} + o(n^2). \end{aligned}\]
Further, a \(K_{p}\)-saturated graph \(G\) of order \(n\) satisfies \(|E(G)| = ex(n; K_{p})\) if and only if \(G\) is \(K_{n_{1}, n_2, n_3, …, n_{p – 1}}\) where \(n_{1} + n_{2}+n_3 + \cdots + n_{p – 1} = n\) and \(|n_{i} – n_{j}| \leq 1\) for all \(i, j \in \{1,2,3, …, p – 1\}\).
These has motivated many studies in \(ex(n; H)\) for arbitrary graphs \(H\). For instant, see Erdős and Gallai [5] for the study of \(ex(n; P_{k})\), Dogan [4] for the study of \(ex(n; K_{1, k})\) and Győri et al. [10] for the study of \(ex(n; C_{2k})\).
It can be asked, on the other hand, how the lower bound, \(sat(n; H)\), grows. In 1964, Erdős et al. [6] found the minimum size of \(K_{p}\)-saturated graphs. Interestingly, the growth of \(sat(n; K_{p})\) is just linear in terms of \(n\).
Theorem 1.3. [6] For integers \(n\) and \(p\) such that \(n \geq p – 2 \geq 1\), we have that \[\begin{aligned} sat(n; K_{p}) = \binom{p – 2}{2} + (n – p + 2)(p – 2). \end{aligned}\]
A \(K_{p}\)-saturated graph \(G\) satisfying \(|E(G)| = sat(n; K_{p})\) if and only if \(G\) is obtained by joining every vertex of \((p – 2)\)-clique to every vertex of \(\overline{K}_{n – p + 2}\).
For more example of the studies of \(sat(n; H)\), see Füredi and Kim [8] when \(H\) is a cycle and Kászonyi and Tuza [11] when \(H\) is a path, a star and a union of edges.
One other direction of the studies of \(H\)-saturated graphs is to establish the existence of these graphs having size between the upper and lower bounds. The first result was obtained in 1995 when Barefoot et al. [2] proved the existence of \(K_{3}\)-saturated graphs having sizes between the bounds. The result of [2] was generalized to \(K_{p}\)-saturated graphs when \(p \geq 3\) by Amin et al. [1], and was extended to \(C_{2k + 1}\)-saturated by Gould et al. [9].
When the length of cycle is even, Ollermann [13] and Tuza [15] independently established \(sat(n; C_{4})\) and Erdős [7] established \(ex(n; C_{4})\).
Theorem 1.4. ([7],[13] and [15] ) Let \(G\) be a \(C_{4}\)-saturated graph containing \(n\) vertices. Then \[\left\lfloor \frac{3n – 5}{2} \right\rfloor \leq |E(G)| \leq \frac{n}{4}\left(1 + \sqrt{4n – 3}\right).\]
To the best of our knowledge, there is no work that provided exact description of the edge spectrum for \(C_4\)-saturated graphs. Although uniquely \(C_4\)-saturated graphs (the graphs which the addition of any missing edge creates exactly one copy of \(C_4\)) have been investigated in [3], this work focused on structural characterizations rather than on attainable edge counts. As we mentioned earlier, the edge spectrum of odd cycle saturated graphs has been studied by Gould et al. [9] by determining the saturation spectrum of obtained by bipartite-based construction. However, we can not apply this construction to our \(C_{4}\)-saturated because a subgraph whose vertices in different partite sets always have \(C_{4}\). In this paper, we establish that, for infinitely many \(n\), there exist \(C_4\)-saturated graphs of order \(n\) and size \(m\) for every integer \(m\) ranging from \(3n/2\) to \(2n\).
In this section, we show our main results concerning the existence of \(C_{4}\)-saturated graphs. In the first subsection, we display \(C_{4}\)-saturated graphs of small orders while a construction for arbitrary large \(C_{4}\)-saturated graphs is provided in the next subsection.
In this section, we list \(C_{4}\)-saturated graphs of order at most \(12\), some of which may be the same as a particular case of our constructions in the next subsection. The bounds are obtained from Theorem 1.4.
We summarize the existences of \(C_4\)-saturated graphs from the list in the following table. The symbol “N/A” (not investigated) shows that we are not able to find a \(C_4\)-satirated graph having the order and size of that entry in which the graph might or might not exists.
| \text{n \textbackslash m} | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | 20 | 21 | 22 | 23 |
| 4 | – | \(F_1\) | – | – | – | – | – | – | – | – | – | – | – | – | – | – | – | – | – | – | – |
| 5 | – | – | \(F_2\) | \(F_3\) | – | – | – | – | – | – | – | – | – | – | – | – | – | – | – | – | – |
| 6 | – | – | – | \(F_4\) | \(F_5\) | N/A | – | – | – | – | – | – | – | – | – | – | – | – | – | – | – |
| 7 | – | – | – | – | – | \(F_6\) | \(F_7\) | N/A | – | – | – | – | – | – | – | – | – | – | – | – | – |
| 8 | – | – | – | – | – | – | \(F_8\) | \(F_9\) | \(F_10\) | N/A | – | – | – | – | – | – | – | – | – | – | – |
| 9 | – | – | – | – | – | – | – | – | \(F_11\) | \(F_12\) | \(G(3)\) | N/A | N/A | – | – | – | – | – | – | – | – |
| 10 | – | – | – | – | – | – | – | – | – | \(F_13\) | \(F_14\) | \(F_15\) | \(F_16\) | – | – | – | – | – | – | – | – |
| 11 | – | – | – | – | – | – | – | – | – | – | – | \(F_17\) | \(F_18\) | \(F_19\) | \(G(4)\) | N/A | N/A | N/A | – | – | – |
| 12 | – | – | – | – | – | – | – | – | – | – | – | – | \(F_20\) | \(F_21\) | N/A | N/A | N/A | N/A | N/A | N/A | N/A |
We first consider the case when the order \(n\) of \(C_{4}\)-saturated graphs is odd.
Construction. Let \(P=xyz\) be a path of length \(2\) and \(P^1=a_1b_1, P^2=a_2b_2, …, P^t=a_tb_t\) be \(t\) paths of length 1. The graph \(G(t)\) is constructed from \(P, P^1, P^2, …, P^t\) by adding edges from \(x\) to all \(a_1, a_2,a_3, …, a_t\), from \(z\) to all \(b_1, b_2, b_3,…, b_t\), and adding edges \(a_1a_2, a_3a_4,a_5a_6, …,\) \(a_{t-2}a_{t-1}, b_2b_3, b_4b_5,b_6b_7 …, b_{t-1}b_{t}\) when \(t\) is odd, and adding edges \(a_1a_2,\\ a_3a_4,a_5a_6, …, a_{t-1}a_{t}, b_2b_3, b_4b_5,b_6b_7, …, b_{t-2}b_{t-1}\) when \(t\) is even. Observe that \(|V(G(t))|=2t+3\) and \(|E(G(t))|=4t+1\).
Lemma 2.1. For \(t\geq2\), there exists a \(C_4\)-saturated graph with \(2t+3\) vertices and \(4t+1\) edges.
Proof. We first show that \(G(t)\) does not contain \(C_4\) as a subgraph. We may consider our graph according to the edges from the construction. We see that the smallest cycles that contain the edge \(a_1b_1\) are only \(a_1b_1zyxa_1\) \(a_1b_1zb_2a_2a_1\), which are not cycles of length \(4\). Hence, the edge \(a_1b_1\) is not contained in any \(C_4\). Similarly, the edges \(a_2b_2, \ldots, a_tb_t\) are not contained in any \(C_4\). We see that the smallest cycles that contain the edge \(a_1a_2\) must pass through either \(x\) or some vertex \(b_j\), and hence have length \(3\) or at least \(5\). Therefore, the edge \(a_1a_2\) is not contained in any \(C_4\). Similarly, the edges \(a_3a_4, a_5a_6, \ldots\) are not contained in any \(C_4\). Moreover, when \(t\) is odd, the edges \(b_2b_3, b_4b_5, b_6b_7, \ldots, b_{t-1}b_t\) are added, and when \(t\) is even, the edges \(b_2b_3, b_4b_5, \ldots, b_{t-2}b_{t-1}\) are added. In both cases, these edges are contained only in cycles of length \(3\) or at least \(5\), and hence are not contained in any \(C_4\). Thus, the edges \(xy, yz, xa_1, \ldots, xa_t, zb_1, \ldots, zb_t\) are not contained in any \(C_4\). Therefore, \(G(t)\) does not contain \(C_4\) as a subgraph.
It remains to show that \(G(t)+ab\) has a \(C_4\) for any non-edge \(ab \notin E(G(t))\).
Case 1. \(y\in \{a, b\}\) Without loss of generality \(y=a\). Clearly \(b\in \{a_1, a_2,a_3, …, a_t, b_1, b_2, b_3,\\…, b_t\}\). If \(b\in \{a_1, a_2,a_3, …, a_t\}\), \(b=a_i\) says, then \(ya_ib_izy\) is a \(C_4\). If \(b\in \{ b_1, b_2, b_3,…, b_t\}\), \(b=b_i\) says, then \(yb_ia_ixy\) is a \(C_4\). This proves Case 1.
Case 2. \(x\in \{a, b\}\) Without loss of generality \(x=a\). Thus \(b\in \{b_1, b_2,b_3, …, b_t, z\}\). If \(b=z\), then \(xzb_1a_1x\) is a \(C_4\). Hence we let \(b\in \{ b_1, b_2,b_3, …, b_t\}\), \(b=b_i\) says, We have \(xb_izyx\) is a \(C_4\). This proves Case 2.
Case 3. \(z\in \{a, b\}\) By similar arguments as Case 2, we prove this case.
Case 4. \(a_i\in \{a, b\}\) for some \(i\in \{1, 2, 3, …, t\}\) Without loss of generality \(a_i=a\). Thus \(b\in \{y, z, b_1, b_2, b_3, …, b_t, a_1, a_2, a_3, …, a_t\} \backslash \{b_i, a_j\}\), when \(a_ia_j \in E(G(t))\). It is possible that \(a_j\) does not exist when \(t\) is odd and \(i=t\). If \(b=y\), then \(a_iyzb_ia_i\) is a \(C_4\). If \(b=z\), then \(a_izyxa_i\) is a \(C_4\). If \(b=b_{i'}\), for some \(i'\in \{1, 2, 3, …, t\} \backslash \{i\}\), then \(a_ib_{i'}a_{i'}xa_i\) is a \(C_4\). Thus we consider when \(b=a_{i'}\) for some \(i'\in \{1, 2,3, …, t\} \backslash \{i\}\). If \(i\) is even, then \(a_ia_{i'}xa_{i-1}a_i\) is a \(C_4\). If \(i\) is odd but \(i<t\), then \(a_ia_{i'}xa_{i+1}a_i\) is a \(C_4\). If \(i\) is odd but \(i=t\), then \(a_ia_{i'}a_{i'-1}xa_i\) is a \(C_4\) when \(i'\) is even and \(a_ia_{i'}a_{i'+1}xa_i\) is a \(C_4\) when \(i'\) is odd. This proves Case 4.
Case 5. \(b_i\in \{a, b\}\) By similar arguments as Case 4, we prove this case. and this completes the proof. ◻
By Lemma 2.1 and the construction of \(G(t)\), we see that the graph \(G(3)\) has \(9\) vertices and \(13\) edges while the graph \(G(4)\) has \(11\) vertices and \(17\) edges. These graphs are counted in the list of Table 1.
A windmill graph \(W(t, k)\) is obtained from \(t\) cycles of \(k\) vertices by identifying one vertex of each cycle together and we call this the vertex \(c\). When \(t \geq 2\), it can be observed that \(W(t, 3)\) is a \(C_{4}\)-saturated graph of order \(2t + 1\) and size \(3t\). Further, for \(t \geq 1\), we let the graph \(W'(t, 3)\) be obtained from the graph \(W(t, 3)\) and two vertex \(x\) and \(y\) by joining \(x\) to a vertex of degree two of one cycle of length \(3\) and joining \(y\) to the other vertex of degree two of the same cycle. It can be observed that \(W'(t, 3)\) is a \(C_{4}\)-saturated graph of \(2t + 3\) vertices, containing \(3t + 2\) edges. Hence, by Lemma 2.1 and the graphs \(W(t, 3)\) and \(W'(t, 3)\), we have the existence of \(C_{4}\)-saturated graphs when \(n\) is odd.
Corollary 2.2. For an odd natural number \(n \geq 5\), there exists a \(C_{4}\)-saturated graph of \(n\) vertices, containing \(m\) edges where \(m \in \left\{\frac{3(n – 1)}{2} – 1, \frac{3(n – 1)}{2}, 2n – 5\right\}\).
When \(n\) is even, we let \(G'(t)\) be the graph obtained from \(G(t)\) and a vertex \(u\) by joining \(u\) to \(x\) and \(y\). By similar arguments of the proof of Lemma 2.1, we can show that \(G'(t)\) is a \(C_{4}\)-saturated graph of \(2t + 4\), having \(4t + 3\) edges. Further, we let \(G''(t)\) be the graph obtained from \(G'(t)\) and vertices \(v, w\) by joining \(v\) to \(y\) and \(z\) and joining \(w\) to \(y\). It can be checked that \(G''(t)\) is a \(C_{4}\)-saturated graph of \(2t + 6\) vertices, having \(4t + 6\) edges.
For the auxiliary of windmill graph, we let \(\hat{W}(t, 3)\) be obtained from \(W(t, 3)\) and a vertex \(z\) by joining \(z\) to the vertex \(c\). Hence, for \(t \geq 1\), \(\hat{W}(t, 3)\) is a \(C_{4}\)-saturated graph of \(2t + 2\) having \(3t + 1\) edges. Further, the graph \(\tilde{W}(t, 3)\) be obtained from \(W'(t, 3)\) and a vertex \(z\) by joining \(z\) to \(c\). It can be checked that the graph \(\tilde{W}(t, 3)\) is a \(C_{4}\)-saturated with \(2t + 4\) vertices, having \(3t + 3\) edges. Thus, we have the existence of \(C_{4}\)-saturated graphs when \(n\) is even as follows.
Corollary 2.3. For an even natural number \(n \geq 4\), there exists a \(C_{4}\)-saturated graph of \(n\) vertices, containing \(m\) edges where \(m \in \left\{\frac{3n}{2} – 3, \frac{3n}{2} – 2, 2n – 6, 2n – 5\right\}\).
Finally, we construct \(C_{4}\)-saturated graphs which can be varied the number of edges while the order is fixed.
Construction. The graph \(H(t_{1}, t_{2})\) is constructed from \(G(t_{1})\) and \(W(t_{2}, 3)\) by identifying the vertex \(y\) of \(G(t_{1})\) with the vertex \(c\) of \(W(t_{2}, 3)\). Observe that \(|V(H(t_{1}, t_{2}))|=2(t_1+t_2)+3\) and \(|E(H(t_{1}, t_{2}))|=4t_1+3t_2+1\). Further, the graph \(H'(t_{1}, t_{2})\) is constructed from \(G'(t_{1})\) and \(W(t_{2}, 3)\) by identifying the vertex \(y\) of \(G'(t_{1})\) with the vertex \(c\) of \(W(t_{2}, 3)\). Observe that \(|V(H'(t_{1}, t_{2}))|=2(t_1+t_2)+4\) and \(|E(H'(t_{1}, t_{2}))|=4t_1+3t_2+3\).
By the above construction, we can establish the following theorem. Let \[Spec_{C_{4}}(n) := \{ m : \exists\text{ a }C_4-\text{saturated graph }G\text{ on }n\text{ vertices with }|E(G)| = m \}.\]
Theorem 2.4. For positive integers \(n\) and \(t \geq 1\) such that \(n = 2t + 3\), we have that \[\begin{aligned} Spec_{C_{4}}(n) = \{3t + 2, 3t + 3, 3t+4, …, 4t + 1\}. \end{aligned}\]
Further, if \(n = 2t + 4\), we have that \[\begin{aligned} Spec_{C_{4}}(n) = \{3t + 4, 3t + 5,3t+6, …, 4t + 3\}. \end{aligned}\]
Proof. Let \(t = t_{1} + t_{2}\) where \(t_{1} \geq 1\) and \(t_{2} \geq 0\) are integers.
We first consider the case when \(n = 2t + 3\).
By construction, the graph \(H(t_1,t_2)\) is obtained from \(G(t_1)\) and \(W(t_2,3)\) by identifying the vertex \(y\) of \(G(t_1)\) with the vertex \(c\) of \(W(t_2,3)\). Hence, \[|V(H(t_1,t_2))| = |V(G(t_1))| + |V(W(t_2,3))| – 1 = (2t_1+3) + (2t_2+1) – 1 = 2t+3,\] and \[|E(H(t_1,t_2))| = |E(G(t_1))| + |E(W(t_2,3))| = (4t_1+1) + 3t_2 = 4t_1 + 3t_2 + 1.\]
Next, we show that \(H(t_1,t_2)\) does not contain a \(4\)-cycle. From the construction, by Lemma 2.1, Corollaries 2.2 and 2.3, both \(G(t_1)\) and \(W(t_2,3)\) do not contain \(C_4\). Moreover, these two graphs intersect in exactly one vertex. Consequently, any cycle in \(H(t_1,t_2)\) must be entirely contained in either \(G(t_1)\) or \(W(t_2,3)\). Since neither of them contains a cycle of length four, it follows that \(H(t_1,t_2)\) contains no \(C_4\).
We now show that adding any missing edge to \(H(t_1,t_2)\) creates a \(C_4\). Let \(uv\) be a non-edge of \(H(t_1,t_2)\). If both \(u\) and \(v\) belong to \(G(t_1)\), then, since \(G(t_1)\) is \(C_4\)-saturated, the graph \(G(t_1)+uv\) contains a \(C_4\), and hence so does \(H(t_1,t_2)+uv\). The same argument applies when both vertices lie in \(W(t_2,3)\). If \(u\) lies in \(G(t_1)\) and \(v\) lies in \(W(t_2,3)\), then together with the common vertex \(y\), the edge \(uv\) forms a \(4\)-cycle using edges of the construction. Therefore, every added edge produces a \(C_4\).
Thus, \(H(t_{1}, t_{2})\) is \(C_{4}\)-saturated having \(n = 2t + 3\) vertices. For each \(m \in \{3t + 2, 3t + 3, …, 4t + 1\}\), we can let \(m = 3t + 1 + i\) for some \(1 \leq i \leq t\). We let \(t_{1} = i\) and \(t_{2} = t – i\). Thus, for a given \(m\), the graph \(H(i, t – i)\) has \(2t + 3\) vertices and \(4i + 3(t – i) + 1 = 3t + 1 + i = m\) edges as required.
The argument for the case \(n = 2t + 4\) is analogous. The graph \(H'(t_1,t_2)\) satisfies \[|V(H'(t_1,t_2))| = 2t + 4 \quad \text{and} \quad |E(H'(t_1,t_2))| = 4t_1 + 3t_2 + 3.\]
As in the previous case, \(H'(t_1,t_2)\) contains no \(C_4\), and adding any missing edge creates a \(C_4\). Hence, \(H'(t_1,t_2)\) is \(C_4\)-saturated.
Therefore, for \(n = 2t + 4\), \[Spec_{C_4}(n) = \{3t + 4, 3t + 5, \ldots, 4t + 3\}.\]
This completes the proof. ◻
Example 2.5. The following table shows that when \(n=19\). We have
| \(t_1\) | \(t_2\) | \(m\) |
|---|---|---|
| 1 | 7 | 26 |
| 2 | 6 | 27 |
| 3 | 5 | 28 |
| 4 | 4 | 29 |
| 5 | 3 | 30 |
| 6 | 2 | 31 |
| 7 | 1 | 32 |
| 8 | 0 | 33 |
The first author has been supported by Petchra Pra Jom Klao Master Scholarship from King Mongkut’s University of Technology Thonburi (27/2566). The authors would like to express their sincere thank to Professor André Kündgen from California State University San Marcos for his valuable suggestion.
National Research Council of Thailand (NRCT) and King Mongkut’s University of Technology Thonburi (N42A660926).