Sul-Young Choi, Jonathan Needleman

Department of Mathematics, Statistics and Computer Science, Le Moyne College, Syracuse New York sulyoung@lemoyne.edu, needlejs@lemoyne.edu

In a uniform central graph (UCG) the set of eccentric vertices of a central vertex is the same for all central vertices. This collection of eccentric vertices is the centered periphery. For a pair of graphs (C, P) the central-peripheral appendage number, Aucg(C, P), is the minimum number vertices needed to be adjoined to the graphs C and P in order to construct a uniform central graph H with center V (C) and centered-periphery V (P). We compute Aucg(C, P) in terms of the radius and diameter of P, and whether or not C is a complete graph. In the process we show Aucg(C, P) ≤ 6 if diam(P) > 2. We also provide structure theorems for UCGs in terms of the centered periphery.

Keywords: uniform central graph, appendage number, center, centered periphery

Mathematics Subject Classification : 05C12, 05C35

DOI: 10.5614/ejgta.2020.8.1.12

1. Introduction

An appendage number of a graph G is the minimum number of vertices to be added to G to obtain a supergraph H of G so that H satisfies some prescribed properties. There is no restriction on the number of edges. Appendage numbers are a measurement of how efficiently one can construct a graph with desired properties. In this paper we study appendage numbers where the supergraph is what is known as a uniform central graph.

Let G = (V (G), E(G)) be a simple graph. The eccentricity of a vertex v, denoted by eG(v), is defined by max{d(u, v) : u ∈ V (G)} where d(u, v) is the distance between two vertices u and

Received: 10 February 2019, Revised: 11 June 2019, Accepted: 27 December 2019.

v. When the graph is clear from context we will just write \(e_G(v) = e(v)\). A vertex x is called an eccentric vertex of v if d(v,x) = e(v); and the set of all eccentric vertices of v is denoted by EC(v). The radius of G, r(G) or r, is the minimum eccentricity of the vertices in G and the diameter of G, diam(G), is the maximum eccentricity of the vertices in G.

A (u,v)-path is called a geodesic, when the length of the path is d(u,v). For a central vertex u, a (u,v)-geodesic is called a radial path if the length of the path is r(G). For any nonempty subset S of vertices in G, \(\langle S \rangle\) represents the subgraph of G induced by S. For terminology not defined in this paper, the reader is referred to [6].

Let \(\mathcal{Z}(G) = \{z \in V(G) | e(z) = r(G)\}\) be the center of the graph G. We now introduce a new term called the centered periphery.

Definition The centered periphery of G is

\[\mathcal{CP}(G) = \bigcup_{z \in \mathcal{Z}(G)} EC(z).\]

This is the set of vertices that are far from at least one vertex in the center. The periphery, which is the set of maximally eccentric vertices, coincides with centered periphery for some graphs. However, in many cases they differ. For instance, the graph in Figure 1 has periphery \(\{p_0, p_1, p_2, p_5, p_6, p_7\}\) while the centered periphery is \(\{p_1, \dots, p_6\}\).

Figure 1: Periphery \(\neq\) Centered Periphery

A graph G is called a uniform central graph, or UCG, if EC(c) is same for all central vertices c of G, i.e. \(EC(c) = \mathcal{CP}(G)\) for every vertex c in the center. The term was introduced in [3] where it is shown that a radial path in a uniform central graph contains only one central vertex. However, the structure of UCGs have not been extensively studied and there is no known classification of UCGs.

So far all papers involving UCGs have only used centers to study UCGs and have not looked at the centered periphery [2, 3, 4, 5]. However, it appears the structure of a UCG relies on both the center and the centered periphery. In this paper we study an appendage number that relies on both the center, and the centered periphery. In doing so we show how the structure of UCGs relies on both substructures. With this in mind we consider a UCG G to consist of three types of vertices, the center \(\mathcal{Z}(G)\), the centered periphery \(\mathcal{CP}(G)\), and the "intermediate" vertices defined by \(\mathcal{I}(G) = V(G) - (\mathcal{Z}(G) \cup \mathcal{CP}(G))\).

We now turn to appendage numbers. Buckley, Miller and Slater [1] studied the appendage number of a graph G, where G is the center of its supergraph. These results have been extended to UCGs. In [4] Gu determined the appendage number for G where G is the center and supergraph is

a UCG. More recently S. Klavzar, K. Narayankar, and S. Lokesh [5] looked at appendage numbers ˇ of G where the supergraph is a UCG and G is any subgraph.

In this paper we study the appendage number for a pair of given graphs (C, P), where the supergraph H is a uniform central graph satisfying hZ(H)i = C and hCP(H)i = P. We denote the central-peripheral appendage number, Aucg(C, P), as the minimum number of "intermediate" vertices needed to construct such a uniform central graph H. Note, that by construction, C and P will be disjoint in H. By convention Aucg(C, P) = ∞ if there is no graph satisfying the above conditions. We summarize our main results as follows.

Theorem 6.1. Let C =< v > and P be any graph with r(P) ≥ 2. Then Aucg(C, P) = 0.

Theorem 6.2. When n ≥ 2 and a graph P

\[A_{\mathrm{ucg}}(K_n,P) = \begin{cases} 2 & \text{if } \mathrm{diam}(P) \geq 4 \text{ and } r(P) \geq 3 \\ 3 & \text{if } \mathrm{diam}(P) \geq 3 \text{ and } r(P) = 2 \end{cases}\]

Furthermore, for all t ∈ N there is a graph P with diam(P) = r(P) = 2 and Aucg(Kn, P) ≥ t.

Theorem 6.3. For a graph P, if C is a graph with diam(C) > 1 then

\[A_{\mathrm{ucg}}(C,P) = \begin{cases} 4 & \text{if } \mathrm{diam}(P) = \infty \\ 5 & \text{if } 5 \leq \mathrm{diam}(P) < \infty \\ 5 \text{ or } 6 & \text{if } \mathrm{diam}(P) = 4 \text{ and } r(P) = 4 \\ 6 & \text{if } \mathrm{diam}(P) = 4 \text{ and } r(P) = 2 \\ 6 & \text{if } \mathrm{diam}(P) = 3 \end{cases}\]

Furthermore, for all t ∈ Z there is a graph P with diam(P) = r(P) = 2 and Aucg(C, P) ≥ t.

These results show that it takes more vertices to construct UCGs with centered periphery that have small radius and diameter. In fact, when diam(P) = r(P) = 2, depending on the structure of P, one needs arbitrarily large number of intermediate vertices. This shows the importance of the centered periphery in understanding UCGs.

We also draw attention to the fact that our results depend on whether or not C is a complete graph, which matches the results of Gu [4]. In light of this we organize our paper in the following way. Section 2 focuses on results that do not depend on the center. These results are then applied to graphs with specific centers; complete graphs in Section 3 and all other graphs in Section 4 to classify central-peripheral appendage numbers. The results in Sections 3 and 4 are given in terms of sizes of various coverings of P. In Section 5 we compute the sizes of these coverings. Section 6 summarizes the previous work and proves Theorems 6.1, 6.2, and 6.3. Finally, in Section 7, using different techniques than Gu [4], we obtain her results as a corollary of our results.

2. General Centers

This section develops results about the structure of a uniform central graph H in terms of P = hCP(H)i. We do this by studying coverings of the centered periphery.

A covering of a graph G = (V, E) is a set V = {V1, . . . , Vk} where Vⁱ ⊂ V with ∪Vⁱ = V . We say k is the size of the covering. A subcovering of a covering V is a subset of V that is also a covering.

Throughout this paper we are interested in coverings satisfying various properties. The simplest and most important of these conditions is condition A. Let P be a graph with covering P = {P1, . . . , Pk}. We say the pair (P, P) satisfies

Condition A if for each 1 ≤ i ≤ k, there is a vertex p /∈ Pⁱ satisfying d(Pⁱ , p) ≥ 2.

When there is no confusion to the graph P, we simply say P satisfies condition A. Elements of a cover can overlap. It is useful to minimize this overlap in some sense.

Lemma 2.1. Let {P1, . . . , Pk} be a covering of P satisfying condition A. Then there is a subcovering {P 0 1 , . . . , P^{0 η}} satisfying condition A and for each i (1 ≤ i ≤ η)

\[P_i' \not\subset \bigcup_{j \neq i} P_j'.\]

That is, for each i there exists p˜ⁱ ∈ P 0 i such that p˜ⁱ 6∈ P 0 j for all j 6= i.

Proof. Suppose there exists an i satisfying

\[P_i \subset \bigcup_{j \neq i} P_j.\]

Then {P^j : j 6= i} is a subcovering satisfying condition A.

The main idea of this paper is to take the question of determining Aucg(C, P) and to transfer it to questions about the size of coverings of P satisfying various conditions. This is possible because for any UCG there exists a natural covering on P. It turns out this covering satisfies condition A. These coverings are used to obtain lower and upper bounds on Aucg(C, P). To do this we first introduce some notation.

For a uniform central graph H we define a stratification of V (H) in terms of the distance from the center. Let

\[D_m = \{ u \in V(G) : d(u, \mathcal{Z}(H)) = m \}\]

for 0 ≤ m ≤ r = r(H). Then D⁰ = Z(H) and D^r = CP(H). For an enumeration D¹ = {x1, . . . , xk}, let Lⁱ be the set of all radial paths from C to P containing xⁱ

Lemma 2.2. Let H be a uniform central graph with hCP(H)i = P. Then the graph H induces a covering on P satisfying condition A.

Proof. Let H be a uniform central graph with hCP(H)i = P. Furthermore, let C = hZ(H)i and D¹ = {x1, . . . , xk} for some k. Let Pⁱ = V (P) ∩ V (Li). Then {P1, . . . , Pk} is a covering of P since each radial path from C to P contains a vertex in D1.

Assume {P1, . . . , Pk} does not satisfy the condition A. Then there is an i satisfying that for every vertex p 6∈ Pⁱ there is a p ⁰ ∈ Pⁱ with d(p, p⁰ ) ≤ 1. This shows xⁱ ∈ V (C), a contradiction.

Since \(x_i \in D_1\), there is a central vertex c with \(d(x_i, c) = 1\). For each vertex v of H not in P, \(d(c, v) \le r(H) - 1\) and hence \(d(x_i, v) \le r(H)\). If p is a vertex in \(P_i\), \(d(x_i, p) = r(G) - 1\) from the construction of \(P_i\).

If p is a vertex in P but not in \(P_i\), then there is a vertex \(p' \in P_i\) with d(p, p') = 1 and so

\[d(x_i, p) \le d(x_i, p') + d(p', p) = (r(H) - 1) + 1 = r(H)\]

and so \(x_i \in V(C)\), a contradiction.

Corollary 2.1. If H is a UCG with \(P = \langle \mathcal{CP}(H) \rangle\), then r(P) > 1.

Proof. If r(P) = 1, then there is \(q \in V(P)\) with \(e_P(q) = 1\). Let \(\overline{P} = \{P_1, \dots, P_k\}\) be the induced cover of P. Without loss of generality we may assume \(q \in P_1\). Then for all \(p \in V(P)\), \(d(p, P_1) \le 1\) and condition A is not met. Hence by Lemma 2.2 P is not a centered periphery for any UCG.

Corollary 2.2. If P is a graph with \(r(P) \leq 1\), then \(A_{\text{ucg}}(C, P) = \infty\) for all graphs C.

For H, a UCG with \(C = \langle \mathcal{Z}(H) \rangle\) and \(P = \langle \mathcal{CP}(H) \rangle\), we use the induced covering from Lemma 2.2 to gain a better understanding of the structure of \(\mathcal{I}(H)\).

Let \(D_1 = \{x_1, \dots, x_k\}\) and \(\{P_1, \dots, P_k\}\) be the induced covering of P defined as in Lemma 2.2. Without loss of generality assume \(\{P_1, \dots, P_{k'}\}\) with \(k' \leq k\), is subcovering with non-empty elements. Also let \(\overline{P} = \{P_1, \dots, P_{k''}\}\) and \(\{\tilde{p}_1, \dots, \tilde{p}_{k''}\}\), with \(k'' \leq k'\), be as in Lemma 2.1. For \(1 \leq m \leq r(H) - 1\) we define the following subsets of \(D_m\).

\[D'_m = D_m \cap \bigcup_{i=1}^{k'} V(\mathcal{L}_i) \text{ and } D''_m(\overline{P}) = D_m \cap \bigcup_{i=1}^{k''} V(\mathcal{L}_i).\]

\(D_m\) and \(D'_m\) are well-defined with respect to H, however \(D''_m(\overline{P})\) depends on a choice of subcover. When this choice is clear from context, we simply use \(D''_m\).

The following proposition describes the structure of \(\mathcal{I}(H)\) that is the key to the rest of this paper.

Proposition 2.1. Let H be a UCG with \(C = \langle \mathcal{Z}(H) \rangle\), \(P = \langle \mathcal{CP}(H) \rangle\), \(\overline{P} = \{P_1, \dots, P_{k''}\}\) and \(\{\tilde{p}_1, \dots, \tilde{p}_{k''}\}\) as in Lemma 2.1 with respect to the induced covering from Lemma 2.2. Then any \((x_i, \tilde{p}_i)\)-geodesic and \((x_j, \tilde{p}_j)\)-geodesic are disjoint if \(i \neq j\).

Proof. For \(L_i\) a \((x_i, \tilde{p}_i)\)-geodesic and \(L_j\) a \((x_j, \tilde{p}_j)\)-geodesic with \(i \neq j\), assume there exists a \(y \in V(L_i) \cap V(L_j)\). Let \(L'_i\) be the subpath of \(L_i\) from \(x_i\) to y and \(L'_j\) the subpath of \(L_j\) from y to \(\tilde{p}_j\). The concatenation of \(L'_i\) and \(L'_j\) yields a \((x_i, \tilde{p}_j)\)-geodesic and so \(\tilde{p}_j \in P_i\), a contradiction. \(\square\)

Corollary 2.3. With the assumptions of Proposition 2.1, \(|D_1''| \le |D_m''|\) for \(1 \le m \le r(H) - 1\).

Proof. For each \(1 \leq i \leq k''\) there exists \(L_i\), a \((x_i, \tilde{p}_i)\)-geodesic. Let \(\mathcal{L} = \{L_1, \ldots, L_{k''}\}\) and \(F_m = V(\mathcal{L}) \cap D_m''\). By Proposition 2.1 \(|F_1| = |F_m|\). Then by the construction of \(F_m\)

\[|D_1''| = |F_1| = |F_m| \le |D_m''|.\]

We often work with UCGs with few intermediate vertices. For such UCGs we can say more about their structure.

Lemma 2.3. Let H be a UCG with \(P = \langle \mathcal{CP}(H) \rangle\) and r = r(H). Furthermore, let \(\overline{P} = \{P_1, \ldots, P_{k''}\}\) be a subcovering of the induced covering and \(\{\tilde{p}_1, \ldots, \tilde{p}_{k''}\}\) an associated set of vertices as in Lemma 2.1. If \(|D_1''| = |D_{r-1}''|\) then for each \(P_i \in \overline{P}\) there is a unique \(y_i \in D_{r-1}''\) such that \(y_i\) is adjacent to every vertex in \(P_i\). Furthermore, if \(i \neq j\), then \(y_i \neq y_j\).

Proof. Let \(D_1'' = \{x_1, \dots, x_{k''}\}\). For each i, let \(L_i\) be an \((x_i, \tilde{p}_i)\)-geodesic and let \(y_i\) be the vertex on \(L_i\) adjacent to \(\tilde{p}_i\). Then \(y_i \in D_{r-1}''\). By Proposition 2.1 \(y_i \neq y_j\) when \(i \neq j\). Furthermore \(D_{r-1}'' = \{y_1, \dots, y_{k''}\}\). We claim \(y_i\) is adjacent to every vertex in \(P_i\).

For a vertex \(p \in P_i\) there is a \(c \in \mathcal{Z}(H)\) and a (c, p)-radial path L that contains \(x_i\). Let y be the vertex on L adjacent to p. Since \(y \in D''_{r-1}\), \(y = y_j\) for some \(1 \le j \le k''\). Since \(y_j\) is adjacent to \(\tilde{p}_j\), there is a \((x_i, \tilde{p}_j)\)-geodesic of length r-1. Therefore, \(\tilde{p}_j \in P_i\) which means j=i, \(y=y_i\) and \(y_i\) is adjacent to p.

Lemma 2.4. Let H be a UCG with \(C = \langle \mathcal{Z}(H) \rangle\) and \(P = \langle \mathcal{CP}(H) \rangle\) and assume the induced covering \(\overline{P} = \{P_1, \dots, P_k\}\) satisfies the conditions of the subcovering in Lemma 2.1. That is \(D_1 = D_1''\). Then each vertex in C is adjacent to each vertex in \(D_1\).

Proof. Let \(D_1 = \{x_1, \dots, x_k\}\) and \(\{\tilde{p}_1, \dots, \tilde{p}_k\}\) be an associated set of vertices to \(\overline{P}\) as in Lemma 2.1. For each vertex c in the center and each \(\tilde{p}_i\), there is a \((c, \tilde{p}_i)\)-radial path. By construction of \(\overline{P}\) and definition of \(\tilde{p}_i\), each \((c, \tilde{p}_i)\)-radial path must contain \(x_i\). Therefore, c and \(x_i\) are adjacent. \(\Box\)

For a graph P, let \(\operatorname{cov}_A(P)\) be the smallest size of a covering of P satisfying condition A. From the definition of condition A, it follows that \(\operatorname{cov}_A(P) \geq 2\) for any graph P with r(P) > 1. The following result is critical in obtaining lower bounds on \(A_{\operatorname{ucg}}(C, P)\).

Proposition 2.2. If H is a uniform central graph with \(C = \langle \mathcal{Z}(H) \rangle\), \(\langle \mathcal{CP}(H) \rangle = P\), r = r(H) and \(\kappa = \text{cov}_A(P)\), then \(|\mathcal{I}(H)| \geq \kappa(r-1)\).

Proof. Let \(\{P_1, \ldots, P_{k''}\}\) be a subcover of the induced cover on P from H from Lemmas 2.2 and 2.1. By definition of \(\kappa\) and corollary 2.3 it follows that

\[\kappa \le k'' = |D_1''| \le |D_m''| \le |D_m|.\]

Since

\[\mathcal{I}(H) = \bigcup_{m=1}^{r-1} D_m\]

the result follows.

Proposition 2.2 is used to obtain bounds on the radius of a UCG.

Corollary 2.4. If H is a uniform central graph with \(\langle \mathcal{CP}(H) \rangle = P\), \(\kappa = \text{cov}_A(P)\) and \(|\mathcal{I}(H)| \leq s\kappa + t\) where \(s, t \in \mathbb{N}\) and \(t < \kappa\), then \(r(H) \leq s + 1\).

Proof. Observing \((s+1)\kappa > s\kappa + t\) the result follows from the contrapositive of Proposition 2.2.

We now construct a graph with center C and centered periphery P. Let C and P be graphs, and \(\rho \in \mathbb{N}\). Suppose \(\overline{P} = \{P_1, \dots, P_k\}\) is a covering of P. Define a graph \(G = \mathcal{G}(C, P, \overline{P}, \rho)\) as follows:

\[V(G) = V(C) \cup V(P) \cup \{x_{i,j} : 0 \le i \le k, 1 \le j \le \rho\}\]

and ab is an edge in G if and only if one of the following occurs

• 1. ab is an edge of C.
• 2. ab is an edge of P.
• 3. a is a vertex of C and \(b = x_{i,1}\) for some i with \(0 \le i \le k\).
• 4. \(a \in P_i\) and \(b = x_{i,\rho}\) for some i with \(1 \le i \le k\).
• 5. \(a = x_{i,j}\) and \(b = x_{i,j+1}\) for i and j with \(0 \le i \le k, 1 \le j \le \rho 1\)

Figure 2: \(G = \mathcal{G}(C, P, \overline{P}, \rho)\)

Proposition 2.3. For two given graphs C and P, let \(\overline{P} = \{P_1, \dots, P_k\}\) be a covering of P satisfying condition A, and \(\rho \ge \min\{\operatorname{diam}(C), 2\}\). Then \(G = \mathcal{G}(C, P, \overline{P}, \rho)\) is a UCG with radius \(\rho + 1\), \(\langle \mathcal{Z}(G) \rangle = C\) and \(\langle \mathcal{CP}(G) \rangle = P\).

Proof. From the construction of G, we can show the following:

• i) For all \(j=1,\ldots,\rho\) and any vertex p in P, \(d(x_{0,j},p)\geq \rho+2\), and so \(e(x_{0,j})\geq \rho+2\) and \(e(p)\geq \rho+2\).
• ii) For all i and j with \(1 \le i \le k\) and \(2 \le j \le \rho\), \(d(x_{i,j}, x_{0,\rho}) \ge \rho + 2\), and so \(e(x_{i,j}) \ge \rho + 2\).

• iii) Since the covering P satisfies condition A, for each i with 1 ≤ i ≤ k there exists a vertex p in P^j for some j 6= i satisfying d^P (Pⁱ , p) ≥ 2. Thus d(xi,1, p) ≥ ρ + 2 and e(xi,1) ≥ ρ + 2.
• iv) For a vertex c in C, d(c, xi,j ) ≤ ρ, d(c, p) = ρ + 1 for all p in P, and d(c, c⁰ ) ≤ 2 for any vertex c 0 in C. This implies e(c) = ρ + 1 and EC(c) = V (P).

Therefore, G = G(C, P, P , ρ) is a UCG with radius ρ + 1, hZ(G)i = C and hCP(G)i = P.

We end this section with a result about conditions when a spanning subgraph of a UCG is still a UCG.

Lemma 2.5. Let H be a UCG with V (C) = Z(H) and let G be a spanning subgraph of H. Then G is a UCG with V (C) = Z(G) and CP(G) = CP(H) if for all c ∈ V (C) and x ∈ V (G), dG(c, x) = dH(c, x).

Proof. Since E(G) ⊂ E(H), the eccentricity of a vertex v in G is greater than or equal to the eccentricity of v in H. The assumption that dG(c, x) = dH(c, x) for all c ∈ V (C) and x ∈ V (G) implies Z(G) = V (C) and EC(c) in G is CP(H). Hence, G is a UCG with V (C) = Z(G) and CP(G) = CP(H).

3. When C = Kⁿ with n ≥ 2

In this section we compute appendage numbers when the center C is a complete graph Kⁿ with n ≥ 2 in terms of the size of a smallest covering for the centered periphery.

We introduce a new condition on coverings. Let P be a graph with covering P = {P1, . . . , Pk}. We say (P, P) satisfies

Condition B if for every 1 ≤ i ≤ k and for each p ∈ Pⁱ either

• 1. there is a vertex p ⁰ 6∈ Pⁱ with d(p, p⁰ ) ≥ 3, or
• 2. there is a j 6= i satisfying d(p, P^j ) ≥ 2.

Once again, we say the covering P satisfies condition B when there is no confusion about P. Also define covAB(P) to be the smallest size of a covering of P satisfying both condition A and condition B.

Before determining appendage numbers it is necessary to prove the existence of coverings satisfying conditions A and B.

Lemma 3.1. Let P be a graph with r(P) ≥ 2. Then there exists a covering of P satisfying conditions A and B.

Proof. Let V (P) = {p1, . . . , pk}. Then P = {{p1}, . . . , {pk}} is a covering of P and P satisfies conditions A and B because r(P) ≥ 2.

We now find the appendage numbers in terms of κ = covA(P).

Proposition 3.1. κ ≤ Aucg(Kn, P) ≤ κ + 1 where κ = covA(P).

Proof. By Lemma 3.1 there is a covering of P satisfying condition A, so let P = {P1, . . . , Pκ} be a smallest covering of P satisfying condition A. By Proposition 2.3, the graph G = G(Kn, P, P , 1) is a UCG with radius 2 and |I(G)| = κ + 1, and thus Aucg(Kn, P) ≤ κ + 1. The lower bound follows from Proposition 2.2.

Theorem 3.1. Let κ = covA(P). Then Aucg(Kn, P) = κ if and only if covAB(P) = κ.

Proof. Suppose covAB(P) = κ and let P = {P1, . . . , Pκ} be a smallest covering of P with respect to conditions A and B. Also, let G = G(Kn, P, P , 1) − {x0,1}. Since P satisfies condition B, one can verify that for G, e(p) ≥ 3 for all p ∈ V (P). Using a similar argument to Proposition 2.3 we can show G is a UCG with r(G) = 2, hCP(G)i = P, hZ(G)i = Kⁿ and |I(G)| = κ.

Now assume Aucg(Kn, P) = κ. Let H be a UCG with P = hCP(H)i,hZ(H)i = Kⁿ and |I(H)| = κ. From corollary 2.4, r(H) = 2. Let {P1, . . . , Pk} be the induced covering of P as in Lemma 2.2. We know

\[\kappa \le k = |D_1| = |\mathcal{I}(H)| = \kappa\]

and so k = κ. Let D¹ = {x1, . . . , xk}, where xⁱ is associated to Pⁱ .

Suppose p is a vertex in Pⁱ . Since e(p) ≥ 3 there is an x ∈ V (H) with dH(p, x) ≥ 3. Note, x 6∈ Pⁱ because all vertices in Pⁱ are adjacent to xⁱ . If x ∈ P^j for some j 6= i, then condition B(1) is satisfied by definition. Finally, if x = x^j ∈ D¹ for some j 6= i, then d^P (p, P^j ) ≥ 2 and so P satisfies condition B(2).

In Section 5 we determine when covA(P) = covAB(P).

4. When C 6= Kⁿ

For this section assume that C is not a complete graph and so diam(C) ≥ 2. The results in this section mirror those of when C = Kn, however conditions on the coverings of P, as well as the proofs, are more technical.

Proposition 4.1. For a given pair of graphs (C, P) , 2κ ≤ Aucg(C, P) ≤ 2κ + 2 where κ = covA(P).

Proof. For a given pair of graphs C and P, suppose H is a UCG with hZ(H)i = C and hCP(H)i = P. Then r(H) ≥ diam(C)+1 ≥ 3. From corollary 2.2 we obtain a lower bound Aucg(C, P) ≥ 2κ. For the upper bound consider G = G(C, P, P , 2) where P is a smallest covering of P satisfying condition A. By Proposition 2.3, G is a UCG with |I(G)| = 2κ+2 and so Aucg(C, P) ≤ 2κ+2.

In the proof of Proposition 4.1 we use the fact that G(C, P, P , 2) is a UCG so long as P satisfies condition A. We now consider a modification of this graph, and determine conditions that this new graph is a UCG.

Let P = {P1, . . . , Pk} be a covering of P and let

\[G = \mathcal{G}(C, P, \overline{P}, 2) - \{x_{0,1}, x_{0,2}\}.\]

By construction, d(c, p) = 3 for all c ∈ V (C), p ∈ V (P), and d(c, x) ≤ 2 for x ∈ V (G) − V (P). So G is a UCG with center C and centered periphery P if and only if for all u ∈ V (G) − V (C), e(u) ≥ 4.

Consider the case u = xi,1. If G is a UCG, P must satisfy condition A. This implies e(xi,1) ≥ 4 for all 1 ≤ i ≤ k.

Next, consider the case u = xi,² for some 1 ≤ i ≤ k. Since e(u) ≥ 4 there exists a v ∈ V (G) such that d(u, v) ≥ 4. Because v 6∈ V (C) and d(u, xj,1) ≤ 3, either v ∈ V (P) or v = xj,² for some j 6= i. If v ∈ V (P) then v 6∈ Pⁱ and d(v, Pi) ≥ 3. If v = xj,2, then d(Pⁱ , P^j ) ≥ 2.

Finally, consider the case u ∈ Pⁱ for some i. If G is a UCG, then e(u) ≥ 4, and so there is a v ∈ V (G) such that d(u, v) ≥ 4. Since v 6∈ V (C) and v 6∈ Pⁱ because d(p, p⁰ ) ≤ 2 for all p, p⁰ ∈ Pⁱ , it follows that either v = xj,1, v = xj,² or v ∈ P^j for some j 6= i. If v = xj,¹ then d(u, P^j ) ≥ 2 for j 6= i. If v = xj,² then d(u, P^j ) ≥ 3. Finally, if v ∈ P^j for some j 6= i, then for all p ∈ P^j

\[4 \le d(u, v) \le d(u, p) + d(p, v) \le d(u, p) + 2.\]

We conclude d(u, P^j ) ≥ 2. This analysis gives rise to two new conditions on P.

Let P = {P1, . . . , Pk} be a covering of a graph P. If for all 1 ≤ i ≤ k we say (P, P) satisfies

Condition A⁰ if either

• 1. there is a p 6∈ Pⁱ satisfying d(Pⁱ , p) ≥ 3, or
• 2. there is a j 6= i satisfying d(Pⁱ , P^j ) ≥ 2.

Condition B⁰ if for each p ∈ Pⁱ there is a j 6= i satisfying d(p, P^j ) ≥ 2.

Condition A⁰ arises from e(xi,2) ≥ 4 and condition B⁰ from e(p) > 4, for p ∈ V (P). Note condition A⁰ implies condition A, and condition B⁰ implies condition B. We often abuse notation and say the covering P satisfies a specified condition.

Let covA⁰(P) be the smallest size of the covering of P satisfying condition A⁰ and covA0B⁰(P) the smallest size of the covering of P satisfying conditions A⁰ and B⁰ .

The arguments used to determine conditions A⁰ and B⁰ are bi-directional. This implies the following proposition.

Proposition 4.2. Let C and P be graphs, P a covering of P, and G = G(C, P, P , 2)− {x0,1, x0,2}. Then G is a UCG with center C and centered periphery P if and only if P satisfies conditions A⁰ and B⁰ .

We are now ready to relate appendage numbers to coverings.

Proposition 4.3. Let κ = covA(P). For a graph P with r(P) > 1, covA0B⁰(P) = κ if and only if Aucg(C, P) = 2κ.

Proof. First, assume covA0B⁰(P) = κ. Let P = {P1, . . . , Pκ} be a covering of P satisfying conditions A⁰ and B⁰ . Then by Proposition 4.2 the graph

\[G = \mathcal{G}(C, P, \overline{P}, 2) - \{x_{0,1}, x_{0,2}\}\]

is a UCG and |I(G)| = 2κ and so Aucg(C, P) ≤ 2κ. However, by Proposition 4.1, Aucg(C, P) ≥ 2κ and the result follows.

Next, assume Aucg(C, P) = 2κ. Let H be a UCG with P = hCP(H)i, C = hZ(H)i and |I(H)| = 2κ. Note that r(H) = 3 by corollary 2.4.

Let {P1, . . . , Pk} be the induced covering of P as in Lemma 2.2. There exists a subcover P = {P1, . . . , P^{k 00}} and an associated set of vertices {p˜1, . . . , p˜^{k 00}} as in Lemma 2.1. Assume D^{00 1} = {x1, . . . , x^{k 00}}, and by corollary 2.3 |D⁰⁰ 2 | ≥ k ⁰⁰. Because κ = covA(P) and P satisfies condition A, we know

\[2\kappa \le 2k'' \le |D_1''| + |D_2''| \le |\mathcal{I}(H)| = 2\kappa,\]

and so k ⁰⁰ = |D⁰⁰ 1 | = |D⁰⁰ 2 | = κ. This implies D¹ = D⁰⁰ 1 , D² = D⁰⁰ 2 and κ = k ⁰⁰ = k.

We now show H contains a spanning subgraph isomorphic to

\[G = \mathcal{G}(C, P, \overline{P}, 2) - \{x_{0,1}, x_{0,2}\}.\]

First, for each p˜ⁱ defined above and each central vertex c there is a (c, p˜i)-radial path. By construction of p˜ⁱ this path must contain xⁱ , and thus xⁱ is adjacent to every c in the center by Lemma 2.4.

By Lemma 2.1 there is an enumeration of D² = {y1, . . . , yk} so that yⁱ is adjacent to both xⁱ and each vertex in Pⁱ . Therefore, G = G(C, P, P , 2) − {x0,1, x0,2} is isomorphic to a spanning subgraph of H. By Lemma 2.5, G is a UCG and by Proposition 4.2, P satisfies conditions A⁰ and B 0 .

We now move on to understand when Aucg(C, P) = 2κ + 1. Let H be a UCG such that hZ(H)i = C, hCP(H)i = P and |I(H)| = 2κ + 1. By Proposition 4.3, κ 6= covA0B⁰(P). Also, by corollary 2.4 r(H) = 3, and hence |D1| + |D2| = 2κ + 1. Let {P1, . . . , Pk} be the induced covering of P through D¹ = {x1, . . . , xk} as in Lemma 2.2. Without loss of generality let P = {P1, . . . , P^{k 00}}, with k ⁰⁰ ≤ k, be a subcover with an associated set of vertices {p˜1, . . . , p˜^{k 00}} as in Lemma 2.1. Then

\[2\kappa \le 2k'' \le |D_1''| + |D_2''| \le |\mathcal{I}(H)| = 2\kappa + 1\]

and hence κ = k 00 .

Since

\[\kappa = |D_1''| \le |D_1| \text{ and } \kappa = |D_1''| \le |D_2''| \le |D_2|,\]

either |D1| = κ + 1 or |D2| = κ + 1.

We first address when |D1| = κ + 1 and |D2| = κ.

Proposition 4.4. Assume Aucg(C, P) = 2κ + 1, and let H be a UCG such that hZ(H)i = C, hCP(H)i = P, and |I(H)| = 2κ + 1 where κ = covA(P). Furthermore, assume |D1| = κ + 1. Then covA⁰(P) = κ.

Proof. By corollary 2.3 it follows that

\[\kappa = |D_1''| \le |D_2''| \le |D_2| = \kappa.\]

Therefore \(D_2 = D_2''\) and \(|D_1''| = \kappa\). Since \(k = |D_1| = \kappa + 1\), \(x_k \in D_1\) but \(x_k \notin D_1''\).

Next, we prove \(x_k \notin D_1'\) by showing if \(x_k \in D_1'\), then \(\overline{P}\) satisfies both conditions A' and B'. Hence \(A_{\text{ucg}}(C, P) = 2\kappa\) by Proposition 4.3.

Assume \(x_k \in D_1'\), that is \(D_1 = D_1'\). Because \(|D_2| = |D_2''| = \kappa = |D_1''|\) we may assume \(D_2 = \{y_1, \ldots, y_\kappa\}\) such that each \(y_i\) is adjacent to \(x_i\) and all vertices of \(P_i\) by Lemma 2.3. To understand the structure of \(P_k\), define the indexing set

\[I = \{i : x_k \text{ is adjacent to } y_i \text{ for some } y_i \in D_2\}.\]

From the definition of \(D'_1\) and I,

\[P_k = \bigcup_{i \in I} P_i.\]

For each \(j \notin I\) every radial path to \(\tilde{p}_j\) must contain \(x_j\). Hence, each central vertex \(c \in V(C)\) is adjacent to \(x_j \in D_1\) for \(j \notin I\). A similar argument shows that for each \(c \in V(C)\) and each \(i \in I\), c is adjacent to either \(x_k\) or \(x_i\).

We now show \(\overline{P}\) satisfies conditions A' and B'.

First, assume condition B' fails. Then there exists an \(\iota\) and a vertex \(p \in P_{\iota}\) such that \(d_P(p, P_j) \le 1\) for all \(j \ne \iota\). Therefore, there is a \(p_j \in P_j\) such that \(d(p, p_j) \le 1\), and so the following hold:

• i) \(d(p, x_j) \le d(p, p_j) + d(p_j, x_j) \le 3\).
• ii) \(d(p, y_j) \le d(p, p_j) + d(p_j, y_j) \le 2.\)
• iii) \(d(p, p') \le d(p, p_j) + d(p_j, p') \le 3\) for all \(p' \in P_j\).
• iv) \(d(p, x_{\iota}) = 2\).
• v) \(d(p, y_{\iota}) = 1\).
• vi) d(c, p) = 3 for \(c \in V(C)\).

If \(\iota \in I\), then \(d(p, x_k) = 2\). If \(\iota \notin I\), then for a \(j \in I\)

\[d(p, x_k) \le d(p, p_j) + d(p_j, x_k) \le 3\]

since \(d(p_j, x_k) = 2\). Therefore e(p) = 3, a contradiction, and so \(\overline{P}\) satisfies condition B'.

Next, assume condition A' fails. Then there exists an \(\iota\) such that \(d_P(P_\iota, p') \leq 2\) for all \(p' \in V(P) - P_\iota\) and \(d_P(P_\iota, P_j) \leq 1\) for all \(j \neq \iota\). Then \(d(y_\iota, p) \leq 3\) for all \(p \in V(P)\) and \(d(y_\iota, y_j) \leq 3\) for all \(j \neq \iota\). We obtain a contradiction by showing \(y_\iota\) is in the center.

If \(\iota \not\in I\), then for each \(x_j \in D_1\) there is a \(c \in V(C)\) that is adjacent to \(x_j\). Then \(y_\iota - x_\iota - c - x_j\) is a path and \(d(y_\iota, x_j) \leq 3\). Similarly when \(\iota \in I\) and \(j \notin I\), \(d(y_\iota, x_j) \leq 3\). If \(\iota, j \in I\) then

\(y_{\iota} - x_k - y_j - x_j\) is a path and so \(d(y_{\iota}, x_j) \leq 3\). Finally, \(d(y_{\iota}, c) = 2\) for all \(c \in V(C)\), and so \(e(y_{\iota}) = 3\), a contradiction and \(\overline{P}\) satisfies condition A'.

Since P satisfies conditions A' and B', \(A_{\text{ucg}}(C, P) = 2\kappa\) by Proposition 4.3. This contradicts the assumptions of the proposition and hence \(x_k \notin D'_1\) and so \(D'_1 = D''_1\).

Then \(x_k\) is not on a radial path because \(x_k \not\in D_1'\). Therefore, vertices adjacent to \(x_k\) are in C or \(D_1''\). Furthermore each \(y_i \in D_2\) satisfies \(e(y_i) \geq 4\) from H being a UCG with r(H) = 3. Therefore, there exists a \(u \in V(G)\) with \(d(y_i, u) \geq 4\). Because \(d(c, y_i) = 2\) for all \(c \in V(C)\), we know \(u \notin V(C)\).

Because \(D_1' = D_1''\), each \((c, \tilde{p}_i)\)-radial path contains \(x_i\), and hence each c is adjacent to \(x_i\). It follows that for a \(c \in V(C)\) adjacent to \(x_i \in D_1\) that

\[d(y_i, x_i) \le d(y_i, c) + d(c, x_i) = 3,\]

which means \(u \notin D_1\).

If \(u \in V(P)\) then \(d(u,P_i) \geq 3\) and condition A'(1) is satisfied for i. If \(u = y_j \in D_2''\) then \(d_P(P_i,P_j) \geq 2\) and condition A'(2) is satisfied for i. Since these hold for each i, \(\overline{P}\) satisfies condition A' and \(\operatorname{cov}_{A'}(P) = \kappa\).

A weak converse of Proposition 4.4 also holds.

Proposition 4.5. If P is a graph with r(P) > 1, \(\kappa = \text{cov}_A(P) \neq \text{cov}_{A'B'}(P)\) and \(\text{cov}_{A'}(P) = \text{cov}_A(P)\), then \(A_{\text{ucg}}(C, P) = 2\kappa + 1\).

Proof. Assume \(cov_{A'B'}(P) \neq \kappa\) but \(cov_{A'}(P) = \kappa\). Let \(\overline{P} = \{P_1, \dots, P_\kappa\}\) be a smallest covering with respect to condition A' and

\[G = \mathcal{G}(C, P, \overline{P}, 2) - \{x_{0,2}\}.\]

We claim G is a UCG with \(C = \langle \mathcal{Z}(G) \rangle\), \(P = \langle \mathcal{CP}(G) \rangle\) and \(|\mathcal{I}(G)| = 2\kappa + \underline{1}\).

By Proposition 4.2 the graph \(G' = G - \{x_{0,1}\}\) is a UCG if and only if \(\overline{P}\) satisfies conditions A' and B'. In G', if \(\overline{P}\) satisfies conditions A', then \(e(x_{i,1}) \geq 4\) and \(e(x_{i,2}) \geq 4\). This still holds in G. Furthermore, for each vertex \(p \in V(P)\), \(d(x_{0,1},p) = 4\) in G, and so G is a UCG. Therefore, \(A_{\text{ucg}}(C,P) \leq 2\kappa + 1\), but by Proposition 4.3 \(A_{\text{ucg}}(C,P) > 2\kappa\).

The case when \(|D_2| = \kappa + 1\) is more complicated. To understand this case we consider a new graph G, and determine new conditions for when G is a UCG.

For two graphs C and P, let \(\overline{P} = \{P_1, \dots, P_k\}\) be a covering of P, and \(\overline{Q} = \{Q_0, Q_1, P_2, \dots, P_k\}\) be a covering such that \(Q_0 \cup Q_1 = P_1\).

Define a graph \(G = \mathcal{G}'(C, P, \overline{Q})\) as follows (see Figure 3):

\[V(G) = V(C) \cup V(P) \cup \{x_i, y_j : 1 \le i \le k, 0 \le j \le k\}\]

and ab is an edge in G if and only if one of the following occurs

• i) ab is an edge of C.
• ii) ab is an edge of P.

• iii) a is a vertex of C and \(b = x_i\) for some i with \(1 \le i \le k\).
• iv) \(a \in P_j\) and \(b = y_j\) for some j with \(2 \le j \le k\).
• v) \(a \in Q_l\) and \(b = y_l\) for some l = 0, 1.
• vi) \(a = x_i\) and \(b = y_i\) for \(1 \le i \le k\)
• vii) \(a = x_1\) and \(b = y_0\).

Figure 3: \(G = \mathcal{G}'(C, P, \overline{Q})\)

We now determine conditions on \(\overline{Q}\) for G to be a UCG with \(C=\langle \mathcal{Z}(G)\rangle\) and \(P=\langle \mathcal{CP}(G)\rangle\). By construction for all \(c\in V(C)\) and \(p\in V(P)\), d(c,p)=3, and \(d(c,x)\leq 2\) for all \(x\in V(G)-V(P)\). So G is a UCG with center C and centered periphery P if and only if for all \(u\in V(G)-V(C)\), \(e(u)\geq 4\). Then there exists a vertex v with \(d(u,v)\geq 4\).

First consider the case \(u=x_i\). In every UCG the induced covering satisfies condition A. This implies \(v \in V(P)\) and \(e(x_i) \geq 4\) for all \(1 \leq i \leq k\). Note that, in G the induced covering is \(\overline{P}\), not \(\overline{Q}\).

Next, consider the case \(u=y_i\) for some \(2 \le i \le k\). Since \(v \notin V(C)\) and \(d(v,x_j) \le 3\) for \(1 \le j \le k\), either \(v \in V(P)\) or \(v=y_j\) for \(0 \le j \le k\) and \(j \ne i\). The one of the following holds.

• i) If \(v \in V(P)\) then \(v \notin P_i\) and \(d(P_i, v) \ge 3\).
• ii) If \(v = y_j\), \(2 \le j \le k\) and \(j \ne i\), then \(d(P_i, P_j) \ge 2\).
• iii) If \(v = y_l\) for l = 0 or 1, then \(d(P_i, Q_l) \ge 2\).

Now, consider the case \(u=y_0\) or \(y_1\). Without loss of generality we assume \(u=y_0\). Since \(v \notin V(C)\), \(v \neq x_j\) for \(1 \leq j \leq k\), \(v \neq y_1\) and \(v \notin Q_0 \cup Q_1 = P_1\), the following must hold.

i) If \(v \in V(P)\) then \(v \notin P_1\) and \(d(Q_0, v) \ge 3\).

ii) If \[v = y_j\], \(2 \le j \le k\) and \(j \ne i\), then \(d(Q_0, P_j) \ge 2\).

Now, consider the case u = p ∈ Pⁱ for some 2 ≤ i ≤ k. Once again, if G is a UCG, then e(p) ≥ 4, and so there exists a v ∈ V (G) such that d(u, v) ≥ 4. We know v 6∈ V (C). Also, v 6∈ Pⁱ since d(p, p⁰ ) ≤ 2 for all p ⁰ ∈ Pⁱ . Also note, that for j ≥ 2 and j 6= i, if d(u, y^j ) ≥ 4 then d(u, x^j ) ≥ 4. This implies that we do not need to determine the conditions for d(u, y^j ) ≥ 4. Given this, one of the following must hold.

• i) If v = x^j for j 6= i and 2 ≤ j ≤ k, then d(u, P^j ) ≥ 2.
• ii) If v = x1, then d(u, Q0) ≥ 2 and d(u, Q1) ≥ 2.
• iii) If v = y^l for l = 0 or 1, then d(u, Ql) ≥ 3.
• iv) If v = p ⁰ ∈ P^j − Pⁱ for 2 ≤ j ≤ k and j 6= i, then d(u, p⁰ ) ≥ 4 and d(u, P^j ) ≥ 2.
• v) If v = p ⁰ ∈ Q^l − Pⁱ for l = 0 or 1, then d(p, Ql) ≥ 2 and d(u, p⁰ ) ≥ 4.

The last case to consider, without loss of generality, is u = p ∈ Q0. Since d(u, v) ≤ 3 if v ∈ V (C), v = x1, y⁰ or y¹ or v ∈ Q0, the following must hold.

• i) If v = x^j , then 2 ≤ j ≤ k and d(u, P^j ) ≥ 2.
• ii) If v = y^j for 2 ≤ j ≤ k, then d(u, P^j ) ≥ 3.
• iii) If v = p ⁰ ∈ P^j − Q⁰ for 2 ≤ j ≤ k, then d(u, P^j ) ≥ 2 and d(u, p⁰ ) ≥ 4.
• iv) If v = p ⁰ ∈ Q¹ − Q0, then d(u, p⁰ ) ≥ 4 and d(u, Q1) ≥ 2.

The above discussion is in terms of Q, however the rest of the paper is in terms of P. For this reason now summarize the discussion in terms of two technical conditions on P.

Let P = {P1, . . . , Pk} be a covering of a graph P. For a given ι and two sets Q⁰ and Q¹ such that Q⁰ ∪ Q¹ = P^ι , let

\[\overline{Q} = \overline{P} \cup \{Q_0, Q_1\} - \{P_\iota\}.\]

We say (P, P , Q) satisfies

Condition A⁰⁰

• 1. if for each i 6= ι one of the following holds
  • (a) there is a p 6∈ Pⁱ satisfying d(Pⁱ , p) ≥ 3, or
  • (b) there is a j 6= ι satisfying d(Pⁱ , P^j ) ≥ 2, or
  • (c) there is an l = 0 or 1 such that d(Pⁱ , Ql) ≥ 2,
• 2. and if for all l = 0, 1 either
  • (a) there is a p 6∈ P^ι satisfying d(Q^l , p) ≥ 3, or
  • (b) there is a j 6= ι satisfying d(Q^l , P^j ) ≥ 2.

Condition B"

• 1. if for each \(p \in P_i\), \(i \neq \iota\) one of the following holds
  • (a) there is a \(j \neq \iota\) satisfying \(d(p, P_i) \geq 2\), or
  • (b) \(d(p, Q_0) > 2\) and \(d(p, Q_1) > 2\), or
  • (c) there is an l = 0 or 1 such that \(d(p, Q_l) \ge 3\), or
  • (d) there l=0 or 1 such that \(d(p,Q_l) \geq 2\) and a \(p' \in Q_l\) so that \(d(p,p') \geq 4\).
• 2. and if for each l = 0, 1 and each \(p \in Q_l\), either
  • (a) there is a \(j \neq \iota\) satisfying \(d(p, P_j) \geq 2\), or
  • (b) there exists \(p' \in P_l Q_l\) such that \(d(p, p') \ge 4\) and \(d(p, Q_{l'}) \ge 2\), where l' = 0 or 1 but \(l' \ne l\).

When there exists an \(\iota\), \(Q_0\) and \(Q_1\) such that \((P, \overline{P}, \overline{Q})\) satisfies condition A'' (resp. condition B''), we say \((P, \overline{P})\) or simply \(\overline{P}\) satisfies condition A'' (condition B''). Without loss of generality we may renumber \(\overline{P}\) so that \(\iota=1\). Note that A' and B' imply A'' and B'' by taking \(\iota=1\) and letting \(Q_0=P_1\) and \(Q_1=\emptyset\). However, condition A'' does not imply condition A. So let \(cov_{AA''B''}(P)\) be the smallest size of the covering \(\overline{P}\) of P satisfying conditions A, A'' and B''.

Similar to the discussion of conditions A' and B', the arguments used to determine conditions A" and B" from the graph \(\mathcal{G}(C,P,\overline{Q})\) are bi-directional. We summarize the discussion in the following proposition.

Proposition 4.6. For graphs C and P, and a triple \((P, \overline{P}, \overline{Q})\), \(G = \mathcal{G}'(C, P, \overline{Q})\) is a UCG if and only if \(\overline{P}\) satisfies condition A and \((P, \overline{P}, \overline{Q})\) satisfies conditions A'' and B''.

We are now ready to prove analogous results to Propositions 4.4 and 4.5.

Proposition 4.7. Assume \(A_{\text{ucg}}(C, P) = 2\kappa + 1\), and let H be a UCG with \(\langle \mathcal{Z}(H) \rangle = C\), \(\langle \mathcal{CP}(H) \rangle = P\), and \(|\mathcal{I}(H)| = 2\kappa + 1\) where \(\kappa = \text{cov}_A(P)\). Furthermore, assume \(|D_2| = \kappa + 1\). Then \(\text{cov}_{AA''B''}(P) = \kappa\).

Proof. Let H be a UCG with \(C = \langle \mathcal{Z}(H) \rangle\), \(P = \langle \mathcal{CP}(H) \rangle\), \(|\mathcal{I}(H)| = 2\kappa + 1\) and \(|D_2| = \kappa + 1\). Since \(|D_1| = \kappa\) and \(\kappa \leq |D_1''| \leq |D_1|\), it follows that \(|D_1| = |D_1''|\). We prove this proposition by studying the structure of a spanning subgraph.

Let \(D_1 = \{x_1, \dots, x_\kappa\}\) and \(\{\tilde{p}_1, \dots, \tilde{p}_\kappa\}\) be a set of vertices associated to the induced cover \(\overline{P}\). By Proposition 2.1 there exists an enumeration \(\{y_0, \dots, y_\kappa\}\) of \(D_2\) such that the vertex \(y_j\) is adjacent to \(x_j\) and \(\tilde{p}_j\) for each \(j, 1 \leq j \leq \kappa\). We may also assume \(y_0\) is adjacent to \(x_1\).

We now define a different cover of P. For each \(i, 0 \le i \le \kappa\), let

\[Q_i = \{ p \in V(P) : p \text{ is adjacent to } y_i \}.\]

Let \(P_1' = Q_0 \cup Q_1\) and \(P_i' = Q_i\) for \(2 \le i \le \kappa\), \(\overline{P}' = \{P_1', \dots, P_\kappa'\}\) and \(\overline{Q} = \{Q_0, \dots, Q_\kappa\}\). Since \(|D_1| = |D_1''|\) every vertex of C is adjacent to vertex in \(D_1\) by Lemma 2.4. Therefore,

G = G 0 (C, P, Q) is isomorphic to a spanning subgraph of H, and is a UCG by Lemma 2.5. By Proposition 4.6 P 0 satisfies conditions A, A⁰⁰ and B⁰⁰ which means

\[\kappa \le \operatorname{cov}_{AA''B''}(P) \le |\overline{P}'| = \kappa.\]

We conclude covAA00B⁰⁰(P) = κ.

Proposition 4.8. If P is a graph with r(P) > 1, κ = covA(P) 6= covA0B⁰(P) and covAA00B⁰⁰(P) = covA(P), then Aucg(C, P) = 2κ + 1.

Proof. Assume covA0B⁰(P) 6= κ but covAA00B⁰⁰(P) = κ. By Proposition 4.3 Aucg(C, P) > 2κ, so we need to show Aucg(C, P) ≤ 2κ + 1. Let P be a smallest covering of P with respect to condition A such that there is a refined cover Q where the pair (P , Q) is smallest with respect to conditions A⁰⁰ and B⁰⁰. Without loss of generality we may assume ι = 1. By Proposition 4.6 G = G(C, P, Q) is a UCG with C = hZ(G)i, P = hCP(G)i and |I(G)| = 2κ + 1, which implies Aucg(C, P) ≤ 2κ + 1.

The following theorem summarizes Propositions 4.1, 4.3, 4.4, 4.5, 4.7, and 4.8.

Theorem 4.1. If P is a graph with r(P) > 1 and covA(P) = κ, then following holds:

• 1. Aucg(C, P) = 2κ if and only if covA0B⁰(P) = κ.
• 2. Aucg(C, P) = 2κ + 1 if and only if κ 6= covA0B⁰(P) and either
  • (a) covA⁰(P) = κ or
  • (b) covAA00B⁰⁰(P) = κ.
• 3. Aucg(C, P) = 2κ + 2 otherwise.

5. Coverings

In this section we determine when κ = covA(P) is the size of smallest coverings with respect to the other conditions described in Sections 3 and 4. To do this we introduce one last set of notation. For a graph G, a vertex V in G and s ∈ N let

\[N_s[v] = \{x \in V(G) | d(v, x) \le s\}\]

be the closed s-neighborhood of v. When s = 1 we simply let N1[x] = N[x].

Proposition 3.1 and Theorem 3.1 determine Aucg(Kn, P) up to knowing when covA(P) = covAB(P). We now determine conditions for a graph P to satisfy covA(P) = covAB(P).

Proposition 5.1. If P is a graph with diam(P) ≥ 3, then covA(P) = 2.

Proof. Suppose x is a vertex in P satisfying e(x) ≥ 3. Let P¹ = N[x] and P² = V (P) − P1. Then d(x, P2) ≥ 2. Since e(x) ≥ 3, P² contains a vertex y satisfying d(x, y) ≥ 3, and so d(y, P1) ≥ 2. Thus, {P1, P2} is a covering of P satisfying condition A.

Proposition 5.2. If P is a graph satisfying diam(P) ≥ 4 and r(P) ≥ 3, then covAB(P) = 2.

Proof. Let x and y be vertices in P satisfying d(x, y) = 4. We construct P¹ and P² recursively. Initialize P¹ := N[x] and P² := N[y]. Note that d(x, N[y]) = d(y, N[x]) = 3. For a vertex z in V (P) − (P¹ ∪ P2), update P¹ and P² as follows.

• i) If there is a vertex p ∈ P² satisfying d(z, p) ≥ 3, then let P¹ := P¹ ∪ {z}.
• ii) Else if there is a vertex p ∈ P¹ satisfying d(z, p) ≥ 3, then let P² := P² ∪ {z}.
• iii) Else there is a vertex p ∈ V (P) − (P¹ ∪ P2) satisfying d(z, p) = 3, since r(P) = 3. Let P¹ := P¹ ∪ {z} and P² := P² ∪ {p}.

Continue until all vertices of P have been accounted for. By construction {P1, P2} is a covering of P satisfying condition B. Since N[x] ⊂ P1, d(x, P2) ≥ 2 and similarly d(y, P1) ≥ 2. Thus {P1, P2} satisfies condition A.

Proposition 5.3. If P is a graph with r(P) = 2, then covAB(P) 6= 2.

Proof. Suppose there is a covering {P1, P2} of P satisfying conditions A and B. Assume P¹ contains a vertex z with e(z) = 2. By condition B, d(z, P2) = 2 and so N(z)∩P² = ∅. If p is a vertex in P2, then d(z, p) = 2 and so d(P1, p) = 1, a contradiction to condition A.

Proposition 5.4. For every α ∈ N, there exists a graph P with r(P) = diam(P) = 2 and covA(P) = 2α.

Proof. Construct P ^α = (V α , E^α ) as follows. Let

\[V^{\alpha} = \{e_i, f_i : 1 \le i \le \alpha\}\]

and

\[E^{\alpha} = \{e_i e_j, f_i f_j, e_i f_j : 1 \le i, j \le \alpha, i \ne j\}.\]

Note, P α is a complete graph minus a perfect matching. It follows that r(P α ) = diam(P α ) = 2. We now show covA(P α ) = 2α. By Lemma 3.1 there exists a covering

\[\{P_1^{\alpha}, P_2^{\alpha}, \dots, P_k^{\alpha}\}\]

of P α satisfying condition A. Suppose e¹ ∈ P α 1 . If P α 1 contains a vertex other than e1, then d(P α 1 , x) = 1 for all x ∈ V ^α−P α 1 , a contradiction to condition A. Therefore P α ¹ = {e1}. Similarly |P α i | = 1 for all i = 1, 2, . . . , k and covA(P α ) = 2α.

Propositions 5.1 through 5.3 determine when covA(P) = covAB(P) for all graphs P with r(P) > 1 except those with r(P) = diam(P) = 2 and those with r(P) = diam(P) = 3. Proposition 5.4 gives insight into richness of the case r(P) = diam(P) = 2. However, we do not have any definitive results for r(P) = diam(P) = 3. This is discussed further in Section 6.

For a non-complete graph C, Theorem 4.1 relates Aucg(C, P) to covA0B⁰(P), covA⁰(P), and covAA00B⁰⁰(P). Because of Proposition 5.4, we only consider P with diam(P) > 2. By Proposition 5.1 we need to understand when the smallest coverings are of size 2.

Proposition 5.5. P is a graph with covA0B⁰(P) = 2 if and only if P is disconnected.

Proof. Assume P is disconnected. Let P¹ be the vertices of a connected component of P and let P² = V (P) − P1. Since, for all u ∈ P¹ and v ∈ P2, d(u, v) = ∞ it follows that {P1, P2} satisfies conditions A⁰ and B⁰ .

Next, assume P is connected but P = {P1, P2} is a covering. Since P is connected, d(P1, P2) = 1 and there is a p¹ ∈ P¹ and p² ∈ P² with d(p1, p2) = 1. Therefore d(p1, P2) = 1 and d(p2, P1) = 1 and condition B⁰ fails, and so covA0B⁰(P) > 2.

Proposition 5.6. For a graph P, covA⁰(P) = 2 if and only if diam(P) ≥ 5.

Proof. Assume diam(P) ≥ 5. Then there exist u, v ∈ V (P) with d(u, v) ≥ 5. Let P¹ = {p ∈ V (P) : d(u, p) ≤ 2} and P² = V (P) − P1. Then d(u, P2) ≥ 3. Also d(v, P1) ≥ 3 because if there is a p ∈ P¹ with d(v, p) ≤ 2, then d(u, v) ≤ d(u, p) + d(p, v) ≤ 4, a contradiction. So {P1, P2} satisfies condition A⁰ .

Next, assume there is a covering {P1, P2} of P satisfying condition A⁰ . Then there is a u ∈ P¹ such that d(u, P2) ≥ 3. Then N2[u] ⊂ P¹ and N2[u] ∩ P² = ∅. Similarly, P² contains a vertex v such that d(v, P1) ≥ 3, and so N2[v] ⊂ P¹ and N2[v] ∩ P¹ = ∅. Therefore d(u, v) ≥ 5.

Proposition 5.7. If P is a graph with diam(P) ≤ 3, then covAA00B⁰⁰(P) 6= 2.

Proof. Let P be a graph with diam(P) ≤ 3. Suppose there is a covering P = {P1, P2} of P satisfying condition A such that for ι = 1 the triple (P, P , Q) satisfies conditions A⁰⁰ and B⁰⁰ , where Q = {Q0, Q1, P2} with P¹ = Q⁰ ∪ Q1. For each p ∈ P1, d(p, P2) ≥ 2 by condition B⁰⁰(2) because diam(P) ≤ 3. This implies d(P1, P2) ≥ 2. However, d(P1, P2) ≤ 1 since P is connected, a contradiction.

Proposition 5.8. If P is a graph with r(P) = 2, then covAA00B⁰⁰(P) 6= 2.

Proof. Let P be a graph with r(P) = 2. Suppose there is a covering P = {P1, P2} of P satisfying condition A such that for ι = 1 the triple (P, P , Q) satisfies conditions A⁰⁰ and B⁰⁰, where Q = {Q0, Q1, P2} with P¹ = Q⁰ ∪ Q1.

For a central vertex c ∈ V (P) either c ∈ P¹ or c ∈ P2.

Suppose c ∈ P1. Without loss of generality assume c ∈ Q0. By condition B⁰⁰(2), d(c, P2) ≥ 2. In fact, d(c, P2) = 2 because c is central, and so there exists a p ∈ P² with d(c, p) = 2. Let c−x−p be a geodesic. Then x ∈ P1, e(x) ≤ 3 and d(x, P2) = 1. Therefore, {P1, P2} does not satisfy condition B⁰⁰-2 for x, a contradiction.

Next, suppose c ∈ P2. By the hypotheses c does not satisfy B⁰⁰(1a), B⁰⁰(1c), and B⁰⁰(1d). Therefore, d(c, Q0) ≥ 2 and d(c, Q1) ≥ 2. Since c is a central vertex, d(c, Q0) = 2 and d(c, Q1) = 2. Then there exist q⁰ ∈ Q⁰ and q¹ ∈ Q1, satisfying d(c, q0) = 2 and d(c, q1) = 2. Let c − x − q⁰ and c − y − q¹ be paths. Then both x and y are in P² and d(P2, Qi) ≤ 1 for i = 0, 1. Therefore {P1, P2} does not satisfy condition A⁰⁰(1).

To fully understand Aucg(C, P) there are still two cases left to consider, when diam(P) = 4 and r(P) = 3, and diam(P) = 4 and r(P) = 4. In these cases covA0B⁰(P) 6= 2 and covA⁰(P) 6= 2. When diam(P) = r(P) = 4, covAA00B⁰⁰(P) = 2 depends on P. To show that there exist graphs P with covAA00B⁰⁰(P) 6= 2, we introduce the following lemma.

Lemma 5.1. If P is a graph with diam(P) = 4 and covAA00B⁰⁰(P) = 2, then there exist three vertices x1, x2, x³ such that

\[N_2[x_1] \cap N_2[x_2] \cap N_2[x_3] = \emptyset.\]

Proof. Suppose there is a covering P = {P1, P2} of P satisfying condition A such that for ι = 1 the triple (P, P , Q) satisfies conditions A⁰⁰ and B⁰⁰, where Q = {Q0, Q1, P2} with P¹ = Q⁰ ∪ Q1.

Since P is connected, without loss of generality we may assume that d(P2, Q1) ≤ 1. Then A ⁰⁰(2b) is not satisfied for l = 1 and so, from A⁰⁰(2a), there exists a p¹ ∈ P² such that d(Q1, p1) ≥ 3. For l = 0 there are two cases for condition A⁰⁰(2), either part 2a is met or part 2b is met.

For l = 0, either there exists a p⁰ ∈ P² such that d(Q0, p0) ≥ 3 or d(P2, Q0) ≥ 2 by condition A ⁰⁰(2b).

Suppose d(P2, Q0) ≥ 2, by connectivity of P we know d(P2, Q1) ≤ 1 and d(Q0, Q1) ≤ 1. Since d(p1, Q1) ≥ 3, N2[p1] ∩ Q¹ = ∅ and so

\[N_2[p_2] \subset (P_2 \cup Q_0) - Q_1.\]

Since p¹ ∈ P² and d(Q0, P2) ≥ 2, N1[p1] ∩ Q⁰ = ∅ and N1[p1] ⊂ P2. From

\[2 \le d(Q_0, P_2) \le d(Q_0, N_1[p_1]),\]

it follows that N2[p1] ⊂ P2. Therefore, d(N2[p1], Q0) ≥ 2 and d(p1, Q0) ≥ 4. Since diam(P) = 4, d(p1, Q0) = 4.

Let p¹ − x − y − z − q⁰ be a geodesic for some q⁰ ∈ Q0. Then z 6∈ Q⁰ since d(z, p1) = 3, and z 6∈ P² since d(q0, z) = 1. Hence z ∈ Q1. Furthermore, y ∈ N2[p1] ⊂ P2, so d(z, P2) ≤ 1 and d(z, Q0) ≤ 1. This implies condition B⁰⁰(2) is not met for z ∈ Q1, a contradiction. Therefore d(P2, Q0) ≤ 1.

Then, for l = 0 condition A⁰⁰(2a) is satisfied and there is a p⁰ ∈ P² such that d(Q0, p0) ≥ 3. Therefore, N2[p0] ∩ Q⁰ = ∅. Since N2[p1] ∩ Q¹ = ∅, it follows that N2[p0] ∩ N2[p1] ⊂ P2.

From condition A⁰⁰(1) there exists a q ∈ Q⁰ such that d(q, P2) ≥ 3. Then N2[q] ∩ P² = ∅ and

\[N_2[p_0] \cap N_2[p_1] \cap N_2[q] = \emptyset.\]

Proposition 5.9. There exists a graph P with r(P) = diam(P) = 4 and covAA00B⁰⁰(P) 6= 2.

Proof. Let P be the graph of a hexagonal prism as in Figure 4. Then r(P) = diam(P) = 4. If covAA00B⁰⁰(P) = 2 then by Lemma 5.1 there exist vertices x1, x2, x³ such that

\[N_2[x_1] \cap N_2[x_2] \cap N_2[x_3] = \emptyset,\]

or equivalently,

\[N_2[x_1]^c \cup N_2[x_2]^c \cup N_2[x_3]^c = V(P).\]

For any vertex x of P, the complement of \(N_2[x]\) is a star with three pendant vertices as in Figure 4. Because the prism has twelve vertices, a set of three stars would cover the prism with no overlap. However, one can check this is not possible and so \(cov_{AA''B''}(P) \neq 2\)

Figure 4: A hexagonal prism and the complement of a 2-neighborhood.

Proposition 5.10. There exists a graph P with \(r(P) = \operatorname{diam}(P) = 4\) and \(\operatorname{cov}_{AA''B''}(P) = 2\).

Proof. Let P be the graph of a heptagonal prism as in Figure 5. Then r(P) = diam(P) = 4. Consider the covering \(\overline{P} = \{P_1, P_2\}\), where \(P_1 = Q_0 \cup Q_1\) as in Figure 5. Here vertices of \(Q_0\) are represented by the open circles, \(Q_1\) by the open squares, and \(P_2\) by the filled circles. One can verify this covering satisfies conditions A, A" and B", and so \(\text{cov}_{AA''B''}(P) = 2\).

Figure 5: A graph P with \(r(P) = \operatorname{diam}(P) = 4\) and \(\operatorname{cov}_{AA''B''}(P) = 2\)

6. Appendage Numbers

In this section we determine \(A_{\text{ucg}}(C, P)\) for most pairs of graphs (C, P) based on the structure of C, proving Theorems 6.1, 6.2, and 6.3, given in the introduction. Conjectures are also given for the two remaining cases.

Theorem 6.1. Let \(C = \{v\}\) and P be any graph with \(r(P) \geq 2\). Then \(A_{ucg}(C, P) = 0\).

Proof. Let H be the graph with vertex set

\[V(H) = V(P) \cup \{v\}\]

and edge set

\[E(H) = E(P) \cup \{vp | p \in V(P)\}.\]

We claim H is a UCG with hZ(H)i = C, hCP(H)i = P and |I(H)| = 0.

Since v is adjacent to all other vertices in H, e(v) = 1. If p is a vertex in P there is a p ⁰ ∈ V (P) satisfying d^P (p, p⁰ ) = 2. Since p and p 0 are not adjacent in P, they are not adjacent in H and e(p) ≥ 2. This implies hZ(H)i = {v} and H is a UCG with hCP(H)i = P.

Theorem 6.2. When n ≥ 2

\[A_{\text{ucg}}(K_n, P) = \begin{cases} 2 & \text{if } \operatorname{diam}(P) \ge 4 \text{ and } r(P) \ge 3\\ 3 & \text{if } \operatorname{diam}(P) \ge 3 \text{ and } r(P) = 2 \end{cases}\]

Furthermore, for all t ∈ N there is a graph P with diam(P) = r(P) = 2 and Aucg(Kn, P) ≥ t.

Proof. This follows directly from Proposition 3.1, Theorem 3.1 and Propositions 5.1, 5.2, 5.3, and 5.4.

Conjecture 1. If diam(P) = r(P) = 3, then Aucg(Kn, P) = 2.

When diam(P) = r(P) = 3, Aucg(C, P) = 2 or 3. However, all our examples show Aucg(Kn, P) = 2, but we have not been able to prove this is always true.

Theorem 6.3. If C is a graph with diam(C) > 1 then

\[A_{\mathrm{ucg}}(C,P) = \begin{cases} 4 & \textit{if} \operatorname{diam}(P) = \infty \\ 5 & \textit{if} \ 5 \leq \operatorname{diam}(P) < \infty \\ 5 \textit{ or} \ 6 & \textit{if} \ \operatorname{diam}(P) = 4 \textit{ and } r(P) = 4 \\ 6 & \textit{if} \ \operatorname{diam}(P) = 4 \textit{ and } r(P) = 2 \\ 6 & \textit{if} \ \operatorname{diam}(P) = 3 \end{cases}\]

Furthermore, for all t ∈ Z there is a graph P with diam(P) = r(P) = 2 and Aucg(C, P) ≥ t.

Proof. This follows directly from Theorem 4.1, Proposition 5.1 and Propositions 5.4, through 5.10.

The only case not accounted for is when diam(P) = 4 and r(P) = 3. In this case we know covA0B⁰(P) 6= 2, so Aucg(C, P) = 5 or 6. We also know covA⁰(P) 6= 2. Therefore Aucg(C, P) = 5 if and only if covAA00B⁰⁰(P) = 2. However, we have not found this to be the case for any such P. We also have been unable to show it is impossible, so we are left with the following conjecture.

Conjecture 2. If C is a graph with diam(C) > 1 and P is a graph with diam(P) = 4 and r(P) = 3, then Aucg(C, P) = 6.

The diam(P) = r(P) = 4 case also warrants further discussion. Propositions 5.9 and 5.10 show there are examples of P when \(A_{\rm ucg}(C,P) = 6\) and with \(A_{\rm ucg}(C,P) = 5\). It will be necessary to find another metric invariant other than diameter and radius to refine the results of this case. At this point we are unsure what a suitable invariant may be.

Finally, independent of C, there is a major difference between possible appendage numbers when \(\operatorname{diam}(P) > 2\) and when \(\operatorname{diam}(P) = 2\). When \(\operatorname{diam}(P) > 2\), Theorems 6.2 and 6.3 show there are only finitely many possible appendage numbers, and which are independent of the size of V(P). On the other hand, for \(\operatorname{diam}(P) = r(P) = 2\) the graph \(P^{\alpha}\) in Proposition 5.4 gives

\[A_{\text{ucg}}(K_n, P^{\alpha}) = |V(P^{\alpha})| = 2\alpha.\]

This may suggest that appendage numbers are related to |V(P)| when diam(P) = r(P) = 2, however the following proposition shows this is not the case.

Proposition 6.1. For every \(\alpha, \beta \in \mathbb{N}\), there is a graph P such that \(V(P) = 2\alpha + \beta\) and \(A_{\text{ucg}}(K_n, P) = 2\alpha\).

Proof. In this proof we modify the construction of \(P^{\alpha}\) from Proposition 5.4. For \(\alpha, \beta \in \mathbb{N}\) define \(P^{\alpha,\beta} = (V^{\alpha,\beta}, E^{\alpha,\beta})\) as follows. Let

\[V^{\alpha,\beta} = \{e_i, f_i, g_j : 1 \le i \le \alpha, 1 \le j \le \beta\}\]

and

\[E^{\alpha,\beta} = \{e_i e_j, f_i f_j, e_i f_j, e_k g_l, f_k g_l : 1 \le i, j \le \alpha, i \ne j, 2 \le k \le \alpha, 1 \le l \le \beta\}.\]

That is, \(P^{\alpha,\beta}\) is the graph from Proposition 5.4 with \(\beta\) new vertices, \(g_i's\), that are adjacent to every vertex except themselves, \(e_1\) and \(f_1\). Observe that \(\operatorname{diam}(P^{\alpha,\beta}) = r(P^{\alpha,\beta}) = 2\) if \(\alpha \geq 2\).

We now show \(\operatorname{cov}_A(P^{\alpha,\beta}) = \operatorname{cov}_{AB}(P^{\alpha,\beta}) = 2\alpha\). Let \(\overline{P^{\alpha,\beta}} = \{P_1,\ldots,P_k\}\) be a covering of \(P^{\alpha,\beta}\) satisfying condition A. For \(2 \le i \le \alpha\), \(\{e_i\}\), \(\{f_i\} \in \overline{P^{\alpha,\beta}}\) as in Proposition 5.4. If

\[\{e_1, f_1, g_1, \dots, g_\beta\} \in \overline{P^{\alpha,\beta}},\]

then \(\overline{P^{\alpha,\beta}}\) fails to satisfy condition A. Therefore \(e_1\), \(f_1\) and the \(g_l\)s must be contained in least two elements of \(\overline{P^{\alpha,\beta}}\), and so \(\text{cov}_A(P^{\alpha,\beta}) \geq 2\alpha\).

Let \(P_1^{\alpha,\beta}=\{e_1\}\) and \(Q_1^{\alpha,\beta}=\{f_1,g_1\ldots,g_\beta\}\), and for \(2\leq i\leq \alpha\) let \(P_i^{\alpha,\beta}=\{e_i\}\) and \(Q_i^{\alpha,\beta}=\{f_i\}\). Then \(\{P_1^{\alpha,\beta},Q_1^{\alpha,\beta},\ldots,P_{\alpha}^{\alpha,\beta},Q_{\alpha}^{\alpha,\beta}\}\) is a covering of \(P^{\alpha,\beta}\) that satisfies both conditions A and B. So \(A_{\text{ucg}}(K_n,P^{\alpha,\beta})=2\alpha\) and \(V(P^{\alpha,\beta})=2\alpha+\beta\).

7. Other Appendage Numbers

In the paper [4] Gu defines \(A_{\rm ucg}(C)\) to be the minimum number of vertices needed to be added to C in order to create a uniform central graph G with \(\langle \mathcal{Z}(G) \rangle = C\). To match notation we let \(A_{\rm ucg}(C,-) = A_{\rm ucg}(C)\). Gu's main theorem is the following.

Theorem 7.1 (Gu). If C is a connected graph, then

\[A_{\text{ucg}}(C, -) = \begin{cases} 2 & \text{if } C = \{v\} \\ 4 & \text{if } C = K_n, n \ge 2 \\ 6 & \text{otherwise} \end{cases}.\]

We use our results to give an alternative proof of Gu's result which is also true without the condition that C is connected.

Proof. Observe that Aucg(C, −) = min{Aucg(C, P) + |V (P)|} where the minimum is taken over all graphs P. By Proposition 2.2, r(P) > 1 and so we may assume |V (P)| ≥ 2. Since covA(P) ≥ 2 for any P, by Proposition 3.1 Aucg(Kn, P) ≥ 2 for n ≥ 2, and by Proposition 4.1 Aucg(C, P) ≥ 4 for any non-complete graph C. Hence Aucg(Kn, −) ≥ 4 and Aucg(C, −) ≥ 6.

Let P ² be a graph with two isolated vertices {u, v} and P² = {{u}, {v}} a covering. Note P² satisfies conditions A, B, A⁰ and B⁰ . Let

\[G_1 = \mathcal{G}(K_n, P^2, \overline{P^2}, 1) - \{x_{0,1}\}\]

and

\[G_2 = \mathcal{G}(K_n, P^2, \overline{P_2}, 2) - \{x_{0,1}, x_{0,2}\}.\]

The graph G¹ is the UCG in the first half of the proof of Theorem 3.1 and G² is a UCG by Proposition 4.2. Furthermore, |I(G1)| = 2 and |I(G1)| = 4, so Aucg(Kn, −) = 4 and Aucg(C, −) = 6. Finally, Aucg({v}, −) = 2 by Theorem 6.1.

We can also consider Aucg(−, P), the minimum number of vertices needed to be added to P in order to construct a uniform central graph G with hCP(G)i = P. From Propositions 2.2 and 6.1, it follows that Aucg(−, P) = ∞ if r(P) = 1, and Aucg(−, P) = 1 otherwise.

References

• [1] F. Buckley, Z. Miller, and P. Slater, On graphs containing a given graph as center, J. Graph Theory 5 (1981), 427–434.
• [2] S.-y. Choi, P. Guan, Construction of a family of uniform central graphs, Congr. Numer. 173 (2005) 75–78.
• [3] S.-y. Choi and N. Manickam, Uniform central graphs, Congr. Numer. 130 (1998), 89–94.
• [4] W. Gu, On central appendage number of a uniform central graph, Congr. Numer. 159 (2002) 69-75.
• [5] S. Klavzar, K. Narayankar, and S. Lokesh, Constructing uniform central graphs and embed- ˇ ding into them, Indian J. Pure Appl. Math. 50 (2019) 451-460.
• [6] D. West, Introduction to Graph Theory, 2nd edition, Upper Saddle River, NJ, Prentice Hall (2001).