Hafizh M. Radiapradana^a , Suhadi Wido Saputro^a , Erma Suwastika^a , Oki Neswan^a , Andrea Semanicov ˇ a-Fe ´ nov ˇ cˇ´ıkova´ b

Faculty of Mathematics and Natural Sciences, Institut Teknologi Bandung,

Jalan Ganesa 10 Bandung, Indonesia

Technical University, Letna 9, Ko ´ sice, Slovakia ˇ

hafizhmcdc@gmail.com, {suhadi, ermasuwastika, oneswan}@math.itb.ac.id, andrea.fenovcikova@tuke.sk

For integer k ≥ 2, let X = {0, 1, 2, . . . , k}. In this paper, we determine the order of a star graph K1,n of n + 1 vertices, such that K1,n admits a topological integer additive set-labeling (TIASL) with respect to a set X. We also give a condition for a star graph K1,n such that K1,n is not a TIASL-graph on set X.

Keywords: set-labeling, set topology, star graph, sumset, topological integer additive set-labeling

Mathematics Subject Classification : 05C78

DOI: 10.5614/ejgta.2018.6.2.13

1. Introduction

Research on graph labeling was started after Rosa introduced the concept of β-valuation of graphs [2]. The concept of set-assignment [1], which is defined as follows, is analogous to the number valuations of graphs. Let G(V, E) be a graph, X be a non-empty set, and P(X) be the power set of X. Then the set-valued function f : V (G) → P(X) is called the set-assignment of vertices of G. We can also define a set-assignment of edges or both elements (vertices and edges)

Received: 31 August 2017, Revised: 28 June 2018, Accepted: 14 September 2018.

^aDepartment of Mathematics,

^bDepartment of Applied Mathematics and Informatics,

in a similar way. A set-assignment of a graph G is called a set-labeling (or a set-valuation) of G if it is injective.

In this paper, we combine the concept of the vertex set-labeling and the set topology. A topology on a non-empty set X is a collection T of subsets of X having the following properties:

• 1. The set X and ∅ are in T .
• 2. The union of the elements of any sub-collection of T is in T .
• 3. The intersection of the elements of any finite sub-collection of T is in T .

Let G be a connected, simple, and finite graph. Let X be a finite non-empty set of non-negative integers. A vertex set-labeling f : V (G) → P(X) − {∅} is called a topological integer additive set-labeling (TIASL) of G if f is an injective function, {f(V (G)) ∪ {∅}} is a topology of X, and there exists the corresponding function f ⁺ : E(G) → P(X) − {∅} such that for every edge uv ∈ E(G), f ⁺(uv) = f(u) + f(v). We recall that the sumset (or Minkowski sum [4]) of two non-empty sets A and B, denoted by A + B, is defined by A + B = {a + b | a ∈ A; b ∈ B}. A graph G which admits TIASL is called a topological integer additive set-labelled graph (in short, TIASL-graph).

The topological integer additive set-labeling was introduced by Sudev and Germina [3]. They give a tight condition for a TIASL-graph. They proved that G is a TIASL-graph if and only if G has at least one pendant vertex. They also characterized all TIASL-graphs with respect to either the indiscrete topology or Sierpenski's topology.

Let G be a graph having a pendant vertex. For integer k ≥ 2, let X = {0, 1, 2, . . . , k}. It seems that every graph G admits a topological integer additive set-labeling on set X if the cardinality of X is big enough. In [3], Sudev and Germina proved that an (n, m)-tadpole graph is a TIASLgraph. An (n, m)-tadpole graph is a graph obtained from one copies of cycle Cn, n ≥ 3, and path Pm, m ≥ 2, by identifying an end point of the path P^m to a vertex of cycle Cn. They have shown that an (n, m)-tadpole graph of n + m − 1 vertices admits a topological integer additive set-labeling on set X = {0, 1, 2, . . . , k} where k = 2(m + n) − 5.

In this paper, we consider a star graph K1,n of n+1 vertices and a given set X = {0, 1, 2, . . . , k} where k ≥ 2. We obtain two main results. The first result is related to the order of a star graph K1,n such that K1,n is a TIASL-graph on the set X.

Theorem 1.1. Let K1,n be a star graph with n + 1 vertices. For k ≥ 2, let X = {0, 1, 2, . . . , k}. If n is one of the positive integers below, then K1,n is a TIASL-graph on set X.

(a) n ∈ {1, 2, . . . , 4k − 4}, or

(b) \[n = 2^{r_1} + r_2 - 2\] for \(r_1 \in \{2, 3, \dots, k-1\}\) and \(r_2 \in \{1, 2\}\).

In the second result, we give a condition for a star graph K1,n such that K1,n is not a TIASLgraph on set X.

Theorem 1.2. Let K1,n be a star graph with n + 1 vertices. For k ≥ 2, let X = {0, 1, 2, . . . , k}. If 3 · 2 ^k−¹ − 2 ≤ n ≤ 2 ^k+1 − 2, then K1,n is not a TIASL-graph on set X.

In order to prove both theorems above, we also consider the following useful proposition.

Proposition 1.1. Let S be a finite non-empty set of non-negative integers with s elements. Then P(S) is a topology of S with 2 s elements.

2. Proof of Theorem 1.1

For an integer \(k \ge 2\), let \(X = \{0, 1, 2, \dots, k\}\). First we must consider the following proposition which has been proved by Sudev and Germina [3].

Proposition 2.1. Let \(f:V(G)\to \mathcal{X}-\{\emptyset\}\) is a TIASL of a graph G. Then, the vertices whose set-labels containing the maximal element of the ground set X are pendant vertices which are adjacent to the vertex having the set-label \(\{0\}\).

From Proposition 2.1, if f is a TIASL of a graph G, then there exists a vertex v of G such that \(f(v) = \{0\}\). Therefore, we must construct a topology of X containing \(\{0\}\).

Proposition 2.2. There exists a topology \(\mathcal{T}\) containing \(\{0\}\) on set X such that \(|\mathcal{T}| = t\), where t is one of the positive integers as follows.

(a) \[3 \le t \le 4k - 2\], or

(b) \[t = 2^{r_1} + r_2\] for \(r_1 \in \{2, 3, \dots, k-1\}\) and \(r_2 \in \{1, 2\}\).

Proof. We distinguish two cases.

Part 2.2.1. 3 < t < 4k - 2

Let \(I_0 = X\). For \(i \in \{1, 2, ..., k\}\), we define recursively

\[I_i = I_{i-1} - \max(I_{i-1})\]

and

\[\mathcal{I}_i = \{I_k\} \cup \{I_s \mid 0 \le s \le i - 1\}.\]

Note that \(|\mathcal{I}_i| = i + 1\). We also define \(I_i^* = I_{k-i} - \{0\}\) and \(\mathcal{I}_i^* = \{I_s^* \mid 1 \le s \le i\}\). In this case, \(|\mathcal{I}_{i}^{*}| = i\). For \(j \in \{1, 2, \dots, k-2\}\), we define

\[\widehat{I}_j = I_{j+2} \cup \{k-1\}\]

and

\[\widehat{I}_j^* = \widehat{I}_j - \{0\}.\]

We also define

\[\mathcal{I}_j^{**} = \widehat{\mathcal{I}}_j \cup \widehat{\mathcal{I}}_j^*,\]

where \(\widehat{\mathcal{I}}_j = \{\widehat{I}_s \mid 1 \leq s \leq j\}\) and \(\widehat{\mathcal{I}}_j^* = \{\widehat{I}_s^* \mid 1 \leq s \leq j\}\). Note that \(|\mathcal{I}_j^{**}| = 2j\). By some definitions above, we define a collection-set \(\mathcal{T}_1\) with t elements as follows.

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

Note that \(I_k = \{0\} \in \mathcal{T}_1\). Now, we will show that \(\mathcal{T}_1\) is a topology of X.

Let A and B be two distinct elements of \(\mathcal{T}_1\) where \(|A| \leq |B|\). If \(A \subset B\), then \(A \cap B = A \in \mathcal{T}_1\)and \(A \cup B = B \in \mathcal{T}_1\). Otherwise, we distinguish six cases.

• 1. \(A \in \mathcal{I}_k\) and \(B \in \mathcal{I}_i^*\) for \(i \in \{1, 2, \dots, k\}\) (or \(B \in \mathcal{I}_k\) and \(A \in \mathcal{I}_i^*\)) Then \(A \cap B \in \mathcal{I}_i^*\) and \(A \cup B \in \mathcal{I}_k\).
• 2. \(A \in \mathcal{I}_k\) and \(B \in \widehat{\mathcal{I}}_j\) for \(j \in \{1, 2, \dots, k-2\}\) (or \(B \in \mathcal{I}_k\) and \(A \in \widehat{\mathcal{I}}_j\)) Then \(A \cap B \in \mathcal{I}_k\) and either \(A \cup B \in \mathcal{I}_k\) or \(A \cup B \in \widehat{\mathcal{I}}_j\).
• 3. \(A \in \mathcal{I}_k\) and \(B \in \widehat{\mathcal{I}}_j^*\) for \(j \in \{1, 2, \dots, k-2\}\) (or \(B \in \mathcal{I}_k\) and \(A \in \widehat{\mathcal{I}}_j^*\)) Then \(A \cap B \in \mathcal{I}_k^*\) and either \(A \cup B \in \widehat{\mathcal{I}}_j\) or \(A \cup B \in \mathcal{I}_k\).
• 4. \(A \in \mathcal{I}_i^*\) and \(B \in \widehat{\mathcal{I}}_j\) for \(i \in \{k-1, k\}\) and \(j \in \{1, 2, \dots, k-2\}\) (or \(B \in \mathcal{I}_i^*\) and \(A \in \widehat{\mathcal{I}}_j\)) Then either \(A \cap B = \emptyset\) or \(A \cap B \in \mathcal{I}_i^*\) or \(A \cap B \in \widehat{\mathcal{I}}_j^*\). Also, we have either \(A \cup B \in \widehat{\mathcal{I}}_j\) or \(A \cup B \in \mathcal{I}_k\).
• 5. \(A \in \mathcal{I}_i^*\) and \(B \in \widehat{\mathcal{I}}_j^*\) for \(i \in \{k-1, k\}\) and \(j \in \{1, 2, \dots, k-2\}\) (or \(B \in \mathcal{I}_i^*\) and \(A \in \widehat{\mathcal{I}}_j^*\)) Then either \(A \cap B \in \mathcal{I}_k\) or \(A \cap B = \emptyset\). Also, we have either \(A \cup B \in \mathcal{I}_i^*\) or \(A \cup B \in \widehat{\mathcal{I}}_j^*\).
• 6. \(A \in \widehat{\mathcal{I}}_j\) and \(B \in \widehat{\mathcal{I}}_j^*\) for \(j \in \{1, 2, \dots, k-2\}\) (or \(B \in \widehat{\mathcal{I}}_j\) and \(A \in \widehat{\mathcal{I}}_j^*\)) Then \(A \cap B \in \widehat{\mathcal{I}}_j^*\) and \(A \cup B \in \widehat{\mathcal{I}}_j\).

From the six cases above, we obtain that every two distinct elements A and B in \(\mathcal{T}_1\) satisfy \(A \cap B \in \mathcal{T}_1\) and \(A \cup B \in \mathcal{T}_1\). Since \(\mathcal{T}_1\) also contains \(\emptyset\) and X, it implies that \(\mathcal{T}_1\) is a topology of X.

Part 2.2.2. \[t = 2^{r_1} + r_2\] for \(r_1 \in \{2, 3, \dots, k-1\}\) and \(r_2 \in \{1, 2\}\)

We define the sets \(J_{r_1} = \{0, 1, \dots, r_1\}\). Now, we consider an element a of X such that \(a \neq \max(X)\). Let \(X^- = X - \{a\}\). By these definitions, we define a collection-set \(\mathcal{T}_2\) with t elements as follows.

\[\mathcal{T}_2 = \begin{cases} \mathcal{P}(J_{r_1}) \cup \{X\}, & \text{if } t = 2^{r_1} + 1, \\ \mathcal{P}(J_{r_1}) \cup \{\{X\}, \{X^-\}\}, & \text{if } t = 2^{r_1} + 2. \end{cases}\]

Now, we will show that \(\mathcal{T}_2\) is a topology of X.

Note that \(\emptyset\), \(\{0\}\), \(X \in \mathcal{T}_2\). Let A and B be two distinct elements of \(\mathcal{T}_2\). We distinguish three cases.

• 1. \(A, B \in \mathcal{P}(J_{r_1})\)By Proposition 1.1, then \(A \cap B \in \mathcal{P}(J_{r_1})\) and \(A \cup B \in \mathcal{P}(J_{r_1})\).
• 2. \(A \in \mathcal{P}(J_{r_1})\) or \(A = X^-\), and B = XThen \(A \cup B = B\) and \(A \cap B = A\).
• 3. \(A \in \mathcal{P}(J_{r_1})\) and \(B = X^-\). Then \(A \cap B \in \mathcal{P}(J_{r_1})\) and \(A \cup B \in \{X, X^-\}\).

From three cases above, we obtain that \(A \cap B\), \(A \cup B \in \mathcal{T}_2\).

Now, we are ready to prove Theorem 1.1.

Proof of Theorem 1.1. Let \(V(K_{1,n}) = \{v_1, v_2, \dots, v_{n+1}\}\), where \(v_1\) is the centre of \(K_{1,n}\). Let \(\mathcal{T}_t\) be a topology of X with t elements satisfying Proposition 2.2. Let \(\mathcal{T}_t' = \mathcal{T}_t - \{\emptyset\}\). Now, we define a vertex injective labeling \(f: V(S_n) \to \mathcal{T}_t'\) such that \(f(v_1) = \{0\}\). Since for \(2 \le i \le n\), \(v_1\) is adjacent to \(v_i\) and \(f(v_1) + f(v_i) = f(v_i) \in \mathcal{T}_t' \subseteq \mathcal{P}(X)\), we obtain that \(K_{1,n}\) is a TIASL-graph on the set X.

3. Proof of Theorem 1.2

Let S be a finite non-empty set of non-negative integers. From Proposition 1.1, it is clear that \(\mathcal{P}(S)\) is a topology on the set S. Let \(\mathcal{A} \subset \mathcal{P}(S)\). On some cases of \(\mathcal{A}\), the collection \(\mathcal{P}(S) - \mathcal{A}\) is not a topology on the set S. In proposition below, we prove that if \(L \in \mathcal{P}(S)\) is not an element of a topology \(\mathcal{T}\) on the set S, then there exists an element \(I \in \mathcal{L}\) such that \(I \in \mathcal{T}\).

Proposition 3.1. Let S be a finite non-empty set of non-negative integers with s elements, and \(\mathcal{T}\) be a topology of S. Let \(A \in \mathcal{P}(S)\) but \(A \notin \mathcal{T}\). Then there exists an element a of A such that \(\{a\} \notin \mathcal{T}\).

Proof. By the definition of a topology, we have \(A \neq \emptyset\). Let \(A = \{a_1, a_2, \dots, a_r\}\). If r = 1, then we are done. Now, we assume that \(r \geq 2\). Suppose that \(\{a_i\} \in \mathcal{T}\) for \(1 \leq i \leq r\). Note that \(\bigcup_{i=1}^r \{a_i\} = A \notin \mathcal{T}\), a contradiction.

Let the collection \(\mathcal{T}\) be a topology on the set S which is satisfying Proposition 3.1 above and the set \(L \in \mathcal{P}(S)\) but \(L \notin \mathcal{T}\). Let \(l \in L\) and \(\{l\} \notin \mathcal{T}\). So, there are no two distinct sets \(A_1\) and \(A_2\) in \(\mathcal{T}\) such that \(A_1 \cap A_2 = \{l\}\). Therefore, we need to determine how many elements of \(\mathcal{T}\) such that \(\mathcal{T}\) may be a topology on the set S.

Proposition 3.2. Let S be a finite non-empty set of non-negative integers with \(s \geq 2\) elements. Let A be a non-empty collection-set, where every element of A is an element of P(S). If P(S) - A is a topology of S, then \(|P(S) - A| \leq 3 \cdot 2^{s-2}\).

Proof. Let \(S = \{v_1, v_2, \dots, v_s\}\). By Proposition 1.1, \(\mathcal{P}(S)\) is a topology of S with \(2^s\) elements. Let \(\mathcal{A}\) be a non-empty collection-set, where every element of \(\mathcal{A}\) is element of \(\mathcal{P}(S)\). Let \(\mathcal{T} = \mathcal{P}(S) - \mathcal{A}\) be a topology of S.

Let \(E \in \mathcal{A}\). Since \(\mathcal{T}\) is a topology of S, it is clear that \(E \neq \emptyset\) and \(E \neq S\). By considering Proposition 3.1, without lost of generality, let \(v_s \in E\) and \(\{v_s\} \notin \mathcal{T}\). We can say that \(\{v_s\} \in \mathcal{A}\).

Let \(\mathcal{B}=\{\{v_s,v_i\}\mid 1\leq i\leq s-1\}\). Note that \(|\mathcal{B}|=s-1\). Since \(\mathcal{T}\) is a topology of S, then at least s-2 elements of \(\mathcal{B}\) are in \(\mathcal{A}\). Without lost of generality, let \(\widehat{\mathcal{B}}=\{\{v_s,v_i\}\mid 1\leq i\leq s-2\}\subseteq \mathcal{A}\). Now, we define \(B=\{v\mid \{v_s,v\}\in\widehat{\mathcal{B}}\}\). We also define \(\mathcal{C}=\{\{v_s\}\cup C\mid C\in\mathcal{P}(B)\}\). Note that \(|\mathcal{C}|=2^{s-2}, \{v_s\}\in\mathcal{C}\), and \(\mathcal{B}\subseteq\mathcal{C}\). Note that for any distinct elements \(C_1,C_2\in\mathcal{C}\), we have \(C_1\cup C_2\) and \(C_1\cap C_2\) are also in \(\mathcal{C}\). However, every \(C\in\mathcal{C}\) satisfy \(C\cap\{v_s,v_{s-1}\}=\{v_s\}\in\mathcal{A}\). So, it must be \(\mathcal{C}\subseteq\mathcal{A}\). Therefore, we obtain

\[|\mathcal{P}(S) - \mathcal{A}| \le 2^s - 2^{s-2} = 3 \cdot 2^{s-2}.\]

Proof of Theorem 2. Theorem 1.2 is a direct consequence of Propositions 1.1 and 3.2.

Acknowledgement

This work is partially supported by Riset Program Penelitian, Pengabdian Masyarakat, dan Inovasi (P3MI) 1016/I1.C01/PL/2017, by APVV-15-0116, and by VEGA 1/0233/18.

References

• [1] B.D. Acharya and K.A. Germina, Set-valuations of graphs and their applications: A survey, Ann. Pure Appl. Math. 4 (1) (2013), 8–42.
• [2] A. Rosa, On certain valuation of the vertices of a graph, in Theory of Graphs (Int. Symposium, Rome, July 1966), Gordon and Breach, N.Y., and Dunod. Paris (1967), 349–355.
• [3] N.K. Sudev and K.A. Germina, A study on topological integer additive set-labeling of graphs, Electron. J. Graph Theory Appl. 3 (1) (2015), 70–84.
• [4] G. Varadhan and D. Manocha, Accurate Minkowski sum approximation of polyhedral models, Graph. Models 68 (2006), 343–355.