Electronic Journal of Graph Theory and Applications

Grant Fickes^a, Tony W. H. Wong*b

gfickes@email.sc.edu, wong@kutztown.edu

The edge-distinguishing chromatic number (EDCN) of a graph G is the minimum positive integer k such that there exists a vertex coloring \(c:V(G)\to\{1,2,\ldots,k\}\) whose induced edge labels \(\{c(u),c(v)\}\) are distinct for all edges uv. Previous work has determined the EDCN of paths, cycles, and spider graphs with three legs. In this paper, we determine the EDCN of petal graphs with two petals and a loop, cycles with one chord, and spider graphs with four legs. These are achieved by graph embedding into looped complete graphs.

Keywords: vertex coloring, edge-distinguishing, graph embedding, EDCN, caterpillars, petal graphs, chorded cycles, spiders Mathematics Subject Classification: 05C15, 05C60, 05C45 DOI: 10.5614/ejgta.2022.10.2.5

1. Introduction

Let the graph G be composed of a simple graph together with at most one loop at each vertex, and let V(G) and E(G) be the vertex set and the edge set of G respectively. Let \([k] = \{1, 2, \ldots, k\}\) denote a set of k colors, and let \(\binom{[k]}{i}\) denote the set of i-subsets of [k]. For every vertex coloring \(c:V(G)\to [k]\), there is an induced edge coloring \(c':E(G)\to \binom{[k]}{1}\cup \binom{[k]}{2}\), defined by

Received: 16 February 2021, Revised: 13 April 2022, Accepted: 17 April 2022.

^&lt;sup>a</sup>Department of Mathematics, University of South Carolina, USA

^&lt;sup>b</sup>Department of Mathematics, Kutztown University of Pennsylvania, USA

^*corresponding author

\(c'(uv) = \{c(u), c(v)\}\) for each edge uv. A vertex coloring c is considered edge-distinguishing if c' is injective. The edge-distinguishing chromatic number (EDCN) of G, denoted by \(\lambda(G)\), is the minimum integer k such that an edge-distinguishing vertex coloring with k colors exists for G.

The concept of coloring certain elements of a graph G to distinuouish another set of elements associated with G has many variations. For instance, the problem of vertex-distinguishing edge coloring has been studied in the literature [2, 4, 5], and the problem of distinguishing graph automorphisms through vertex coloring has also been studied [8, 15].

This notion of edge-distinguishing vertex coloring, also called a line-distinguishing vertex coloring, was first introduced by Frank et al. [12]. This problem was further studied by Al-Wahabi et al. [3], Zagaglia Salvi [16], Fickes and Wong [11], etc. Brunton et al. [7] considered the case when the edge coloring function c' is also surjective. It is worth mentioning that the more popular notion of harmonious chromatic number typically refers to a slight variation of the EDCN [14]. More specifically, if G is a simple graph, then the harmonious chromatic number of G, denoted by h(G), is the minimum integer k such that an edge-distinguishing proper vertex coloring with k colors exists for G. It is obvious that \(\lambda(G) \leq h(G)\).

Determining \(\lambda(G)\) for a general graph G is NP-complete [13]. Consequently, most work in the literature focuses on providing bounds on h(G) and thus \(\lambda(G)\) [1] or studying the asymptotic behavior of h(G) [6] for various families of graphs G. When trying to determine the exact formula for \(\lambda(G)\) or h(G), only very limited families have been tackled. For example, \(\lambda(G)\) is determined for paths and cycles [3, 12], and h(G) is determined for complete r-ary trees [10].

We are interested in determining the exact formula for the EDCN of other families of graphs; however, pushing the results from paths and cycles to other graphs seems formidable, and it has not been done since the 1980's until very recently. A path is a tree with maximum degree 2, so a natural extension of a path is a spider graph, which has a unique vertex with degree at least 3, often called the central vertex. Each path between the central vertex and a leaf (i.e., a degree 1 vertex) is called a leg. We denote a spider graph as \(S_{\ell_1,\ell_2,\dots,\ell_\Delta}\), where \(\Delta \geq 3\) is the number of legs, and \(1 \leq \ell_1 \leq \ell_2 \leq \ldots \leq \ell_\Delta\) represent the number of edges in each leg. Here are some published results on the EDCNs of paths, cycles, and spider graphs in the literature.

Theorem 1.1 ([3, 12]). Let \(G = P_n\) be a path with n vertices. Then

\[\lambda(P_n) = \begin{cases} 1 & \text{if } n \leq 2; \text{ and } \\ \min\left\{2\left\lceil\sqrt{\frac{n-2}{2}}\right\rceil, 2\left\lceil\frac{1+\sqrt{8n-7}}{4}\right\rceil - 1\right\} & \text{if } n \geq 3. \end{cases}\]

Theorem 1.2 ([3, 12]). Let \(G = C_n\) be a cycle with n vertices, where \(n \ge 3\). Then

\[\lambda(C_n) = \min\left\{2\left\lceil\sqrt{\frac{n}{2}}\right\rceil, 2\left\lceil\frac{1+\sqrt{8n+1}}{4}\right\rceil - 1\right\}.\]

Theorem 1.3 ([11]). Let \(S_{\ell_1,\ell_2,\ell_3}\) be a spider graph with 3 legs, where \(\ell_1 + \ell_2 + \ell_3 = L\). Then

\[\lambda(S_{\ell_1,\ell_2,\ell_3}) = \begin{cases} 3 & \text{if } 3 \leq L \leq 6 \text{ and } \ell_1 = 1; \\ 4 & \text{if } L = 6 \text{ and } \ell_1 = 2; \\ \left\lceil \frac{-1+\sqrt{1+8L}}{2} \right\rceil & \text{if } L \geq 7 \text{ and } \left\lceil \frac{-1+\sqrt{1+8L}}{2} \right\rceil \text{ is odd; and } \\ \left\lceil \sqrt{2L-4} \right\rceil & \text{otherwise.} \end{cases}\]

Theorem 1.4 ([11]). Let S`1,`2,...,`<sup>∆</sup> be a spider graph with ∆ legs, where 2 ≤ `ⁱ ≤ ∆+3 2 for each 1 ≤ i ≤ ∆. Then

\[\lambda(S_{\ell_1,\ell_2,\dots,\ell_{\Delta}}) = \Delta + 1.\]

Although the edge-distinguishing chromatic number was introduced almost 40 years ago, the above list seemingly exhausts all major progress on the EDCN of various families of graphs. In this paper, we extend this list by studying spider graphs with four legs. The technique used to obtain Theorem 1.3 was too cumbersome to apply, so we adopt a different approach here. We try to "fold up" or embed a spider graph with four legs into petal graphs and cycles with one chord to aid our discussions. Through this method, we determine the EDCN of three families of graphs: some petal graphs, all cycles with one chord, and all spider graphs with four legs.

To determine the EDCN of various graphs, let us first introduce a simple tool to establish lower bounds.

Proposition 1.1 ([11]). Let G be a simple graph with maximum degree ∆(G). Then λ(G) ≥ ∆(G). Furthermore, if there exists a vertex u of G such that deg(u) = ∆(G) and every neighbor of u has degree > 1, then λ(G) ≥ ∆(G) + 1.

Next, we present the main tool to determine the EDCN of a graph, namely Theorem 1.5. Let K^k denote the complete graph on k vertices {v0, v1, v2, . . . , vk−1}, and let viv^j denote the edge between vertices vⁱ and v^j . If we attach a loop vivⁱ at every vertex vⁱ of Kk, then we obtain a new graph, which is denoted by K^∗ k . In other words,

\[K_k^* = K_k \cup \{v_0 v_0, v_1 v_1, v_2 v_2, \dots, v_{k-1} v_{k-1}\}.\]

A graph homomorphism is a function from the vertex set of one graph to the vertex set of another that preserves edges. An embedding of a graph G in K^∗ k refers to a graph homomorphism from G to K^∗ k that induces an injection from E(G) to E(K^∗ k ).

Theorem 1.5 ([12]). Let G be a simple graph, and let k be a positive integer. Then λ(G) ≤ k if and only if there is an embedding of G in K^∗ k .

Another trivial but useful observation is the following.

Proposition 1.2. Let H be a subgraph of G. If G can be embedded in K^∗ k , then H can also be embedded in K^∗ k , and hence, λ(H) ≤ λ(G).

In Section 2, we begin by proving the necessary and sufficient conditions to embed a subfamily of caterpillar trees in K^{∗ k} when k is odd. Then, we proceed to prove the necessary and sufficient conditions to embed "petal graphs" with two petals and one loop, cycles with one chord, and finally spider graphs with four legs in K^∗ k . For each of these families of graphs, the treatment for odd k is different from even k, so we separate our discussion on odd and even k into Sections 2 and 3 respectively. Lastly, in Section 4, we determine the EDCN of these petal graphs, chorded cycles, and spider graphs.

2. k is odd

2.1. Caterpillars

In the study of graph labelings, caterpillar trees are often the first object studied after paths. Naturally, this is where our discussion begins.

Definition 1. Let \(\ell\) be a positive integer and m be a nonnegative integer. Let \(CP_{\ell}^{i_1,i_2,\dots,i_m}\) denote a caterpillar tree with the central path \(y_0y_1y_2\cdots y_\ell\) and m extra edges \(y_{\ell+1}y_{i_1}, y_{\ell+2}y_{i_2},\dots,y_{\ell+m}y_{i_m}\), where \(0 < i_1 \le i_2 \le \dots \le i_m < \ell\).

If \(i_1, i_2, \ldots, i_m\) are distinct and \(m \leq k\), then we would like to embed such caterpillar trees in \(K_k^*\) with all the extra edges \(y_{\ell+1}y_{i_1}, y_{\ell+2}y_{i_2}, \ldots, y_{\ell+m}y_{i_m}\) embedded as loops. Hence, the main question is whether we can embed the central path \(y_0y_1y_2\cdots y_\ell\) in \(K_k^*\) such that \(y_{i_1}, y_{i_2}, \ldots, y_{i_m}\) are mapped to distinct vertices. The following theorem by Dvořák et. al. answers our question positively with only a few exceptions.

Theorem 2.1 ([9]). Let \(k \geq 3\) be odd, let \(C = z_0 z_1 z_2 \cdots z_{\binom{k}{2}-1} z_0\) be a cycle of length \(\binom{k}{2}\) such that exactly k vertices, namely \(z_{i_1}, z_{i_2}, \ldots, z_{i_k}\), are black, where \(0 \leq i_1, i_2, \ldots, i_k \leq \binom{k}{2} - 1\). Then there exists an embedding of C in \(K_k\) that is injective on the black vertices if and only if either \(k \neq 5\) or k = 5 and \(\{i_1, i_2, i_3, i_4, i_5\} \not\equiv \{0 + c, 3 + c, 4 + c, 6 + c, 7 + c\}\) or \(\{0 + c, 1 + c, 3 + c, 7 + c, 9 + c\}\) (mod 10) for every \(c \in \mathbb{Z}_{10}\).

This result is paramount to the proof of the following theorem.

Theorem 2.2. Let k be odd, and let \(m \leq k\). Consider caterpillar trees \(CP_\ell^{i_1,i_2,\dots,i_m}\) such that \(0 < i_1 < i_2 < \dots < i_m < \ell\) and \(CP_\ell^{i_1,i_2,\dots,i_m} \neq CP_4^{1,3}\). Such caterpillar trees can be embedded in \(K_k^*\) if and only if \(\ell + m \leq {k+1 \choose 2}\).

Proof. The number of edges in \(CP_{\ell}^{i_1,i_2,\dots,i_m}\) and \(K_k^*\) are \(\ell+m\) and \(\binom{k+1}{2}\) respectively, so \(\ell+m \leq \binom{k+1}{2}\) is a necessary condition for \(CP_{\ell}^{i_1,i_2,\dots,i_m}\) to be embedded in \(K_k^*\).

To prove that the condition is sufficient, if \(\ell' + m < \binom{k+1}{2}\), we can first consider \(CP_{\ell'}^{i_1,i_2,\dots,i_m}\) as a subgraph of \(CP_{\ell}^{i_1,i_2,\dots,i_m}\), where \(\ell + m = \binom{k+1}{2}\). Due to Proposition 1.2, it suffices to show that \(CP_{\ell}^{i_1,i_2,\dots,i_m}\) can be embedded in \(K_k^*\) if \(\ell + m = \binom{k+1}{2}\) and \(CP_{\ell}^{i_1,i_2,\dots,i_m} \neq CP_4^{1,3}\).

If k=1, then \(\ell+m=\binom{k+1}{2}=1\), implying that \(\ell=1\) and m=0. It is obvious that \(CP_1\), which is a path with two vertices, can be embedded in \(K_1^*\), which is a loop at one vertex. If k=3 or 5, we exhaust all possible caterpillar trees that satisfy the given conditions, and the only caterpillar tree that cannot be embedded in \(K_k^*\) is \(CP_4^{1,3}\). If \(k\geq 7\), we need the following claim so that we can apply Theorem 2.1 in our proof.

Claim: If \(k \ge 7\) and m < k, then there exists a set

\[B = \{y_{j_1}, y_{j_1+1}, y_{j_2}, y_{j_2+1}, \dots, y_{j_{k-m}}, y_{j_{k-m}+1}\}\]

of 2(k-m) distinct vertices, where \(j_1 < j_2 < \cdots < j_{k-m} < \ell\), such that \(\{y_{i_1}, y_{i_2}, \dots, y_{i_m}\} \cap B = \emptyset\).

Proof of Claim: Let

\[J = \{j \in \mathbb{N} : j < \ell, \ j \text{ is odd, and } \{j, j + 1\} \cap \{i_1, i_2, \dots, i_m\} = \emptyset\}.\]

Note that \(\left\lfloor \frac{\ell}{2} \right\rfloor \geq \frac{1}{2}(\ell-1) = \frac{1}{2}\left(\binom{k+1}{2} - m - 1\right) \geq \frac{1}{2}\left(\binom{k+1}{2} - k\right) = \frac{1}{2}\binom{k}{2} \geq k\) when \(k \geq 7\). Hence, \(|J| \geq \left\lfloor \frac{\ell}{2} \right\rfloor - m \geq k - m\). As a result, our claim follows by picking distinct integers \(j_1, j_2, \ldots, j_{k-m}\) from J.

Assume \(k \geq 7\). Let \(CP_{\ell}^{i_1,i_2,\dots,i_m}\) be a caterpillar tree that satisfies the conditions given by the statement of the theorem. Let \(j_0 = -1\) and \(j_{k-m+1} = \ell\), and if m < k, then let B be the set of vertices as provided by the claim. Let

\[\phi: \{y_0, y_1, y_2, \dots, y_{\ell+m}\} \to \{z_0 = z_{\binom{k}{2}}, z_1, z_2, \dots, z_{\binom{k}{2}-1}\}\]

be defined such that

\[\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\]

This function defines an embedding from \(CP_{\ell}^{i_1,i_2,\dots,i_m}\) to a graph \(\mathcal{C}^*\) that consists of a cycle \(z_0z_1z_2\cdots z_{\binom{k}{2}-1}z_{\binom{k}{2}}\) of length \(\binom{k}{2}\) together with the set of k loops

\[\{\phi(y_{i_{\gamma}})\phi(y_{\ell+\gamma}): 1 \le \gamma \le m\} \cup \{\phi(y_{j_{\beta+1}})\phi(y_{j_{\beta+1}+1}) = z_{j_{\beta+1}-\beta}z_{j_{\beta+1}-\beta}: 0 \le \beta \le k-m-1\}.\]

Note that these k loops are at distinct vertices due to the constructions in our claim and our function \(\phi\).

Define the cycle C by removing all the loops from \(C^*\) and coloring the vertices

\[\phi(y_{i_1}), \phi(y_{i_2}), \dots, \phi(y_{i_m}), \phi(y_{j_1}), \phi(y_{j_2}), \dots, \phi(y_{j_{k-m}})\]

black. Note that these are all the vertices that have loops in \(C^*\). By Theorem 2.1, there exists an embedding of C in \(K_k\) that is injective on the black vertices. As a result, there is an embedding of \(C^*\) in \(K_k^*\) with the loops embedded as loops, which completes our proof.

2.2. Petal graphs

A petal graph can be considered as a resultant graph by connecting the legs of a spider graph. It can also be considered as a resultant graph by identifying vertices of a chorded cycle. Hence, it is logical to study the embedding of petal graphs in \(K_k^*\) prior to the subsections on cycles with one chord and spider graphs.

Definition 2. Let \(m \in \mathbb{N}\) such that \(m \geq 2\), and let \(c_1, c_2, \ldots, c_m \in \mathbb{N}\) such that \(c_1 \leq c_2 \leq \cdots \leq c_m\). Let \(P_{c_1, c_2, \ldots, c_m}\) be the petal graph that has vertices \(u_0, u_1^1, u_2^1, \ldots, u_{c_1-1}^1, u_1^2, u_2^2, \ldots, u_{c_2-1}^m, \ldots, u_1^m, u_2^m, \ldots, u_{c_m-1}^m\), and for each \(i=1,2,\ldots,m\), the edges form a cycle \(u_0u_1^iu_2^i\ldots u_{c_i-1}^iu_0\) of length \(c_i\), which is called the i-th petal of the petal graph. If \(c_i=1\), then the i-th petal of \(P_{c_1,c_2,\ldots,c_m}\) is simply a loop.

Figure 1. Petal graph \(P_{1,1,2,3,5,6}\)

We are going to show that petal graphs \(P_{1,c_2,c_3}\) can be embedded in \(K_k^*\) when k is odd as long as some trivial necessary conditions are satisfied.

Theorem 2.3. If k is odd, then \(P_{1,c_2,c_3}\) can be embedded in \(K_k^*\) if and only if \(c_2 \ge 3\) and \(1+c_2+c_3 \le {k+1 \choose 2}\).

Proof. The only if direction is trivial. For the if direction, let \(n=c_2+c_3\). If \(k\leq 3\), then \(n\leq {3+1\choose 2}-1=5\), contradicting that \(c_2\geq 3\). Hence, it is only meaningful to consider \(k\geq 5\). In all of the following cases, we embed the first petal \(u_0u_0\) of \(P_{1,c_2,c_3}\) as the loop \(v_0v_0\) in \(K_k^*\).

Without loss of generality, we can assume that \(n > {k-1 \choose 2} - 1\). Otherwise, if \(n \le {k-1 \choose 2} - 1\), we can consider embedding \(P_{1,c_2,c_3}\) in \(K_{k-2}^*\), which can be further embedded in \(K_k^*\) trivially. Let \(h = {k+1 \choose 2} - 1 - n\) be the gap between n and \({k+1 \choose 2} - 1\). Based on our assumption, \(0 \le h \le {k+1 \choose 2} - 1 - {k-1 \choose 2} = 2k - 2\).

To embed \(P_{1,c_2,c_3}\) in \(K_k^*\), after embedding the petal \(u_0u_0\) as the loop \(v_0v_0\) in \(K_k^*\), it suffices to partition the edges of \(K_k^* - v_0v_0\) into three subgraphs \(H_0\), \(H_1\), and \(H_2\) that satisfy all the following conditions.

• 1. The number of edges in \(H_0\), \(H_1\), and \(H_2\) are h, \(c_2\), and \(c_3\) respectively.
• 2. After removing isolated vertices, \(H_1\) and \(H_2\) are connected.
• 3. The degree of \(v_0\) in each of \(H_1\) and \(H_2\) is positive.
• 4. All degrees in \(H_0\), \(H_1\), and \(H_2\) are even.

This is because the petals \(u_0u_1^2u_2^2\cdots u_{c_2-1}^2u_0\) and \(u_0u_1^3u_2^3\cdots u_{c_3-1}^3u_0\) can then be embedded as \(H_1\) and \(H_2\) respectively, since \(H_1\) and \(H_2\) are Eulerian by conditions 2 and 4, and \(u_0\) can be embedded as \(v_0\) by condition 3.

Construction of \(H_1\)

Let \(\ell\) be the unique odd integer such that \(\binom{\ell-1}{2}-1 < c_2 \leq \binom{\ell+1}{2}-1\). Note that \(\ell \geq 3\). Let \(g = \binom{\ell+1}{2}-1-c_2\) be the gap between \(c_2\) and \(\binom{\ell+1}{2}-1\), which satisfies \(0 \leq g \leq \binom{\ell+1}{2}-1-\binom{\ell-1}{2}=2\ell-2\). Let S be the set of g edges in \(K_k^*\) defined as

\[S = \begin{cases} \{v_1v_1, v_2v_2, \dots, v_gv_g\} & \text{if } 0 \leq g \leq \ell-1; \text{ and } \\ \{v_0v_1v_2 \cdots v_{\ell-1}v_0, v_1v_1, v_2v_2, \dots, v_{g-\ell}v_{g-\ell}\} & \text{if } \ell \leq g \leq 2\ell-2. \end{cases}\]

Let \(V_1 = \{v_0, v_1, v_2, \dots, v_{\ell-1}\}\) and \(V_2 = \{v_\ell, v_{\ell+1}, \dots, v_{k-1}\}\). Let \(L_1\) and \(L_2\) be the induced subgraphs of \(K_k^*\) on \(V_1\) and \(V_2\) respectively, and let \(L_b\) be the complete bipartite graph between \(V_1\) and \(V_2\).

Define the subgraph \(H_1\) as \(L_1 - v_0v_0 - S\). It is clear from the construction that the following conditions hold.

• 1. The number of edges in \(H_1\) is \(c_2\).
• 2. After removing \(V_2\), \(H_1\) is connected since
  • if \(\ell=3\), then \(g=\binom{\ell+1}{2}-1-c_2=5-c_2\leq 5-3=2\), so \(H_1\) contains the cycle \(v_0v_1v_2v_0\); and
  • if \(\ell > 3\), then \(H_1\) contains the cycle \(v_0v_2v_4\cdots v_{\ell-1}v_1v_3\cdots v_{\ell-2}v_0\).
• 3. The degree of \(v_0\) is positive since \(H_1\) is connected after \(V_2\) is removed.
• 4. All degrees in \(H_1\) are even.

Construction of \(H_0\)

Let g' be the number of loops in S. If \(h \le g'\), then let \(H_0\) be the subgraph that contains h loops in S. Otherwise, we have the following claim.

Claim 1: If h > g', then \(k > \ell\).

Proof of Claim 1: If \(k=\ell\), then \(\binom{k-1}{2} \leq c_2 \leq c_3\), thus \(0 \leq h = \binom{k+1}{2} - 1 - n \leq \binom{k+1}{2} - 1 - 2c_2 \leq \binom{k+1}{2} - 1 - 2\binom{k-1}{2} = \frac{-(k-6)(k-1)}{2}\), which implies k=5 and \(h \leq 2\). Note that \(\binom{5-1}{2} \leq c_2 \leq \frac{1}{2} \left(\binom{5+1}{2} - 1\right)\), so \(c_2 = 6\) or 7. Hence, \(g = \binom{5+1}{2} - 1 - c_2 = 8\) or 7, meaning that S = 6 has 8 or 7 edges. As a result, the number of loops in S, denoted by S = 6 or 2. However, S = 6 contradicting the condition that S = 6 or 3.

Under the assumption that h>g', we have \(k-\ell\geq 2\). Index the vertices in \(V_1-\{v_0\}\) in pairs as \(v_{2s-1}\) and \(v_{2s}\), where \(1\leq s\leq \frac{\ell-1}{2}\), and index the vertices in \(V_2\) in pairs as \(v_{\ell+2t-2}\) and \(v_{\ell+2t-1}\), where \(1\leq t\leq \frac{k-\ell}{2}\). Since \(\ell\geq 3\), the number of edges in the complete bipartite graph between \(V_1-\{v_0\}\) and \(V_2\) is \((\ell-1)(k-\ell)\geq 2(k-3)=2k-6\). Let h'=h-g'. We are going to define \(H_0\) based on the following cases.

Case 1: \(k-\ell \geq 4\). Let \(\widetilde{h}\) be the smallest positive integer such that \(h' \equiv \widetilde{h} \pmod 4\). Note that \(h' - \widetilde{h} < h' \leq h \leq 2k-2\). Together with the fact that \(h' - \widetilde{h} \equiv 2k-2 \equiv 0 \pmod 4\), we have \(h' - \widetilde{h} \leq 2k-6\).

Define the subgraph \(H_0\) as the disjoint union of

• \(\frac{h'-\tilde{h}}{4}\) copies of 4-cycles \(v_{2s-1}v_{\ell+2t-2}v_{2s}v_{\ell+2t-1}v_{2s-1}\),
• g' loops in S, and
• \(\widetilde{h}\) loops in \(L_2\).

The number of edges in \(H_0\) is \(\frac{h'-\widetilde{h}}{4} \cdot 4 + g' + \widetilde{h} = h' + g' = h\), and it is clear that all degrees in \(H_0\) are even.

Case 2: \(k-\ell=2\), i.e., \(\ell=k-2\). The number of edges in \(K_k^*-v_0v_0-H_0\) is at least \(2c_2\), so \(h' \leq h \leq {k+1 \choose 2}-1-2c_2 \leq {k+1 \choose 2}-1-2{\ell-1 \choose 2} = {k+1 \choose 2}-1-2{k-3 \choose 2} = \frac{1}{2}(-k^2+15k-26)\), in

addition to the usual bound \(h' \le h \le 2k - 2\). In order for \(\frac{1}{2}(-k^2 + 15k - 26)\) to be nonnegative, we must have \(k \le 13\). Here is a list of values of \(k \le 13\) and the corresponding upper bounds on h.

Claim 2: If k < 13, then h' < 2k - 4.

Proof of Claim 2: Since \(h' \le h\), the only possible cases for h' > 2k - 4 are when (k, h) = (5, 7), (5, 8), (7, 11), and (7, 12). Note that \(\max\left\{3, \binom{k-3}{2}\right\} = \max\left\{3, \binom{\ell-1}{2}\right\} \le c_2 \le \frac{1}{2}\left(\binom{k+1}{2} - 1 - h\right)\). When k = 5 and h = 7 or 8, we have \(c_2 = 3\), so \(H_1\) is the cycle \(v_0v_1v_2v_0\), and g' = 2. Hence, h' = h - g' = 5 or 6. When k = 7, we have

\[c_2 = \begin{cases} 6, \ 7, \text{ or } 8 & \text{if } h = 11; \text{ and} \\ 6 \text{ or } 7 & \text{if } h = 12. \end{cases}\]

As a result, \(H_1\) is the union of the cycle \(v_0v_2v_4v_1v_3v_0\) and \(c_2-5\) loops in \(L_1-v_0v_0\). Hence,

\[g' = \begin{cases} 3, \ 2, \text{ or } 1 & \text{if } h = 11; \text{ and} \\ 3 \text{ or } 2 & \text{if } h = 12. \end{cases}\]

This implies

\[h' = h - g' = \begin{cases} 8, \ 9, \text{ or } 10 & \text{if } h = 11; \text{ and} \\ 9 \text{ or } 10 & \text{if } h = 12. \end{cases}\]

In all cases, \(h' \leq 2k - 4\). This completes the proof of Claim 2.

Next, let \(\widetilde{h}\) be the smallest nonnegative integer such that \(h' \equiv \widetilde{h} \pmod 4\), which is slightly different from Case 1. Note that Claim 2, together with the fact that \(h' - \widetilde{h} \equiv 2k - 2 \equiv 0 \pmod 4\), implies \(h' - \widetilde{h} \leq 2k - 6\). If \(\widetilde{h} \leq 2\), define the subgraph \(H_0\) as the union of

• 4-cycles \(v_{2s-1}v_{k-2}v_{2s}v_{k-1}v_{2s-1}\), where \(1 \le s \le \frac{h'-\widetilde{h}}{4}\),
• g' loops in S, and
• \(\widetilde{h}\) loops in \(L_2\).

If \(\widetilde{h} = 3\), define the subgraph \(H_0\) as the union of

• 4-cycles \(v_{2s-1}v_{k-2}v_{2s}v_{k-1}v_{2s-1}\), where \(1 \le s \le \frac{h'-\widetilde{h}}{4}\),
• g' loops in S, and
• the triangle \(v_{k-3}v_{k-2}v_{k-1}v_{k-3}\).

The number of edges in \(H_0\) is \(4 \cdot \frac{h' - \widetilde{h}}{4} + g' + \widetilde{h} = h' + g' = h\), and it is clear that all degrees in \(H_0\) are even.

Construction of \(H_2\)

Define the subgraph \(H_2\) as \(K_k^* - v_0v_0 - H_0 - H_1\). From the construction, the following conditions hold.

• 1. The number of edges in \(H_2\) is \(\binom{k+1}{2} 1 h c_2 = n c_2 = c_3\).
• 2. After removing isolated vertices in \(V_1\), \(H_2\) is connected due to the following analysis.
  • If \(h \le g'\) and \(k = \ell\), then as provided in the proof of Claim 1, k = 5 and S contains the cycle \(v_0v_1v_2v_3v_4v_0\), which is completely contained in \(H_2\) since \(H_0\) does not contain any edges in this cycle.
  • If \(h \leq g'\) and \(k > \ell\), then \(H_2\) contains both \(L_2\) and \(L_b\).
  • If h > g', then by Claim 1, \(k > \ell\). Hence, in \(H_2\), \(v_0\) is connected with all vertices in \(V_2\), and vertices \(v_1, v_2, \ldots, v_{\ell-1}\) are either isolated vertices and thus removed, or are connected to \(v_0\) through the cycle \(v_0v_1v_2\cdots v_{\ell-1}v_0\).
• 3. The degree of \(v_0\) in \(H_2\) is positive due to item 2.
• 4. All degrees in \(H_2\) are even since all degrees in \(K_k^*\), \(v_0v_0\), \(H_0\), and \(H_1\) are even.

2.3. Cycles with one chord

Caterpillar trees are natural extensions of paths, while chorded cycles are natural extensions of cycles. In this section, we are going to study cycles with one extra chord.

Definition 3. Let \(C_n^{\{0,j\}}\) be a cycle on n vertices \(w_0, w_1, w_2, \ldots, w_{n-1}\) with a chord between \(w_0\) and \(w_j\). Without loss of generality, let \(2 \le j \le \frac{n}{2}\), which also implies \(n \ge 4\). Note that \(j \ne 1\), as \(w_0w_1\) is already in the cycle \(C_n\).

Note that \(C_n^{\{0,2\}}\) contains a triangle \(w_0w_1w_2w_0\). When it is embedded in \(K_k^*\), this triangle creates an obstruction if n is very close to \(\binom{k+1}{2}\). This is reflected by the extra complication in the statement of the following theorem.

Theorem 2.4. Let k be odd. Then \(C_n^{\{0,2\}}\) can be embedded in \(K_k^*\) if and only if \(n \leq \binom{k+1}{2} - 3\). When \(j \geq 3\), then \(C_n^{\{0,j\}}\) can be embedded in \(K_k^*\) if and only if \(n \leq \binom{k+1}{2} - 1\).

Proof. If \(k \leq 3\), then it is obvious that \(C_n^{\{0,j\}}\) cannot be embedded in \(K_k^*\). Also, \(k \leq 3\) is ruled out implicitly by \(4 \leq n \leq \binom{k+1}{2} - 3\) as well as \(6 \leq 2j \leq n \leq \binom{k+1}{2} - 1\). Hence, it is only meaningful to consider \(k \geq 5\).

If \(C_n^{\{0,2\}}\) can be embedded in \(K_k^*\), then note that the vertices in the triangle \(w_0w_1w_2w_0\) must be embedded as distinct vertices in \(K_k^*\). Otherwise, we will create double edges or multiple loops at the same vertex, which do not exist in \(K_k^*\). Without loss of generality, assume that \(w_0, w_1, w_2\) are embedded as \(v_0, v_1, v_2\) respectively. The degrees of \(w_0\) and \(w_2\) in the path \(w_2w_3\cdots w_{n-1}w_0\) are odd, while the degrees of \(v_0\) and \(v_2\) in \(K_k^* - v_0v_1v_2v_0\) are even. To create odd degree vertices at \(v_0\) and \(v_2\) in \(K_k^* - v_0v_1v_2v_0\), if we were to forgo only one edge from \(K_k^* - v_0v_1v_2v_0\), that edge must be \(v_0v_2\). However, \(v_0v_2\) does not exist in \(K_k^* - v_0v_1v_2v_0\), so at least two edges are forgone from \(K_k^* - v_0v_1v_2v_0\) when the path \(w_2w_3\cdots w_{n-1}w_0\) is embedded in \(K_k^* - v_0v_1v_2v_0\). Therefore, \(n+1 \leq {k+1 \choose 2}-2\), or \(n \leq {k+1 \choose 2}-3\).

If \(n \leq \binom{k+1}{2} - 3\), without loss of generality, we can assume that \(n > \binom{k-1}{2} - 3\). Otherwise, if \(n \leq \binom{k-1}{2} - 3\), we can consider embedding \(C_n^{\{0,2\}}\) in \(K_{k-2}^*\), which can be further embedded in \(K_k^*\) trivially. Let \(h = \binom{k+1}{2} - 3 - n\) be the gap between n and \(\binom{k+1}{2} - 3\). Based on our assumption, \(0 \leq h \leq \binom{k+1}{2} - 3 - \binom{k-1}{2} - 2 = 2k - 2\). Let H be defined such that

\[H = \begin{cases} \{v_0v_3v_2, v_0v_0, v_1v_1, v_2v_2, \dots, v_{h-1}v_{h-1}\} & \text{if } 0 \leq h \leq k; \\ \{v_0v_4v_1v_3v_4v_4v_2, v_0v_0, v_1v_1, \dots, v_{h-5}v_{h-5}\} & \text{if } k = 5 \text{ and } 6 \leq h \leq 8; \text{ and} \\ \{v_0v_3v_2, v_{k-1}v_1v_3v_4v_5 \cdots v_{k-1}, \\ v_0v_0, v_1v_1, v_2v_2, \dots, v_{h-k+1}v_{h-k+1}\} & \text{if } k \geq 7 \text{ and } k+1 \leq h \leq 2k-2. \end{cases}\]

Note that the number of edges in H is h+2 in all cases. Now, the chorded cycle \(C_n^{\{0,2\}}\) can be embedded in \(K_k^*\) such that \(w_0\), \(w_1\), \(w_2\) are embedded as \(v_0\), \(v_1\), and \(v_2\) respectively, and the path \(w_2w_3\cdots w_{n-1}w_0\) is embedded as the Eulerian path in \(K_k^*-v_0v_1v_2v_0-H\). This is because the only odd degree vertices in the graph \(K_k^*-v_0v_1v_2v_0-H\) are \(v_0\) and \(v_2\), and this graph is connected after isolated vertices are removed.

When \(j \geq 3\), the only if direction is trivial. For the if direction, the chorded cycle \(C_n^{\{0,j\}}\) can be embedded in the petal graph \(P_{1,j,n-j}\) as follows: the chord \(w_0w_j\) is embedded as the first petal \(u_0u_0\), the path \(w_0w_1w_2\cdots w_j\) is embedded as the second petal \(u_0u_1^2u_2^2\cdots u_{j-1}^2u_0\), and the path \(w_jw_{j+1}\cdots w_{n-1}w_0\) is embedded as the third petal \(u_0u_1^3u_2^3\cdots u_{n-j-1}^3u_0\). Theorem 2.3 completes the proof.

2.4. Spider graphs with three or four legs

We have provided the definition of spider graphs in Section 1, but it is more convenient for our future discussions if we formalize notation.

Definition 4. Let \(\Delta \in \mathbb{N}\) such that \(\Delta \geq 3\), and let \(\ell_1, \ell_2, \ldots, \ell_\Delta \in \mathbb{N}\) such that \(\ell_1 \leq \ell_2 \leq \ldots \leq \ell_\Delta\). Let \(S_{\ell_1,\ell_2,\ldots,\ell_\Delta}\) be the spider graph with vertices \(x_0, x_1^1, x_2^1, \ldots, x_{\ell_1}^1, x_1^2, x_2^2, \ldots, x_{\ell_2}^2, \ldots, x_1^\Delta, x_2^\Delta, \ldots, x_{\ell_\Delta}^\Delta\), and for each \(i=1,2,\ldots,\Delta\), the edges form a path \(x_0x_1^i, x_2^i,\ldots,x_{\ell_i}^i\) between the central vertex \(x_0\) and the leaf \(x_{\ell_i}^i\), which is called the i-th leg of the spider graph.

Although the necessary and sufficient conditions for embedding spider graphs with three legs in \(K_k^*\) were proved [11], we are going to provide a much simplified proof when k is odd, utilizing Theorem 2.3.

Theorem 2.5. Let \(n = \ell_1 + \ell_2 + \ell_3\), and let k be odd. If \(n \geq 7\), then \(S_{\ell_1,\ell_2,\ell_3}\) can be embedded in \(K_k^*\) if and only if \(n \leq {k+1 \choose 2}\).

Proof. If \(k \leq 3\), then \(n \leq {3+1 \choose 2} = 6\), violating the condition that \(n \geq 7\). Hence, it is only meaningful to consider \(k \geq 5\). Furthermore, \(n \geq 7\) implies \(\ell_3 \geq \left\lceil \frac{1}{3} n \right\rceil \geq 3\).

The only if direction is trivial. For the if direction, we consider the following cases.

Case 1: \(\ell_1=1\). Hence, the spider graph \(S_{1,\ell_2,\ell_3}\) can be embedded in the petal graph \(P_{1,3,n-4}\) as follows: the vertices \(x_0\) and \(x_1^1\) of the first leg are both embedded as \(u_0\); the vertices \(x_1^2, x_2^2, \ldots, x_{\ell_2}^2\) of the second leg are embedded as \(u_1^3, u_2^3, \ldots, u_{\ell_2}^3\); and the vertices \(x_1^3, x_2^3, \ldots, x_{\ell_3}^3\) of the third leg are embedded as \(u_1^2, u_2^2, u_0, u_{n-5}^3, u_{n-6}^3, \ldots, u_{\ell_2}^3\). Theorem 2.3 completes the proof.

Case 2: \(\ell_1 \ge 2\). Let (i, j) = (2, 3) if \(\ell_1 + \ell_2 - 1 \le \ell_3\), and let (i, j) = (3, 2) otherwise. The spider graph \(S_{\ell_1,\ell_2,\ell_3}\) can be embedded in the petal graph \(P_{1,c_2,c_3}\), where \(c_i=\ell_1+\ell_2-1\) and \(c_j=\ell_3\), as follows: the vertices \(x_0, x_1^1, x_2^1, \dots, x_{\ell_1}^1\) of the first leg are embedded as \(u_0, u_0, u_1^i, u_2^i, \dots, u_{\ell_1-1}^i\); the vertices \(x_1^2, x_2^2, \dots, x_{\ell_2}^2\) of the second leg are embedded as \(u_{c_{i-1}}^i, u_{c_{i-2}}^i, \dots, u_{\ell_{1}-1}^i\); and the vertices \(x_1^3, x_2^3, \dots, x_{\ell_3}^3\) of the third leg are embedded as \(u_1^j, u_2^j, \dots, u_{c_i-1}^j, u_0\). Again, Theorem 2.3 completes the proof.

The last theorem of this section provides the necessary and sufficient conditions for embedding spider graphs with four legs, the family of graphs that originally drew our interest, in \(K_k^*\) when k is odd.

Theorem 2.6. Let \(n = \ell_1 + \ell_2 + \ell_3 + \ell_4\), and let k be odd. If \(n \geq 7\), then \(S_{\ell_1, \ell_2, \ell_3, \ell_4}\) can be embedded in \(K_k^*\) if and only if

• (a) \(\ell_3 = 1\) and \(n \le \binom{k+1}{2} 1\), or (b) \(\ell_3 \ge 2\) and \(n \le \binom{k+1}{2}\).

Proof. If \(k \leq 3\), then \(n \leq {3+1 \choose 2} = 6\), violating that \(n \geq 7\). Hence, it is only meaningful to consider k > 5.

Assume \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) can be embedded in \(K_k^*\). It is trivial that \(n \leq {k+1 \choose 2}\). If \(n = {k+1 \choose 2}\), then since \(x_{\ell_1}^1, x_{\ell_2}^2, x_{\ell_3}^3\), and \(x_{\ell_4}^4\) are of odd degree in \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) and all vertices in \(K_k^*\) are of even degree, at least two of \(x_{\ell_1}^1\), \(x_{\ell_2}^2\), and \(x_{\ell_3}^3\) must be embedded as the same vertex. If \(\ell_3 = 1\), then this is impossible since there are no double edges in \(K_k^*\), and hence \(n \leq {k+1 \choose 2} - 1\).

For the if direction, due to Proposition 1.2, it suffices to show that \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) can be embedded in \(K_k^*\) if \(n = \binom{k+1}{2} - 1\) when \(\ell_3 = 1\) and \(n = \binom{k+1}{2}\) when \(\ell_3 \ge 2\).

Case 1: \(\ell_3 = 1\). The spider graph \(S_{1,1,1,\ell_4}\) can be embedded in \(K_k^*\) as follows: the vertices \(x_0, x_1^1\), \(x_1^2\), and \(x_1^3\) are embedded as \(v_0\), \(v_0\), \(v_1\), and \(v_2\) respectively; the remaining graph \(K_k^* - v_0 v_0 - v_0 v_1 v_2 v_0\)is an Eulerian graph, so the fourth leg can be embedded as an Eulerian cycle.

Case 2: \(\ell_3 \geq 2\). Let (i,j) = (2,3) if \(\ell_1 + \ell_3 \leq \ell_2 + \ell_4 - 1\), and let (i,j) = (3,2)otherwise. Define \(c_i = \ell_1 + \ell_3\) and \(c_j = \ell_2 + \ell_4 - 1\). Note that \(c_i \geq 1 + 2 = 3\) and \(c_j \ge \max\{n - \ell_1 - \ell_3 - 1, \ell_1 + \ell_3 - 1\} \ge 3\) since \(n \ge 7\). The spider graph \(S_{\ell_1, \ell_2, \ell_3, \ell_4}\) can be embedded in the petal graph \(P_{1,c_2,c_3}\), where \(c_i = \ell_1 + \ell_3\) and \(c_j = \ell_2 + \ell_4 - 1\) as follows: the vertices \(x_0, x_1^1, x_2^1, \dots, x_{\ell_1}^1\) of the first leg are embedded as \(u_0, u_1^i, u_2^i, \dots, u_{\ell_1}^i\); the vertices \(x_1^2, x_2^2, \dots, x_{\ell_2}^2\)of the second leg are embedded as \(u_0, u_1^j, u_2^j, \dots, u_{\ell_2-1}^j\); the vertices \(x_1^3, x_2^3, \dots, x_{\ell_3}^3\) of the third leg are embedded as \(u^i_{c_i-1}, u^i_{c_i-2}, \dots, u^i_{c_i-\ell_3}\); and the vertices \(x^4_1, x^4_2, \dots, x^4_{\ell_4}\) of the fourth leg are embedded as \(u_{c_{i-1}}^{j}, u_{c_{i-2}}^{j}, \dots, u_{c_{i-\ell_{i}}}^{j}\). Theorem 2.3 completes the proof.

3. k is even

In Section 2, we restrict our consideration to k being odd. In this section, except for caterpillar trees, we prove the results parallel to the theorems in the previous section for even k.

To aid our discussions in this section, here are some notations related to an edge decomposition of \(K_k^*\). For each \(j=0,1,2,\ldots,\frac{k-2}{2}\), let \(D_j\) be the subgraph of \(K_k^*\) such that the edge set of \(D_j\) is

\[\{v_pv_q:p\leq q, \text{ either } q-p=j \text{ or } q-p=k-j\}.\]

Note that each \(D_j\) is a regular degree 2 graph and has exactly k edges. Furthermore, let I be the perfect matching subgraph of \(K_k^*\) such that the edge set of I is

\[\left\{ v_i v_{\frac{k}{2}+i} : i = 0, 1, 2, \dots, \frac{k-2}{2} \right\}.\]

Figure 2 illustrates how \(K_6^*\) is decomposed into \(D_0\), \(D_1\), \(D_2\), and I.

Figure 2. \(K_6^*\) contains \(D_0\), \(D_1\), and \(D_2\) as shown below

3.1. Petal graphs

Similar to the case when k is odd, we are going to show that petal graphs \(P_{1,c_2,c_3}\) can be embedded in \(K_k^*\) when k is even as long as some trivial necessary conditions are satisfied.

Theorem 3.1. If k is even, then \(P_{1,c_2,c_3}\) can be embedded in \(K_k^*\) if and only if \(k \ge 6\), \(c_2 \ge 3\), and \(1 + c_2 + c_3 \le \frac{k^2}{2}\).

Proof. For the only if direction, the condition \(c_2 \geq 3\) is trivial. If \(k \leq 4\), then the maximum degree in \(K_k^* - I\) is at most 4, which is less than the maximum degree in \(P_{1,c_2,c_3}\). Hence, we must have \(k \geq 6\). Also, the petal graph \(P_{1,c_2,c_3}\) has only even degrees, so when it is embedded in \(K_k^*\), the image must also have only even degrees. Since all the k vertices in \(K_k^*\) have odd degrees, at least one edge will be missing from each vertex after embedding. In other words, there are at least \(\frac{k}{2}\) edges missing, implying that the number of edges in \(P_{1,c_2,c_3}\) is at most \(\binom{k+1}{2} - \frac{k}{2} = \frac{k^2}{2}\).

For the if direction, let \(n=c_2+c_3\). We are going to show that if \(k \ge 6\), \(c_2 \ge 3\), and \(1+n \le \frac{k^2}{2}\), then \(P_{1,c_2,c_3}\) can be embedded in \(K_k^*-I\). In all of the following cases, we embed the petal \(u_0u_0\) as the loop \(v_0v_0\) in \(K_k^*\).

Without loss of generality, we can assume that \(n > {k \choose 2} - 1\). Otherwise, if \(n \le {k \choose 2} - 1\), we can embed \(P_{1,c_2,c_3}\) in \(K_{k-1}^*\) by Theorem 2.3, which can be further embedded in \(K_k^*\) trivially. Let

\(h=\frac{k^2}{2}-1-n\) be the gap between n and \(\frac{k^2}{2}-1\). Based on our assumption, \(0\leq h\leq \frac{k^2}{2}-1-\binom{k}{2}=\frac{k}{2}-1\).

Case 1: \(3 \le c_2 < k\). Let \(H_0\), \(H_1\), and \(H_2\) be subgraphs of \(K_k^* - I\) such that \(H_0 = \{v_2v_2, v_3v_3, \ldots, v_{h+1}v_{h+1}\}\),

\[H_1 = \begin{cases} v_0 v_1 v_2 v_3 \cdots v_{c_2 - 1} v_0 & \text{if } c_2 \neq \frac{k}{2} + 1; \text{ and} \\ v_0 v_1 v_1 v_2 v_3 \cdots v_{\frac{k}{2} - 1} v_0 & \text{if } c_2 = \frac{k}{2} + 1, \end{cases}\]

and \(H_2=K_k^*-I-v_0v_0-H_0-H_1\). Note that \(H_0\) is well-defined since \(h\leq \frac{k}{2}-1\leq k-2\). With a simple count, we see that \(H_0\) has h edges, \(H_1\) has \(c_2\) edges, and \(H_2\) has \(\binom{k+1}{2}-\frac{k}{2}-1-h-c_2=n-c_2=c_3\) edges. It is clear that all vertices in \(H_1\) and \(H_2\) are of even degree. Furthermore, \(H_2\) is connected since \(H_2\) contains \(D_2\cup\{v_{k-1}v_0\}-\{v_{c_2-1}v_0\}\). Therefore, \(H_1\) and \(H_2\) are both Eulerian, so we can embed the petals \(u_0u_1^2u_2^2\cdots u_{c_2-1}^2u_0\) as \(H_1\) and \(u_0u_1^3u_2^3\cdots u_{c_3-1}^3u_0\) as \(H_2\).

Case 2: \(c_2 \ge k\) and k=6. Note that \(c_2 < \frac{1}{2}(1+n) \le \frac{1}{2} \cdot \frac{k^2}{2} = 9\), i.e., \(c_2=6\), 7, or 8. We can embed the petal \(u_0u_1^2u_2^2\cdots u_{c_2-1}^2u_0\) as \(v_0v_1v_3v_5v_4v_2v_0\) along with \(c_2-6\) additional loops, and embed the petal \(u_0u_1^3u_2^3\cdots u_{c_3-1}^3u_0\) as \(v_0v_5v_1v_2v_3v_4v_0\) along with \(c_3-6\) additional loops. Since \(c_2-6+c_3-6=n-12\le 5\), we can ensure that the two petals are embedded using different loops in \(K_k^*-I-v_0v_0\).

Case 3: \(c_2 \ge k\) and \(k \ge 8\). Let z be the odd integer in \(\{\frac{k-2}{2}, \frac{k-4}{2}\}\). Note that \(\gcd(k, z) = 1\). Since \(k \ge 8\), \(z \ne 1\). In other words, \(D_1\) and \(D_z\) are two distinct Hamiltonian cycles in \(K_k^*\). Let \(c_2'\) and \(c_3'\) be the smallest nonnegative integers such that \(c_2 \equiv c_2' \pmod{k}\) and \(c_3 \equiv c_3' \pmod{k}\).

and \(c_3'\) be the smallest nonnegative integers such that \(c_2 \equiv c_2' \pmod{k}\) and \(c_3 \equiv c_3' \pmod{k}\). Case 3.1: \(c_2' + c_3' < k\). We can embed the petal \(u_0u_1^2u_2^2\cdots u_{c_2-1}^2u_0\) as the subgraph composed of \(D_1\), \(\frac{c_2-c_2'}{k}-1\) elements of \(\{D_2,D_3,\ldots,D_{\frac{k-2}{2}}\}\setminus\{D_z\}\), and \(c_2'\) loops in \(D_0\). Next, we can embed the petal \(u_0u_1^3u_2^3\cdots u_{c_3-1}^3u_0\) as the subgraph composed of \(D_z\), \(\frac{c_3-c_3'}{k}-1\) elements of \(\{D_2,D_3,\ldots,D_{\frac{k-2}{2}}\}\setminus\{D_z\}\), and \(c_3'\) loops in \(D_0\).

Case 3.2: \(c_2' + c_3' \ge k\). Since \(\frac{k^2}{2} - \frac{k}{2} \le n \le \frac{k^2}{2} - 1\) and \(n \equiv c_2' + c_3' \pmod{k}\), we have \(\frac{k}{2} \le c_2' + c_3' - k \le k - 1\), which implies \(\frac{3k}{2} \le c_2' + c_3' \le 2k - 1\). Hence, \(\min\{c_2', c_3'\} \ge \frac{3k}{2} - \max\{c_2', c_3'\} \ge \frac{3k}{2} - (k - 1) > \frac{k}{2}\). Let \(H_1'\) be the subgraph that contains \(c_2' - \frac{k}{2}\) loops in \(D_0\) together with the cycle \(v_0v_2v_4\cdots v_{k-2}v_0\) in \(D_2\), and let \(H_2'\) be the subgraph that contains \(c_3' - \frac{k}{2}\) loops in \(D_0\) together with the cycle \(v_1v_3v_5\cdots v_{k-1}v_1\) in \(D_2\). Let \(H_1\) be the subgraph that contains \(D_1\), \(\frac{c_2-c_2'}{k}-1\) elements of \(\{D_3,\ldots,D_{\frac{k-2}{2}}\}\setminus\{D_z\}\), and \(H_1'\); let \(H_2\) be the subgraph that contains \(D_z\), \(\frac{c_3-c_3'}{k}-1\) elements of \(\{D_3,\ldots,D_{\frac{k-2}{2}}\}\setminus\{D_z\}\), and \(H_2'\). It is easy to see that we can embed the petals \(u_0u_1^2u_2^2\cdots u_{c_2-1}^2u_0\) as \(H_1\) and \(u_0u_1^3u_2^3\cdots u_{c_3-1}^3u_0\) as \(H_2\).

3.2. Cycles with one chord

Unlike the case when k is odd, the obstruction of the triangle in \(C_n^{\{0,2\}}\) when embedded in \(K_k^*\) only occurs when k=4. This is because when k is even, the chord \(w_0w_j\) in \(C_n^{\{0,j\}}\) can be embedded as a diagonal \(v_0v_{\frac{k}{2}}\), instead of as a loop in \(K_k^*\) when k is odd. Hence, with the exception of (k,n,j)=(4,8,2), the trivial necessary conditions are also sufficient for embedding \(C_n^{\{0,j\}}\) in \(K_k^*\).

Theorem 3.2. Let k be even. Then \(C_n^{\{0,j\}}\) can be embedded in \(K_k^*\) if and only if \(k \geq 4\), \(n \leq \frac{k^2}{2}\), and \((k,n,j) \neq (4,8,2)\).

Proof. For the only if direction, if \(k \leq 2\), then \(n \leq \frac{2^2}{2} = 2\), which is impossible according to Definition 3. Hence, \(k \geq 4\). Since the chorded cycle \(C_n^{\{0,j\}}\) has only two vertices with odd degrees, when it is embedded in \(K_k^*\), the image will have at most two vertices with odd degrees. Since all the k vertices in \(K_k^*\) have odd degrees, after embedding, at least one edge will be missing per vertex from at least k-2 vertices. In other words, there are at least \(\frac{k-2}{2}\) edges missing, implying that the number of edges in \(C_n^{\{0,j\}}\) is at most \(\binom{k+1}{2} - \frac{k-2}{2} = \frac{k^2+2}{2}\). Since \(C_n^{\{0,j\}}\) has n+1 edges, we have \(n \leq \frac{k^2}{2}\).

If (k,n,j)=(4,8,2), when \(C_8^{\{0,2\}}\) is embedded in \(K_4^*\), at least one edge that connects two vertices will be missing as discussed. Without loss of generality, let this edge be \(v_1v_3\). Note that the subgraph given by the cycle \(w_0w_1w_2w_0\) in \(C_8^{\{0,2\}}\) must be embedded as a triangle in \(K_4^*-v_1v_3\). Without loss of generality, let \(w_0w_1w_2w_0\) be embedded as \(v_0v_1v_2v_0\). The remaining edges of \(K_4^*\), namely \(K_4^*-v_1v_3-v_0v_1v_2v_0\), form a disconnected graph. As a result, it is impossible to embed the subgraph \(w_2w_3\cdots w_7w_0\) of \(C_8^{\{0,2\}}\). Therefore, if \(C_n^{\{0,j\}}\) can be embedded in \(K_k^*\), then \((k,n,j)\neq (4,8,2)\).

For the if direction, we are going to show that if \(k \geq 4\), \(n \leq \frac{k^2}{2}\), and \((k, n, j) \neq (4, 8, 2)\), then \(C_n^{\{0,j\}}\) can be embedded in \((K_k^* - I) \cup \{v_0 v_{\frac{k}{2}}\}\), which contains \(\frac{k^2}{2} + 1\) edges. In all of the following cases, we embed the chord \(w_0 w_j\) as \(v_0 v_{\frac{k}{2}}\) in \(K_k^*\).

Without loss of generality, we can assume that \(n > {k \choose 2} - 3\). Otherwise, if \(4 \le n \le {k \choose 2} - 3\), we can embed \(C_n^{\{0,j\}}\) in \(K_{k-1}^*\) by Theorem 2.4, which can be further embedded in \(K_k^*\) trivially. Let \(h = \frac{k^2}{2} - n\) be the gap between n and \(\frac{k^2}{2}\). Based on our assumption, \(0 \le h \le \frac{k^2}{2} - {k \choose 2} - 2 = \frac{k}{2} + 2\). Case 1: \(j \le \frac{k}{2}\). Let \(H_0\), \(H_1\), and \(H_2\) be subgraphs of \(K_k^* - I\) such that \(H_0 = \{v_1v_1, v_2v_2, \ldots, v_hv_h\}\), \(H_1 = v_0v_1v_2 \cdots v_{j-1}v_{\frac{k}{2}}\), and \(H_2 = K_k^* - I - H_0 - H_1\). Note that \(H_0\) is well-defined since \(h \le \frac{k}{2} + 2 \le \frac{k}{2} + \frac{k}{2} = k\), and \(v_kv_k\) represents the loop \(v_0v_0\). With a simple count, we see that \(H_0\) has h edges, \(H_1\) has h edges, and h has h as h and h as h and h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h are h and h

Case 2: \(j > \frac{k}{2}\). Let j' and j'' be the smallest positive integers such that \(j - \frac{k}{2} \equiv j' \pmod{k}\) and \(j' \equiv j'' \pmod{\frac{k}{2}}\). Let

\[H_0 = \begin{cases} \{v_{j''+1}v_{j''+1}, v_{j''+2}v_{j''+2}, \dots, v_{j''+h}v_{j''+h}\} & \text{if } h \leq \frac{k}{2}; \\ \{v_{j''+1}v_{j''+1}, v_{j''+2}v_{j''+2}, \dots, v_{j''+h-\frac{k}{2}}v_{j''+h-\frac{k}{2}}\} \\ \cup \{v_0v_2v_4 \cdots v_{k-2}v_0\} & \text{if } h > \frac{k}{2}, \end{cases}\]

\(H_1\) contain the path \(v_0v_1v_2\cdots v_{\frac{k}{2}}\) along with \(\frac{j-\frac{k}{2}-j'}{k}\) elements of \(\{D_3,D_4,\ldots,D_{\frac{k-2}{2}}\}\) and the edges

\[\begin{cases} \{v_1v_1, v_2v_2, \dots, v_{j'}v_{j'}\} & \text{if } j' \leq \frac{k}{2}; \text{ and} \\ \{v_1v_1, v_2v_2, \dots, v_{j''}v_{j''}\} \cup \{v_1v_3v_5 \cdots v_{k-1}v_1\} & \text{if } j' > \frac{k}{2}, \end{cases}\]

and \(H_2=K_k^*-I-H_0-H_1\). Note that \(v_kv_k\) represents the loop \(v_0v_0\). With a simple count, we see that \(H_0\) has h edges, \(H_1\) has j edges, and \(H_2\) has \(\binom{k+1}{2}-\frac{k}{2}-h-j=\frac{k^2}{2}-h-j=n-j\) edges. It is clear that the only two odd degree vertices in \(H_1\) and \(H_2\) are \(v_0\) and \(v_{\frac{k}{2}}\). It is also clear that \(H_1\) is connected. We will now show that \(H_2\) is connected.

• If k = 4, then \(H_2\) is connected since it contains the path \(v_0v_3v_2\) and does not contain the loop \(v_1v_1\).
• If k=6, then \(H_2\) contains the path \(v_0v_5v_4v_3\). Hence, the only possible disconnected edges in \(H_2\) are \(v_1v_1\), \(v_2v_2\), and \(v_1v_2\). However, \(v_1v_1\) and \(v_1v_2\) are always contained in \(H_1\). Moreover, \(H_2\) contains \(v_2v_2\) if and only if \((j',h) \in \{(1,0),(4,0)\}\), and in both cases, \(H_2\) also contains the cycle \(v_0v_2v_4v_0\), so \(H_2\) is connected.
• If k=8, then \(H_2\) contains the path \(v_0v_7v_6v_5v_4\). Hence, the only possible disconnected edges in \(H_2\) are \(v_1v_1, v_2v_2, v_3v_3, v_1v_2, v_2v_3\), and \(v_1v_3\). However, \(v_1v_1, v_1v_2\), and \(v_2v_3\) are always contained in \(H_1\). The loop \(v_2v_2\) is contained in \(H_2\) if and only if \((j',h) \in \{(1,0),(5,0)\}\), and in both cases, \(H_2\) also contains the cycle \(v_0v_2v_4v_6v_0\). Finally, note that if \(j' \leq \frac{k}{2}\), then \(H_2\) contains the cycle \(v_1v_3v_5v_7v_1\); if \(j' > \frac{k}{2} = 4\), then \(\frac{j-\frac{k}{2}-j'}{k} < \frac{16-4-4}{8} \leq 1\), so \(H_2\) contains \(D_3\). Hence, vertex \(v_3\) is always connected to \(v_0\) in \(H_2\), thus the edges \(v_1v_3\) and \(v_3v_3\) will never be isolated edges in \(H_2\). Therefore, \(H_2\) is always connected.
• If \(k \geq 10\), then \(H_2\) contains \(\{v_0v_{k-1}v_{k-2}\cdots v_{\frac{k}{2}}\}\cup D_i\) for some \(i\in\{3,4,\ldots,\frac{k-2}{2}\}\). To demonstrate this, let us first assume the contrary, i.e., every \(D_i\), \(i\in\{3,4,\ldots,\frac{k-2}{2}\}\), is in \(H_1\). Hence, \(\frac{j-\frac{k}{2}-j'}{k}=\frac{k-2}{2}-2\), which implies \(j-j'=\frac{k^2-5k}{2}\). Since \(j\leq\frac{n}{2}\leq\frac{1}{2}\cdot\frac{k^2}{2}=\frac{k^2}{4}\) and j'>0, we have \(\frac{k^2-5k}{2}<\frac{k^2}{4}\), which occurs if and only if 0< k<10, contradicting that \(k\geq 10\). Therefore, \(H_2\) is connected.

Therefore, \(H_1\) and \(H_2\) both contain an Eulerian trail, and we can embed the paths \(w_0w_1w_2\cdots w_j\) and \(w_0w_{n-1}w_{n-2}\cdots w_j\) as \(H_1\) and \(H_2\) respectively.

3.3. Spider graphs with four legs

Theorem 3.3. Let k be even, and let \(n = \ell_1 + \ell_2 + \ell_3 + \ell_4\). Then \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) can be embedded in \(K_k^*\) if and only if \(k \geq 4\), \(n \leq \frac{k^2+4}{2}\), and \((k,\ell_1) \neq (4,2)\).

Proof. For the only if direction, if \(k \leq 2\), then the number of edges in \(K_k^*\) is at most \(\binom{2+1}{2} = 3\), which is less than the number of edges in \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\), so \(k \geq 4\) is a necessary condition.

Since the spider graph \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) has only four vertices with odd degrees, when it is embedded in \(K_k^*\), the image will have at most four vertices with odd degrees. Since all the k vertices in \(K_k^*\)

have odd degrees, after embedding, at least one edge will be missing per vertex from at least k-4vertices. In other words, there are at least \(\frac{k-4}{2}\) edges missing, implying that the number of edges in \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) is at most \(\binom{k+1}{2} - \frac{k-4}{2} = \frac{k^2+4}{2}\), i.e., \(n \leq \frac{k^2+4}{2}\). Finally, embedding \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) in \(K_k^*\) when \((k,\ell_1) = (4,2)\) is impossible due to Proposition 1.1,

since \(\Delta(S_{\ell_1,\ell_2,\ell_3,\ell_4}) = 4\). Therefore, \((k,\ell_1) \neq (4,2)\).

For the if direction, by Proposition 1.2, we only need to consider \(n = \frac{k^2+4}{2}\). We are going to define the embedding \(\phi:V(S_{\ell_1,\ell_2,\ell_3,\ell_4})\to V(K_4^*)\) explicitly.

When k = 4, since n = 10 and \(\ell_1 \neq 2\).

\[(\ell_1, \ell_2, \ell_3, \ell_4) \in \{(1, 1, 1, 7), (1, 1, 2, 6), (1, 1, 3, 5), (1, 1, 4, 4), (1, 2, 2, 5), (1, 2, 3, 4), (1, 3, 3, 3)\}.\]

For all these instances, we embed the first leg \(x_0x_1^1\) of \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) in \(K_4^*\) as the loop \(v_0v_0\), i.e., \(\phi(x_0) = v_0\) and \(\phi(x_1^1) = v_0\). The embedding of other legs are given by the following table.

When \(k \geq 6\), we proceed by considering the following cases.

Case 1: \(\ell_2 + \ell_3 \ge 4\). Let (i, j) = (2, 3) if \(\ell_2 + \ell_3 - 1 \le \ell_1 + \ell_4 - 2\), and let (i, j) = (3, 2)otherwise. Furthermore, let \(c_i = \ell_2 + \ell_3 - 1\) and \(c_j = \ell_1 + \ell_4 - 2\). We claim that the petal graph \(P_{1,c_2,c_3}\) can be embedded in \(K_k^* - I\). Since \(\ell_2 + \ell_3 \ge 4\), we have \(\ell_2 + \ell_3 - 1 \ge 3\). Also, since \(\ell_4 \ge \frac{k^2+4}{8}\) and \(k \ge 6\), we have \(\ell_4 \ge 5\), so \(\ell_1 + \ell_4 - 2 \ge 4 > 3\). Finally, \(\ell_1 + \ell_2 + \ell_3 + \ell_4 = \frac{k^2+4}{2}\), which implies \(1 + c_2 + c_3 = 1 + (\ell_2 + \ell_3 - 1) + (\ell_3 + \ell_4 - 2) = \frac{k^2}{2}\). Therefore, there exists an embedding \(\psi: V(P_{1,c_2,c_3}) \to V(K_k^* - I)\) by the argument provided in the proof of Theorem 3.1.

Now, we start embedding \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) in \(K_4^*\) as follows. We embed the second leg \(x_0 x_1^2 x_2^2 \cdots x_{\ell_2}^2\) of \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) as the path \(\psi(u_0) \psi(u_1^i) \psi(u_2^i) \cdots \psi(u_{\ell_2}^i)\) in \(K_k^*\). Let \(v_a = \psi(u_{\ell_2}^i)\) be a vertex in \(K_k^*\). Then we embed the third leg \(x_0x_1^3x_2^3\cdots x_{\ell_3}^3\) as the path \(\psi(u_0)\psi(u_{c_i-1}^i)\psi(u_{c_i-2}^i)\cdots\)\(\psi(u_{\ell_2}^i)v_{\frac{k}{2}+a}\), where \(\frac{k}{2}+a\) is performed under modulo k. Note that the edge \(\psi(u_{\ell_2}^i)v_{\frac{k}{2}+a}\) is in the perfect matching I.

Let \(v_{b_2} = \psi(u^j_{\ell_4-2})\) and \(v_{b_1} = \psi(u^j_{\ell_4-1})\) be vertices in \(K_k^*\). Here, if \(\ell_4 - 1 = c_j\), then \(u^j_{\ell_4-1} = u_0\). Case 1.1: \(v_{b_2} \notin \{v_a, v_{\frac{k}{2}+a}\}\). In this case, we embed the fourth leg \(x_0 x_1^4 x_2^4 \cdots x_{\ell_4}^4\) as the path \(\psi(u_0)\psi(u_0)\psi(u_1^j)\psi(u_2^j)\cdots\psi(u_{\ell_4-2}^j)v_{\frac{k}{2}+b_2}\), where \(\frac{k}{2}+b_2\) is performed under modulo k. Note that the edge \(\psi(u^j_{\ell_4-2})v_{\frac{k}{2}+b_2}\) is in the perfect matching I and is distinct from the edge \(\psi(u^i_{\ell_2})v_{\frac{k}{2}+a}\). Finally, we embed the first leg \(x_0x_1^1x_2^1\cdots x_{\ell_1}^1\) as the path \(\psi(u_0)\psi(u_{c_j-1}^j)\psi(u_{c_j-2}^j)\cdots\)

Case 1.2: \(v_{b_2} \in \{v_a, v_{\frac{k}{2}+a}\}\) and \(v_{b_1} \notin \{v_a, v_{\frac{k}{2}+a}\}\). In this case, we embed the fourth leg \(x_0x_1^4x_2^4\cdots x_{\ell_4}^4\) as the path \(\psi(u_0)\psi(u_0)\psi(u_1^j)\psi(u_2^j)\cdots \psi(u_{\ell_4-1}^j)\), and we embed the first leg

\(x_0x_1^1x_2^1\cdots x_{\ell_1}^1\) as the path \(\psi(u_0)\psi(u_{c_j-1}^j)\psi(u_{c_j-2}^j)\cdots \psi(u_{\ell_4-1}^j)v_{\frac{k}{2}+b_1}\), where \(\frac{k}{2}+b_1\) is performed under modulo k. Note that the edge \(\psi(u_{\ell_4-1}^j)v_{\frac{k}{2}+b_1}\) is in the perfect matching I and is distinct from the edge \(\psi(u_{\ell_2}^i)v_{\frac{k}{2}+a}\).

Case 1.3: \(v_{b_2}, v_{b_1} \in \{v_a, v_{\frac{k}{2}+a}\}\). In this case, we claim that \(\ell_1 > 1\). To demonstrate this, let us first assume the contrary, i.e., \(\ell_1 = 1\). As a result, \(c_j = \ell_4 - 1\) and \(v_{b_1} = \psi(u_j^j) = \psi(u_0)\), which is the vertex \(v_0\) due to the proof of Theorem 3.1. Therefore, we have \(v_{b_2}, v_{b_1} \in \{v_0, v_{\frac{k}{2}}\}\). However, \(v_{b_2} = \psi(u_j^j)\) cannot be the vertex \(v_0\), or else \(\psi(u_0)\psi(u_{c_j-1}^j) = v_0v_0 = \psi(u_0)\psi(u_0)\), contradicting that \(\psi\) is an embedding. The vertex \(v_{b_2}\) cannot be the vertex \(v_{\frac{k}{2}}\) either, or else \(\psi(u_0)\psi(u_{c_j-1}^j) = v_0v_{\frac{k}{2}}\) is an edge in the perfect matching I, contradicting that \(\psi\) is an embedding of \(P_{1,c_2,c_3}\) in \(K_k^* - I\). Hence, \(\ell_1 > 1\).

Note that \(v_{b_2}=v_{b_1}\), or else \(\psi(u^j_{\ell_4-2})\psi(u^j_{\ell_4-1})=v_{b_2}v_{b_1}\) is an edge in the perfect matching I. Let \(v_{b_0}=\psi(u^j_{\ell_4})\). Here, if \(\ell_4=c_j\), then \(u^j_{\ell_4}=u_0\). Since \(v_{b_1}v_{b_0}=\psi(u^j_{\ell_4-1})\psi(u^j_{\ell_4})\neq \psi(u^j_{\ell_4-2})\psi(u^j_{\ell_4-1})=v_{b_2}v_{b_1}\) and \(v_{b_1}v_{b_0}=\psi(u^j_{\ell_4-1})\psi(u^j_{\ell_4})\) is not in I, we conclude that \(v_{b_0}\notin \{v_a,v_{\frac{k}{2}+a}\}\). As a result, we can embed the fourth leg \(x_0x_1^4x_2^4\cdots x_{\ell_4}^4\) as the path \(\psi(u_0)\psi(u^j_1)\psi(u^j_2)\cdots\psi(u^j_{\ell_4})\), and we embed the first leg \(x_0x_1^1x_2^1\cdots x_{\ell_1}^1\) as the path \(\psi(u_0)\psi(u_0)\psi(u^j_{c_j-1})\psi(u^j_{c_j-2})\cdots\psi(u^j_{\ell_4})v_{\frac{k}{2}+b_0}\), where \(\frac{k}{2}+b_0\) is performed under modulo k. Note that the edge \(\psi(u^j_{\ell_4})v_{\frac{k}{2}+b_0}\) is in the perfect matching I and is distinct from the edge \(\psi(u^i_{\ell_2})v_{\frac{k}{2}+a}\).

Case 2: \(\ell_2+\ell_3<4\). This means that \((\ell_2,\ell_3)\in\{(1,1),(1,2)\}\), and consequently \((\ell_1,\ell_2,\ell_3,\ell_4)\in\{(1,1,1,n-3),(1,1,2,n-4)\}\). In both cases, we are going to embed \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) in \(K_k^*\) such that the image of the embedding is \((K_k^*-I)\cup\{v_0v_{\frac{k}{2}},v_1v_{\frac{k}{2}+1}\}\): the first leg \(x_0x_1^1\) is embedded as the loop \(v_0v_0\), and the second leg \(x_0x_1^2\) is embedded as the diagonal \(v_0v_{\frac{k}{2}}\). If \(\ell_3=1\), then the third leg \(x_0x_1^3\) is embedded as the edge \(v_0v_1\); if \(\ell_3=2\), then the third leg \(x_0x_1^3x_2^3\) is embedded as the path \(v_0v_1v_1\). Note that \(v_0,v_1,v_{\frac{k}{2}}\), and \(v_{\frac{k}{2}+1}\) are all the odd degree vertices in \((K_k^*-I)\cup\{v_0v_{\frac{k}{2}},v_1v_{\frac{k}{2}+1}\}\), while \(v_1\) and \(v_{\frac{k}{2}}\) are all the odd degree vertices in the image graph of the first three legs. Hence, if we remove the image graph of the first three legs from \((K_k^*-I)\cup\{v_0v_{\frac{k}{2}},v_1v_{\frac{k}{2}+1}\}\), we have an Eulerian graph with \(\ell_4\) edges and exactly two odd degree vertices, namely \(v_0\) and \(v_{\frac{k}{2}+1}\). Therefore, we can embed the fourth leg \(x_0x_1^4x_2^4\cdots x_{\ell_4}^4\) as the remaining graph of \((K_k^*-I)\cup\{v_0v_{\frac{k}{2}},v_1v_{\frac{k}{2}+1}\}\). \(\square\)

4. Edge-distinguishing chromatic numbers

4.1. Petal graphs

Theorem 4.1. Let \(c_2, c_3 \in \mathbb{N}\) such that \(3 \le c_2 \le c_3\). Let \(e = 1 + c_2 + c_3\) be the number of edges of \(P_{1,c_2,c_3}\). The edge-distinguishing chromatic number of \(P_{1,c_2,c_3}\) is given by

\[\lambda(P_{1,c_2,c_3}) = \begin{cases} 5 & \text{if } e \leq 10; \\ \left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil & \text{if } e \geq 11 \text{ and } \left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil \text{ is odd; and } \\ \left\lceil \sqrt{2e} \right\rceil & \text{otherwise.} \end{cases}\]

Proof. Since the maximum degree of \(P_{1,c_2,c_3}\) is 6, we must have \(k \geq 5\) in order to embed \(P_{1,c_2,c_3}\) in \(K_k^*\). On the other hand, by Theorem 2.3, \(P_{1,c_2,c_3}\) can be embedded in \(K_5^*\) if \(e \leq 10\). Hence, \(\lambda(P_{1,c_2,c_3}) = 5\) if \(e \leq 10\).

If e > 11, note that

\[5 \leq \left\lceil \frac{-1 + \sqrt{8e + 1}}{2} \right\rceil \leq \left\lceil \sqrt{2e} \right\rceil \leq \left\lceil \frac{-1 + \sqrt{8e + 1}}{2} \right\rceil + 1.\]

Also note that the minimum positive integer k that satisfies \(\binom{k+1}{2} \geq e\) is \(\left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil\), and the minimum positive integer k that satisfies \(\frac{k^2}{2} \geq e\) is \(\left\lceil \sqrt{2e} \right\rceil\).

If \(\left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil\) is odd, then \(\left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil -1\) is even but strictly less than \(\left\lceil \sqrt{2e} \right\rceil\), so \(\left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil -1\) does not satisfy \(\frac{k^2}{2} \geq e\). Hence, by Theorems 2.3 and 3.1, \(k = \left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil\) is the minimum positive integer such that \(P_{1,c_2,c_3}\) can be embedded in \(K_k^*\).

If \(\left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil\) and \(\left\lceil \sqrt{2e} \right\rceil\) are both even, then \(\left\lceil \sqrt{2e} \right\rceil = \left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil\), so \(\left\lceil \sqrt{2e} \right\rceil - 1\) does not satisfy \(\binom{k+1}{2} \geq e\). Hence, by Theorems 2.3 and 3.1, \(k = \left\lceil \sqrt{2e} \right\rceil\) is the minimum positive integer such that \(P_{1,c_2,c_3}\) can be embedded in \(K_k^*\).

If \(\left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil\) is even but \(\left\lceil \sqrt{2e} \right\rceil\) is odd, then \(\left\lceil \sqrt{2e} \right\rceil = \left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil + 1\) is odd and satisfies \(\binom{k+1}{2} \geq e\), but \(\left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil\) does not satisfy \(\frac{k^2}{2} \geq e\). Hence, by Theorems 2.3 and 3.1, \(k = \left\lceil \sqrt{2e} \right\rceil\) is the minimum positive integer such that \(P_{1,c_2,c_3}\) can be embedded in \(K_k^*\).

Finally, we finish by applying Theorem 1.5.

4.2. Cycles with one chord

Theorem 4.2. Let \(j, n \in \mathbb{N}\) such that \(2 \le j \le \frac{n}{2}\). Let e = n + 1 be the number of edges of \(C_n^{\{0,j\}}\). The edge-distinguishing chromatic number of \(C_n^{\{0,j\}}\) is given by

\[\lambda(C_n^{\{0,2\}}) = \begin{cases} 4 & \text{if } e \leq 8; \\ 5 & \text{if } e = 9; \\ \left\lceil \frac{-1 + \sqrt{8e + 17}}{2} \right\rceil & \text{if } e \geq 10 \text{ and } \left\lceil \frac{-1 + \sqrt{8e + 17}}{2} \right\rceil \text{ is odd; and } \\ \left\lceil \sqrt{2e - 2} \right\rceil & \text{otherwise,} \end{cases}\]

and if \(j \geq 3\), then

\[\lambda(C_n^{\{0,j\}}) = \begin{cases} 4 & \text{if } e \leq 6; \\ \left\lceil \frac{-1 + \sqrt{8e+1}}{2} \right\rceil & \text{if } e \geq 7 \text{ and } \left\lceil \frac{-1 + \sqrt{8e+1}}{2} \right\rceil \text{ is odd; and } \\ \left\lceil \sqrt{2e-2} \right\rceil & \text{otherwise.} \end{cases}\]

Proof. It is obvious that no chorded cycle can be embedded in \(K_3^*\), so \(\lambda(C_n^{\{0,j\}}) \ge 4\) for all \(j, n \in \mathbb{N}\) such that \(2 \le j \le \frac{n}{2}\).

When j=2, by Theorem 3.2, \(C_n^{\{0,2\}}\) can be embedded in \(K_4^*\) if and only if \(e\leq 8\). Hence, \(\lambda(C_n^{\{0,2\}})=4\) if \(e\leq 8\). Also, by Theorem 2.4, \(C_n^{\{0,2\}}\) can be embedded in \(K_5^*\) when e=9. Hence, \(\lambda(C_n^{\{0,2\}})=5\) if e=9.

If e > 10, note that

\[5 \leq \left\lceil \frac{-1 + \sqrt{8e + 17}}{2} \right\rceil \leq \left\lceil \sqrt{2e - 2} \right\rceil \leq \left\lceil \frac{-1 + \sqrt{8e + 17}}{2} \right\rceil + 1.\]

Also note that the minimum positive integer k that satisfies \(\binom{k+1}{2} - 2 \ge e\) is \(\left\lceil \frac{-1 + \sqrt{8e + 17}}{2} \right\rceil\), and the minimum positive integer k that satisfies \(\frac{k^2}{2} + 1 \ge e\) is \(\left\lceil \sqrt{2e - 2} \right\rceil\).

If \(\left\lceil \frac{-1+\sqrt{8e+17}}{2} \right\rceil\) is odd, then \(\left\lceil \frac{-1+\sqrt{8e+17}}{2} \right\rceil - 1\) is even but strictly less than \(\left\lceil \sqrt{2e-2} \right\rceil\), so \(\left\lceil \frac{-1+\sqrt{8e+17}}{2} \right\rceil - 1\) does not satisfy \(\frac{k^2}{2} + 1 \ge e\). Hence, by Theorems 2.4 and 3.2, \(k = \left\lceil \frac{-1+\sqrt{8e+17}}{2} \right\rceil\) is the minimum positive integer such that \(C_n^{\{0,2\}}\) can be embedded in \(K_k^*\).

If \(\left\lceil \frac{-1+\sqrt{8e+17}}{2} \right\rceil\) and \(\left\lceil \sqrt{2e-2} \right\rceil\) are both even, then \(\left\lceil \sqrt{2e-2} \right\rceil = \left\lceil \frac{-1+\sqrt{8e+17}}{2} \right\rceil\), so \(\left\lceil \sqrt{2e-2} \right\rceil - 1\) does not satisfy \(\binom{k+1}{2} - 2 \ge e\). Hence, by Theorems 2.4 and 3.2, \(k = \left\lceil \sqrt{2e-2} \right\rceil\) is the minimum positive integer such that \(C_n^{\{0,2\}}\) can be embedded in \(K_k^*\).

is the minimum positive integer such that \(C_n^{\{0,2\}}\) can be embedded in \(K_k^*\). If \(\left\lceil \frac{-1+\sqrt{8e+17}}{2} \right\rceil\) is even but \(\left\lceil \sqrt{2e-2} \right\rceil\) is odd, then \(\left\lceil \sqrt{2e-2} \right\rceil = \left\lceil \frac{-1+\sqrt{8e+17}}{2} \right\rceil + 1\) is odd and satisfies \(\binom{k+1}{2} - 2 \ge e\), but \(\left\lceil \frac{-1+\sqrt{8e+17}}{2} \right\rceil\) does not satisfy \(\frac{k^2}{2} + 1 \ge e\). Hence, by Theorems 2.4 and 3.2, \(k = \left\lceil \sqrt{2e-2} \right\rceil\) is the minimum positive integer such that \(C_n^{\{0,2\}}\) can be embedded in \(K_k^*\).

Our proof of the formula for \(\lambda(C_n^{\{0,2\}})\) is finished by applying Theorem 1.5.

When \(j \geq 3\), by Theorem 3.2, \(C_n^{\{0,j\}}\) can be embedded in \(K_4^*\) if \(e \leq 6\). Hence, \(\lambda(C_n^{\{0,j\}}) = 4\) if \(e \leq 6\), note that

\[4 \le \left\lceil \frac{-1 + \sqrt{8e + 1}}{2} \right\rceil \le \left\lceil \sqrt{2e - 2} \right\rceil \le \left\lceil \frac{-1 + \sqrt{8e + 1}}{2} \right\rceil + 1.\]

Also note that the minimum positive integer k that satisfies \(\binom{k+1}{2} \geq e\) is \(\left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil\), and the minimum positive integer k that satisfies \(\frac{k^2}{2}+1 \geq e\) is \(\left\lceil \sqrt{2e-2} \right\rceil\). The rest of the proof is analogous to the case when j=2.

4.3. Spider graphs with four legs

Theorem 4.3. Let \(\ell_1, \ell_2, \ell_3, \ell_4 \in \mathbb{N}\) such that \(\ell_1 \leq \ell_2 \leq \ell_3 \leq \ell_4\). Let \(e = \ell_1 + \ell_2 + \ell_3 + \ell_4\) be the number of edges of \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\). The edge-distinguishing chromatic number of \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) is given by

\[\lambda(S_{1,1,1,\ell_4}) = \begin{cases} 4 & \text{if } e \leq 10; \\ \left\lceil \frac{-1 + \sqrt{8e + 9}}{2} \right\rceil & \text{if } e \geq 11 \text{ and } \left\lceil \frac{-1 + \sqrt{8e + 9}}{2} \right\rceil \text{ is odd; and } \\ \left\lceil \sqrt{2e - 4} \right\rceil & \text{otherwise,} \end{cases}\]

and if \(\ell_3 \geq 2\), then

\[\lambda(S_{\ell_1,\ell_2,\ell_3,\ell_4}) = \begin{cases} 4 & \text{if } e \leq 10 \text{ and } \ell_1 = 1; \\ 5 & \text{if } e \leq 10 \text{ and } \ell_1 = 2; \\ \left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil & \text{if } e \geq 11 \text{ and } \left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil \text{ is odd; and } \\ \left\lceil \sqrt{2e-4} \right\rceil & \text{otherwise.} \end{cases}\]

Proof. Since the maximum degree of \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) is 4, we must have \(\lambda(S_{\ell_1,\ell_2,\ell_3,\ell_4}) \geq 4\) by Proposition 1.1. In other words, \(k \geq 4\) is necessary to embed \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) in \(K_k^*\).

When \(\ell_3=1\), by Theorem 3.3, \(S_{1,1,1,\ell_4}\) can be embedded in \(K_4^*\) if and only if \(e\leq 10\). Hence, \(\lambda(S_{1,1,1,\ell_4})=4\) if \(e\leq 10\).

If \(e \ge 11\), note that

\[5 \le \left\lceil \frac{-1 + \sqrt{8e + 9}}{2} \right\rceil \le \left\lceil \sqrt{2e - 4} \right\rceil \le \left\lceil \frac{-1 + \sqrt{8e + 9}}{2} \right\rceil + 1.\]

Also note that the minimum positive integer k that satisfies \(\binom{k+1}{2} - 1 \ge e\) is \(\left\lceil \frac{-1 + \sqrt{8e+9}}{2} \right\rceil\), and the minimum positive integer k that satisfies \(\frac{k^2}{2} + 2 \ge e\) is \(\left\lceil \sqrt{2e-4} \right\rceil\).

If \(\left\lceil \frac{-1+\sqrt{8e+9}}{2} \right\rceil\) is odd, then \(\left\lceil \frac{-1+\sqrt{8e+9}}{2} \right\rceil - 1\) is even but strictly less than \(\left\lceil \sqrt{2e-4} \right\rceil\), so \(\left\lceil \frac{-1+\sqrt{8e+9}}{2} \right\rceil - 1\) does not satisfy \(\frac{k^2}{2} + 2 \ge e\). Hence, by Theorems 2.6 and 3.3, \(k = \left\lceil \frac{-1+\sqrt{8e+9}}{2} \right\rceil\) is the minimum positive integer such that \(S_{1,1,1,\ell_4}\) can be embedded in \(K_k^*\).

If \(\left\lceil \frac{-1+\sqrt{8e+9}}{2} \right\rceil\) and \(\left\lceil \sqrt{2e-4} \right\rceil\) are both even, then \(\left\lceil \sqrt{2e-4} \right\rceil = \left\lceil \frac{-1+\sqrt{8e+9}}{2} \right\rceil\), so \(\left\lceil \sqrt{2e-4} \right\rceil - 1\) does not satisfy \(\binom{k+1}{2} - 1 \ge e\). Hence, by Theorems 2.6 and 3.3, \(k = \left\lceil \sqrt{2e-4} \right\rceil\) is the minimum positive integer such that \(S_{1,1,1,\ell_4}\) can be embedded in \(K_k^*\).

If \(\left\lceil \frac{-1+\sqrt{8e+9}}{2} \right\rceil\) is even but \(\left\lceil \sqrt{2e-4} \right\rceil\) is odd, then \(\left\lceil \sqrt{2e-4} \right\rceil = \left\lceil \frac{-1+\sqrt{8e+9}}{2} \right\rceil + 1\) is odd and satisfies \(\binom{k+1}{2} - 1 \ge e\), but \(\left\lceil \frac{-1+\sqrt{8e+9}}{2} \right\rceil\) does not satisfy \(\frac{k^2}{2} + 2 \ge e\). Hence, by Theorems 2.6 and 3.3, \(k = \left\lceil \sqrt{2e-4} \right\rceil\) is the minimum positive integer such that \(S_{1,1,1,\ell_4}\) can be embedded in \(K_k^*\).

Our proof of the formula for \(\lambda(S_{1,1,1,\ell_4})\) is finished by applying Theorem 1.5.

When \(\ell_3 \geq 2\), by Theorem 3.3, \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) can be embedded in \(K_4^*\) if and if \(e \leq 10\) and \(\ell_1 = 1\). Hence, \(\lambda(S_{\ell_1,\ell_2,\ell_3,\ell_4}) = 4\) if \(e \leq 10\) and \(\ell_1 = 1\). If \(\ell_1 = 2\), then \(e \geq 8 \geq 7\), and by Theorem 2.6, \(S_{\ell_1,\ell_2,\ell_3,\ell_4}\) can be embedded in \(K_5^*\) if \(e \leq 10\). Hence, \(\lambda(S_{\ell_1,\ell_2,\ell_3,\ell_4}) = 5\) if \(e \leq 10\) and \(\ell_1 = 2\).

If \(e \ge 11\), note that

\[5 \le \left\lceil \frac{-1 + \sqrt{8e + 1}}{2} \right\rceil \le \left\lceil \sqrt{2e - 4} \right\rceil \le \left\lceil \frac{-1 + \sqrt{8e + 1}}{2} \right\rceil + 1.\]

Also note that the minimum positive integer k that satisfies \(\binom{k+1}{2} \ge e\) is \(\left\lceil \frac{-1+\sqrt{8e+1}}{2} \right\rceil\), and the minimum positive integer k that satisfies \(\frac{k^2}{2} + 2 \ge e\) is \(\left\lceil \sqrt{2e-4} \right\rceil\). The rest of the proof is analogous to the case when \(\ell_3 = 1\).

5. Concluding remarks and future work

When the authors determined the EDCN of spider graphs with three legs [11], the focus was only on one graph, making the approach restrictive. In this paper, we consider a variety of graphs; in particular, petal graphs serve as an intermediate step when chorded cycles and spider graphs are embedded in \(K_k^*\), which makes the proof easier to navigate. Moreover, this new approach allows us to solve all suggested problems listed in the aforementioned paper except the conjecture concerning caterpillar trees.

Although the embedding of caterpillar trees in \(K_k^*\) still eludes us when k is even, we are able to show that the trivial necessary conditions for embedding certain caterpillar trees in \(K_k^*\) are also sufficient when k is odd. Hence, one major future work direction is to continue our study of caterpillar trees.

Here is a list of other potential future projects on EDCN.

• 1. General petal graphs with three or four petals;
• 2. Spider graphs with more than 4 legs;
• 3. Ladder graphs.

References

• [1] A. Aflaki, S. Akbari, K. J. Edwards, D. S. Eskandani, M. Jamaali, and H. Ravanbod, On harmonious colouring of trees, Electron. J. Combin. 19.1 (2012), #P3.
• [2] M. Aigner, E. Triesch, and Z. Tuza, Irregular assignments and vertex-distinguishing edge-colorings of graphs, Ann. Disc. Math. 52 (1992), 1–9.
• [3] K. Al-Wahabi, R. Bari, F. Harary, and D. Ullman, The edge-distinguishing chromatic number of paths and cycles, Ann. Disc. Math. 41 (1989), 17–22.
• [4] P. Balister, B. Bollobás, and R. Schelp, Vertex distinguishing colorings of graphs with \(\Delta(G)=2\), Disc. Math. 252 (2002), 17–29.
• [5] C. Bazgan, A. Harkat-Benhamdine, H. Li, and M. Woźniak, On the vertex-distinguishing proper edge-colorings of graphs, J. Combin. Theory Ser. B 75 (1999), 288–301.
• [6] D. Beane, N. Biggs, and B. Wilson, The growth rate of the harmonious chromatic number, J. Graph Theory 13 (1989), 291–299.
• [7] B. Brunton, B. Wilson, and T. Griggs, Graphs which have n/2-minimal line-distinguishing colourings, Disc. Math. 155 (1996), 19–26.
• [8] K. Collins and A. Trenk, The distinguishing chromatic number, Electron. J. Combin. 13 (2006), #R16.
• [9] T. Dvořák, I. Havel, and P. Liebl, Euler cycles in the complete graph \(K_{2m+1}\), Disc. Math. 171 (1997), 89–102.

• [10] K. Edwards, The harmonious chromatic number of complete r-ary trees, Disc. Math. 203 (1999), 83–99.
• [11] G. Fickes and T. W. H. Wong, The edge-distinguishing chromatic number of spider graphs with three legs or bounded leg lengths, J. Combin. Math. Combin. Comput. 113 (2020), 165– 181.
• [12] O. Frank, F. Harary, and M. Plantholt, The line-distinguishing chromatic number of a graph, Ars Combin. 14 (1982), 241–252.
• [13] J. Hopcroft and M. Krishnamoorthy, On the harmonious coloring of graphs, SIAM J. Algebr. Disc. Methods 4 (1983), 306–311.
• [14] J. Mitchem, On the harmonious chromatic number of a graph, Disc. Math. 74 (1989), 151– 157.
• [15] J. Tymoczko, Distinguishing numbers for graphs and groups, Electron. J. Combin. 11.1 (2004), #R63.
• [16] N. Zagaglia Salvi, A note on the line-distinguishing chromatic number and the chromatic index of a graph, J. Graph Theory 17 (1993), 589–591.