R. Gurusamy^∗a , R. Lakshmanan^b , R. Ratha Jeyalakshmi^a , S. Arockiaraj^c

sahama2010@gmail.com, lakshmsc2004@yahoo.co.in, rratha@mepcoeng.ac.in, psarockiaraj@gmail.com ^∗corresponding author

The Steiner n-radial graph of a graph G on p vertices, denoted by SRn(G), has the vertex set as in G and any n(2 ≤ n ≤ p) vertices are mutually adjacent in SRn(G) if and only if they are n-radial in G. When G is disconnected, any n vertices are mutually adjacent in SRn(G) if not all of them are in the same component. For the edge set of SRn(G), draw Kⁿ corresponding to each set of n-radial vertices. The Steiner radial number rS(G) of a graph G is the least positive integer n such that the Steiner n-radial graph of G is complete. In this paper, Steiner radial number has been determined for the line graph of any tree, total graph of any tree, complement of any tree, sum of two non-trivial trees and Mycielskians of some families. For any pair of positive integers a, b ≥ 3 with a ≤ b, there exists a graph whose Steiner radial number is a and Steiner radial number of its line graph is b.

Keywords: n-radius, Steiner n-radial graph, Steiner radial number, line graph, total graph, Mycielskian graph.

Mathematics Subject Classification : 05C12

DOI: 10.5614/ejgta.2025.13.1.3

1. Introduction

We consider finite undirected graphs without multiple edges and loops throughout this paper. Let G be a graph on p vertices and S, a set of vertices of G. The subgraph induced by S in G is denoted by ⟨S⟩. In [9], the Steiner distance (SD) of S in G denoted by dG(S), is defined as

Received: 21 February 2020, Revised: 19 December 2024, Accepted: 27 January 2025.

^a Department of Mathematics, Mepco Schlenk Engineering College, Sivakasi 626005, Tamil Nadu, INDIA.

^bPG and Research Department of Mathematics, Thiagarajar College, Madurai 625009, Tamil Nadu, INDIA.

^cDepartments of Mathematics,Government Arts & Science College, Sivakasi 626124, Tamil Nadu, INDIA.

the minimum number of edges in a connected subgraph of G that contains S. Such a subgraph is necessarily a tree and is called a Steiner tree for S in G. Steiner trees play a significant role in various aspects of image processing, such as segmentation, feature extraction, image registration, and compression. They provide efficient methods for connecting and analyzing image features, thereby enhancing the capabilities of automated image analysis systems and improving the accuracy of image-based applications [18, 19]. The Steiner n-eccentricity en(v) of a vertex v in a graph G is defined as en(v) = max{dG(S) : S ⊆ V (G) with v ∈ S and |S| = n}. The n-radius radn(G) of G is defined as the smallest Stenier n-eccentricity among the vertices of G, and the n-diameter diamn(G) of G is the largest Steiner n-eccentricity. The concept of SD was further developed in [17, 21].

In [14], KM. Kathiresan et al. introduced the concept of Steiner radial number of a graph G. Any n vertices of a graph G are said to be n-radial to each other if SD between them is equal to the n-radius of the graph G. The Steiner n-radial graph of a graph G, denoted by SRn(G), has the vertex set as in G and n(2 ≤ n ≤ p) vertices are mutually adjacent in SRn(G) if and only if they are n-radial in G. If G is disconnected, any n vertices are mutually adjacent in SRn(G) if not all of them are in the same component. For the edge set of SRn(G), draw Kⁿ corresponding to each set of n-radial vertices. When n = 2, Steiner n-radial graph of G coincides with radial graph G. For a pair of graphs G and H on p vertices, the least positive integer n such that SRn(G) ∼= H, is called the Steiner completion number of G over H. When H = Kp, the Steiner completion number of G over His called as Steiner radial number of G. The Steiner radial number rS(G) of a graph G is the least positive integer n such that the Steiner n-radial graph of G is complete.

The Steiner tree and Steiner radial number are valuable tools in network optimization across various domains, offering efficient solutions for connecting multiple points with minimal distance or cost. Steiner radial graphs are valuable for visualizing complex networks such as social networks, communication networks, or biological networks [7, 23, 24].

The concept of graph operator has found various applications in chemical research [12, 11]. The line graph L(G) of a graph G has vertices corresponding to the edges of G and two vertices are adjacent in L(G) if their corresponding edges of G have a common end vertex [10]. Parameters of line graphs have been applied for the evaluation of structural complexity of molecular graphs and design of novel topological indices [5, 6].

The total graph T(G) of a graph G has vertex set V (G) ∪ E(G) and two vertices of T(G) are adjacent whenever they are neighbours in G [13]. The vertices and edges of a graph are called elements. Two elements of a graph are neighbours if they are either incident or adjacent. Several properties of total graphs are investigated in [1, 2, 3, 4]. A tree is defined as a connected graph that contains no cycles, and various parameters associated with trees have been extensively studied [20, 22]. A vertex of degree zero in G is called an isolated vertex and a vertex of degree one is called a pendant vertex or a leaf. An edge e in a graph G is called a pendant edge if it is incident with a pendant vertex. A vertex of degree p − 1 is called an universal vertex or full degree vertex. The graph G obtained from K1,m and K1,n by joining their centers by an edge is called a bistar and is denoted by B(m, n). The join G = G¹ + G² has V (G) = V (G1) ∪ V (G2) and E(G) = E(G1) ∪ E(G2) ∪ {uv : u ∈ V (G1), v ∈ V (G2)} if G¹ and G² are two graphs with disjoint vertex sets. A vertex v in G is called peripheral if eccentricity of v is equal to diameter of G.

A power graph \(G^k\) (the \(k^{th}\) power of a graph G) is the graph whose vertices are those of G and in which two distinct vertices are joined whenever the distance between them in G is at most k [13]. The complement \(\overline{G}\) of a simple graph G is the simple graph with vertex set V(G) defined by \(uv \in E(\overline{G})\) if and only if uv is not in E(G) [8]. For a graph G = (V, E), the Mycielskian of G is the graph \(\mu(G)\) with vertex set \(V \cup V' \cup \{u\}\), where \(V' = \{v'_i : v_i \in V\}\) and edge set \(E \cup \{v_iv'_j : v_iv_j \in E\} \cup \{v'_iu : v'_i \in V'\}\) [16]. The following notation can be found in [15]. The set of all connected graphs G for which F(G) = 1 and F(G) = 0 on F(G) = 0 or F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on F(G) = 0 on

Now, we collect some useful results known for Steiner radial number of graphs from [14].

Theorem A [14]. For every tree T with \(m(\neq p-1)\) pendant vertices, \(r_S(T)=m+2\).

Theorem B [14]. For any complete bipartite graph \(K_{p_1,p_2}\) with \(p_1 \le p_2\) and \(p_1 \ne 1\), \(r_S(K_{p_1,p_2}) = p_1 + 1\).

Theorem C [14]. If G is disconnected graph of order \(p \ge 3\) but not totally disconnected, then \(SR_3(G) \cong K_p\).

Theorem D [14]. \(r_S(G) = 2\) if and only if G is either complete or totally disconnected. For graph theoretic terminology, we follow [8].

2. Main Results

In this section, we shall determine the Steiner radial number for the line graph of a graph, the total graph of a graph, the complement of a tree, and the Mycielskians of certain graphs.

In Observation 2.1, we determine the Steiner radial number for the complement of a complete n-partite graph and illustrate the possible Steiner n-radial graphs in Example 2.1.

Observation 2.1. For any complete n-partite graph other than complete graph, the Steiner radial number of its complement is 3.

Proof. By Theorem C, the result follows.

Proposition 2.1. If \(G \in F_{12}\), then \(r_S(G) = 3\).

Proof. Since \(G \in F_{12}\), \(R(G) \cong G\) and hence \(SR_n(G) \cong G\) which is not complete. Therefore, \(r_S(G) \geq 3\). SD of any 3-element set having at least one full degree vertex is 2 and SD of any 3-element set in which none of them are adjacent or only 2 vertices are adjacent is 3. Hence for any vertex v of degree p-1 in G, \(e_3(v)=2\) and for any vertex v of degree less than p-1, \(e_3(v)\) is either 2 or 3. Hence 3-radius of G is 2. Hence \(SR_3(G)\cong K_p\) and hence \(r_S(G)=3\).

Example 2.1. All possible Steiner n-radial graphs of the line graph of \(K_{2,4}\) are given below: Let \(G = K_{2,4}\), and let its line graph, denoted by L(G), be shown in Figure 1. If we let n = 2, \(rad_2(L(G)) = 2\) and the sets \(S_1 = \{e_{11}, e_{22}\}\), \(S_2 = \{e_{11}, e_{23}\}\), \(S_3 = \{e_{11}, e_{24}\}\), \(S_4 = \{e_{12}, e_{21}\}\), \(S_5 = \{e_{12}, e_{23}\}\), \(S_6 = \{e_{12}, e_{24}\}\), \(S_7 = \{e_{13}, e_{21}\}\), \(S_8 = \{e_{13}, e_{22}\}\), \(S_9 = \{e_{13}, e_{24}\}\), \(S_{10} = \{e_{14}, e_{21}\}\), \(S_{11} = \{e_{14}, e_{22}\}\) and \(S_{12} = \{e_{14}, e_{23}\}\) are the only sets of 2-radial vertices of L(G). Hence the Steiner 2-radial graph of L(G) is obtained and shown in Figure 2.

If we take n=3, \(rad_3(L(G))=3\) and the sets \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\)

{e21, e23, e12}, S¹³ = {e21, e23, e14}, S¹⁴ = {e21, e24, e12}, S¹⁵ = {e21, e24, e13}, S¹⁶ = {e21, e12, e13}, S¹⁷ = {e21, e12, e14} and S¹⁸ = {e21, e13, e14} are the only sets of 3-radial vertices of L(G). Hence the Steiner 3-radial graph of L(G) is obtained and shown in Figure 2.

If we let n = 4, rad4(L(G)) = 4 and the sets S¹ = {e11, e22, e23, e24}, S² = {e12, e21, e23, e24}, S³ = {e13, e21, e22, e24}, S⁴ = {e14, e21, e22, e23}, S⁵ = {e11, e12, e13, e24}, S⁶ = {e11, e13, e14, e22} and S⁷ = {e12, e13, e14, e21} are the only sets of 4-radial vertices of L(G). Hence the Steiner 4 radial graph of L(G) is obtained, which is isomorphic to SR3(L(G)), as shown in Figure 3.

If we take n = 5, rad5(L(G)) = 4 and the sets S¹ = {e11, e12, e13, e14, e21}, S² = {e11, e12, e22, e23, e24}, S³ = {e13, e14, e22, e23, e24} and S⁴ = {e11, e21, e22, e23, e24} are 5 radial vertices of L(G). Hence the Steiner 5-radial graph of L(G) is obtained and shown in Figure 3, which is isomorphic to K8.

Figure 1. G = K2,⁴ and its Line graph L(G)

Figure 2. Steiner 2-radial graph of L(G)

Steiner radial number resulting from various graph operations | Gurusamy et al.

Figure 3. Steiner 3-radial graph of L(G) and Steiner 5-radial graph of L(G)

2.1. Steiner radial number for Line graph of some graphs

In the next theorem, we compute the Steiner radial number for tree.

Theorem 2.1. For any tree T of order p other than star and bistar, rS(L(T)) = rS(T). When T is either a star or a bistar, rS(L(T)) is 2 and 3 respectively.

Proof. Let T be any tree of order p other than star and bistar with m pendant vertices. Let x1, x2, . . . , x^m be the m pendant edges of T. Since L(T) has p − 1 vertices, d(S) ≤ p − 2 for any vertex subset S of L(T). For any vertex e in L(T), en(e) = p−2 for n = m+1. Let eⁱ and e^j be two non pendant edges of T. For any set X ⊆ {x1, x2, . . . , xm} with |X| = m−1, SD of the set {eⁱ , ej} S X is less than p − 2 and hence eⁱ and e^j are non-adjacent in Steiner (m + 1)-radial of L(T). Since (m + 2)-radius of L(T) is p − 2 and {eⁱ , e^j , x1, x2, x3, . . . xm} has SD p − 2 in L(T), the Steiner (m + 2)-radial of L(T) is Kp. Therefore, rS(L(T)) = m + 2. By Theorem A, the result follows.

When T is a star, L(T) is a complete graph on p−1 vertices and hence rS(L(T)) = 2. When T is a bistar B(m, n) on m+n+2 vertices, L(T) is a graph obtained by identifying a vertex of Km+1 with a vertex of Kn+1. This shows that L(T) ∈ F¹² and by proposition 2.1 , rS(L(T)) = 3.

In the next theorem, we compute the Steiner radial number for complete bipartite graph.

Proposition 2.2. For any complete bipartite graph K^p1,p² with p¹ ≤ p² and p¹ ̸= 1, rS(L(K^p1,p² )) = p² + 1.

Proof. Let {u1, u2, . . . , u^p1 } and {v1, v2, . . . , v^p2 } be the two partitions of K^p1,p² . Let {ei,j : 1 ≤ i ≤ p2, 0 ≤ j ≤ p¹ − 1} be the vertices of L(K^p1,p² ). For each vertex ei,j ,

\[e_n(e_{i,j}) = \begin{cases} 2n-2 &, & \text{if} & n \le p_1\\ n+p_1-2, & \text{if} & p_1+1 \le n \le p_2\\ p_1+p_2-1, & \text{if} & p_2+1 \le n \le p_1p_2 \end{cases}\]

Since any set of p² vertices having the vertices e1,⁰ and e1,¹ has SD less than n-radius, rS(L(K^p1,p² )) > p2. By graph symmetry, if e1,⁰ is adjacent to all the remaining vertices in SR^p2+1(L(K^p1,p² )), then the result follows. By division algorithm, p² = kp¹ + r. The set S = {ei,j : 1 ≤ i ≤ kp¹ + r

and \(j=(i-1) \bmod p_1\) is a set of \(p_2\) vertices whose SD is \(p_1+p_2-2\). By adding any vertex \(e_{i,j} \in V(L(K_{p_1,p_2}))-S\), SD of \(S \cup e_{i,j}\) is \(p_1+p_2-1\). Hence \(e_{1,0}\) is adjacent all the vertices of \(SR_{p_2+1}(L(K_{p_1,p_2}))\).

Steiner radial numbers highlight distinct variations between a graph and its line graph. The following Theorem demonstrates the existence of graphs with specified Steiner radial numbers for both the original graph and its line graph

Theorem 2.2. For any pair of positive integers \(a, b \ge 3\) with \(a \le b\) there exists a graph whose Steiner radial number is a and Steiner radial number of its line graph is b.

Proof. By taking \(p_1 = a - 1\) and \(p_2 = b - 1\), using Theorem B and proposition 2.2, the result follows.

2.2. Steiner radial number for Total graph of a tree

In the upcoming theorem, we determine the Steiner radial number for the total graph of a tree.

Theorem 2.3. For any tree T of order p with \(m(\neq p-1)\) pendant vertices, \(r_S(T(T))=2m+2\).

Proof. Let T be a tree of order p with m number of pendant vertices and n number of pendent edges. If \(n \geq 2m\), then the n-eccentricities of all the vertices are equal. Since a tree other than star has at least two non-pendant vertices, SD of set of 2m or 2m+1 vertices with two non-pendant vertices is less than n-radius. But the set of 2m+2 vertices having all pendant vertices and edges is equal to n-radius. Hence the result follows.

In the next proposition, we compute the Steiner radial number for power graph.

Proposition 2.3. Let G be a graph on \(p \ge 3\) vertices with radius r. Then

\[r_S(G^k) = \begin{cases} 3, & \text{for } r \leq k < d \\ 2, & \text{for } r = d. \end{cases}\]

Proof. When \(r \leq k < d\), \(G^k \in F_{12}\) and by proposition 2.1, \(r_S(G^k) = 3\). When r = d, \(G^k \cong K_p\) and hence \(r_S(G^k) = 2\).

In the next proposition, we compute the Steiner radial number for join of two graphs.

Proposition 2.4. If \(G_1\) and \(G_2\) are non-trivial trees with \(p_1\) and \(p_2\) vertices respectively and none of them is a star graph, then \(r_S(G_1 + G_2) = min\{p_1, p_2\}\).

Proof. Assume \(p_1 \leq p_2\). Let \(u_1, u_2, \ldots, u_{p_1}\) be the vertices of \(G_1\) and \(v_1, v_2, \ldots, v_{p_2}\) be the vertices of \(G_2\). In \(G_1 + G_2\), \(e_n(u_i) = \begin{cases} n, & \text{if } n < p_1 \\ n-1, & \text{if } n \geq p_1 \end{cases}\) and \(e_n(v_j) = \begin{cases} n, & \text{if } n < p_2 \\ n-1, & \text{if } n \geq p_2 \end{cases}\) for any i and j, \(1 \leq i \leq p_1\) and \(1 \leq j \leq p_2\) respectively. If \(n < p_1, rad_n(G_1 + G_2) = n\) and in this case \(SR_n(G_1 + G_2)\) is not complete on \(p_1 + p_2\) vertices. No one of the vertex \(u_i\) is adjacent to any one of \(v_j\), \(1 \leq i \leq p_1\) and \(1 \leq j \leq p_2\). Hence \(r_S(G_1 + G_2) \geq n + 1\) whenever \(n < p_1\). Suppose that \(n \geq p_1\). In this case \(rad_n(G_1 + G_2) = n - 1\). Let X be a subset of \(V(G_1 + G_2)\) with n-elements. If X contains at least one element from each \(G_1\) and \(G_2\), then SD of X is n - 1. This implies that any two vertices in \(SR_n(G_1 + G_2)\) are adjacent. Hence the result follows. □

2.3. Steiner radial number for complement of a tree

In the next result, we obtain a Steiner radial number for complement of a tree.

Theorem 2.4. Let T be a tree other than star. If T has either a pendant vertex which is adjacent to a vertex of degree 2 or a vertex and its neighbours all of degree 2, then \(r_S(\overline{T}) = n\). Otherwise \(r_S(\overline{T}) = d + 2\) where d is the minimum degree among the vertices of degree > 3.

Proof. Let T be a tree and v be a vertex of T. If v is a pendant vertex which is adjacent to a vertex of degree 2, then \(e_n(v,\overline{T})=n\) while \(n\leq 3\) and n-1 while \(n\geq 4\). If v is a vertex of degree 2 whose neighbours are also of degree 2, then \(e_n(v,\overline{T})=n\) while \(n\leq 3\) and n-1 while \(n\geq 4\). If T has a vertex and its neighbours all of degree 2, then \(rad_n(\overline{T})=n\) while \(n\leq 3\) and n-1 while \(n\geq 4\). In case of \(n\leq 3\), \(SR_n(\overline{T})\) is not complete. Since there is no set of n-elements containing at least two peripheral vertices of T with SD n. When n=4, \(rad_n(\overline{T})=3\) and \(SR_n(\overline{T})\) is complete.

Assume that T has neither a pendant vertex adjacent to a vertex of degree 2 nor a vertex and its neighbours all of degree 2. In this case every vertex v of T is adjacent to at least one vertex say u of degree \(\geq 3\). Among all the vertices of T with degree at least 3, let v has the smallest degree d. Any set S having the vertex v and a non-neighbour of v is of SD |S| - 1. Any set S having the vertices from N[v] is of SD |S|. Hence for each vertex \(u_i\) of T with degree \(d_i\), \(e_n(u_i, \overline{T}) = \begin{cases} n, & \text{if } n \leq d_i + 1 \\ n-1, & \text{if } n \geq d_i + 2 \end{cases}\) and for each vertex \(w \in N(u_i)\), \(e_n(w, \overline{T}) = \begin{cases} n, & \text{if } n \leq d_i + 1 \\ n-1, & \text{if } n \geq d_i + 2 \end{cases}\). This implies that \(rad_n(\overline{T}) = n\) if \(n \leq d+1\) and n-1 if \(n \geq d+2\). In \(\overline{T}\), any set S on (d+1)-elements having at least two peripheral vertices is of SD(d). Hence \(SR_{d+1}(\overline{T})\) is not complete. Take n = d+2. Since any set S of size d+2 having any two pendant vertices of T and at least two peripheral vertices of T is of T is complete. Hence the result follows.

If T is a star on p vertices, then \(\overline{T}\) is \(K_{p-1} \cup K_1\) and by Theorem \(C, r_S(\overline{T}) = 3\).

Corollary 2.1. For any positive integer n, \(r_S(\overline{P_n}) = \begin{cases} 4, & \text{if } n \geq 4, \\ n, & \text{if } n = 1, 2, 3. \end{cases}\)

Proof. By 2.4, the result is true for \(n \geq 5\). When \(n = 4, \overline{P_n} \cong P_4\) and hence by Theorem A, \(r_S(\overline{P_4}) = 4\). When n = 3, \(\overline{P_n} \cong P_2 \cup K_1\) and hence by Theorem C, \(r_S(\overline{P_3}) = 3\). When n = 2, \(\overline{P_n}\) is totally disconnected and hence by Theorem D, \(r_S(\overline{P_2}) = 2\). When n = 1, the result is trivial. \(\square\)

Corollary 2.2. For any positive integers \(m_1\) and \(m_2\) with \(m_1 \leq m_2\), \(r_S(\overline{B_{m_1,m_2}}) = m_1 + 3\)

2.4. Steiner radial number for Mycielskians of some standard graphs

In the following results, we shall explore the computation of the Steiner radial number for the Mycielskians of a certain family of graphs.

Theorem 2.5. For any complete bipartite graph \(K_{m,n}\), \(r_S(\mu(K_{m,n})) = 3\).

Proof. Let \(A = \{a_1, a_2, \dots, a_m\}\) and \(B = \{b_1, b_2, \dots, b_n\}\) be the two partitions of vertex set V and let E be edge set of \(K_{m,n}\). Then the Mycielskian of \(K_{m,n}\) is \(\mu(K_{m,n})\) with vertex set \(V' = A \cup B \cup A' \cup B' \cup \{u\}\), where \(A' = \{a'_i : a_i \in A\}\) and \(B' = \{b'_i : b_i \in B\}\) and edge set \(E' = E \cup \{a_i b'_j : a_i b_j \in E\} \cup \{b_i a'_j : b_i a_j \in E\} \cup \{a'_i u : a'_i \in A\} \cup \{b'_i u : b'_i \in B\}\). Since \(\mu(K_{m,n})\) is not isomorphic to

\(K_{2(m+n)+1}\), by theorem D, \(r_S(\mu(K_{m,n})) \geq 3\). For any vertex v in \(\mu(K_{m,n})\), \(e_3(v) = 3\) and hence 3-radius is 3. The Steiner 3-radial graph of \(\mu(K_{m,n})\) is \(SR_3(\mu(K_{m,n}))\) has the vertex set V' and edge set can be obtained from the following cases.

Case 1. Each of the sets \(\{a_i, a_j, u\}\), \(\{b_i, b_j, u\}\), \(\{a'_i, a'_j, a_i\}\) and \(\{b'_i, b'_j, b_i\}\) for all \(1 \le i \le m\), \(1 \le j \le n\) with \(i \ne j\) have SD 3 respectively. Hence the subgraphs [A], [B], [A'] and [B'] are complete in \(SR_3(\mu(K_{m,n}))\).

Case 2. Each of the sets \(\{a_i, b_j, u\}\), \(\{a_i, a_i', u\}\), \(\{a_i, b_j', a_i'\}\), \(\{b_j, b_j', u\}\), \(\{b_j, b_j', a_i'\}\) and \(\{b_j', b_k', a_i'\}\) for all \(1 \le i \le m\), \(1 \le j, k \le n\) with \(j \ne k\) have SD 3 respectively. Therefore, all the elements in A, B, A', B' and \(\{u\}\) are mutually adjacent in \(SR_3(\mu(K_{m,n}))\). Thus Steiner 3-radial of \(\mu(K_{m,n})\) is \(K_{2(m+n)+1}\).

Theorem 2.6. Let G be a graph of order n with diameter at most 2 and \(\Delta(G) = n - 1\). Then \(r_S(\mu(G)) = 3\).

Proof. Let \(V = \{v_1, v_2, \dots, v_n\}\) be the vertex set and E be the edge set of G. Then the Mycielskian of G is \(\mu(G)\), has the vertex set \(V \cup V' \cup \{u\}\), where \(V' = \{v'_i : v_i \in V\}\) and edge set \(E \cup \{v_i v'_j : v_i v_j \in E\} \cup \{v'_i u : v'_i \in V'\}\). Since \(\Delta(G) = n - 1\), there exists a vertex v in G such that deg(v) = n - 1, for that \(v, e_3(v) = 3\) in \(\mu(G)\). Hence 3-radius of \(\mu(G)\) is 3.

Case 1. Assume that diameter of G is 1. Then each of the sets \(\{v_i, v_j, u\}\), \(\{v_i, v_i', u\}\) and \(\{v_i, v_i', v_j'\}\) in \(\mu(G)\) have SD 3 and forms a \(K_3\) in the corresponding Steiner 3—radial graph. Thus \(SR_3(\mu(G)) = K_{2n+1}\).

Case 2. Assume that diameter of G is 2. Then each of the sets \(\{v_i, v_j, u\}\), \(\{v_i', v_j', v_k'\}\) and \(\{v_i, v_i', u\}\) have SD 3. Hence in \(SR_3(\mu(G))\) the subgraph \([V] \cup \{u\}\) and \([V'] \cup \{u\}\) are complete. Hence to prove \(SR_3(\mu(G))\) is complete, it is enough to show that every vertex in V is adjacent to all the vertices in V'.

Subcase a. If \(v_i\) is a full degree vertex in G, the sets \(\{v_i, v_i', v_j'\}\) having SD 3. Thus the subgraph \([V \cup V']\) is complete in \(SR_3(\mu(G))\). Hence the result follows.

Subcase b. If \(v_i\) is not a full degree vertex, then there exists a vertex \(v_j\) not adjacent with \(v_i\). Since diameter of G is 2, there exists a vertex \(v_k\) common to \(v_i\) and \(v_j\). Then the sets \(\{v_i, v_k', v_j'\}\) having SD 3 and hence the subgraph \([V \cup V']\) is complete in \(SR_3(\mu(G))\). Hence the result follows. \(\square\)

Theorem 2.7. For any path \(P_n\) with \(n \ge 7\) vertices, \(SR_3(\mu(P_n)) = K_{2n+1} - K_{1,n}\)

Proof. Let \(V = \{v_0, v_1, v_2, \dots, v_{n-1}\}\) be the vertex set and E be the edge set of \(P_n\). Then the Mycielskian of \(P_n\) is \(\mu(P_n)\), has the vertex set \(V \cup V' \cup \{u\}\), where \(V' = \{v'_i : v_i \in V\}\) and edge set \(E \cup \{v_i v'_j : v_i v_j \in E\} \cup \{v'_i u : v'_i \in V'\}\). Since \(\mu(P_n)\) is not isomorphic to \(K_{2n+1}\), by theorem D, \(r_S(\mu(P_n)) \geq 3\). For any vertex in \(\mu(P_n)\), \(e_3(v_i) = 6\), \(e_3(v'_i) = 5\) and \(e_3(u) = 4\) for all \(0 \leq i \leq n-1\) and hence 3-radius is 4. \(SR_3(\mu(P_n))\) has the vertex set as in \(\mu(P_n)\) and edge set can be obtained from the following cases.

Case 1. The sets \(\{v_i, v_j, u : d(v_i, v_j) \ge 3 \text{ in } P_n\}\) and \(\{v_i, v_j, v_k : d(v_i, v_j) = 2 \text{ and } d(v_i, v_k) = 2 \text{ or } d(v_j, v_k) = 2 \text{ in } P_n\}\) have SD 4 and forms \(K_3\) in \(SR_3(\mu(P_n))\). Let \(v_k\) be the eccentric vertex of \(v_i\) in \(P_n\). Then \(\{v_i, v_j, v_k' : d(v_i, v_j) = 1 \text{ in } P_n\}\) has SD 4. Hence in \(SR_3(\mu(P_n))\), the subgraph \([V] \cup \{u\}\) is complete.

Case 2. For any two vertices \(v_i'\) and \(v_j'\) in V', there exists a vertex \(v_k \in V\) such that \(d(v_j', v_k) = 2\)

or \(d(v_i', v_k) = 2\). Hence the sets \(\{v_i', v_j', v_k\}\) forms \(K_3\) in \(SR_3(\mu(P_n))\). Thus the subgraph [V'] is complete in \(SR_3(\mu(P_n))\).

Case 3. Let \(v_k\) be the eccentric vertex of \(v_i\) in \(P_n\). Then the sets \(\{v_i, v_j', v_k\}\) and \(\{v_i, v_j', v_k'\}\) have SD 4 when \(v_i\) and \(v_j\) are adjacent and non-adjacent respectively. Hence the subgraphs [V] and [V'] are mutually adjacent in \(SR_3(\mu(P_n))\).

Case 4. For any two vertices \(\{v_i', u\}\), there is no vertex w in \(\mu(P_n)\) such that \(d(\{v_i', u, w\}) = 4\). Hence the vertices \(v_i'\) and u are not adjacent in \(SR_3(\mu(P_n))\). Hence the result follows.

Observation 2.2. For any path \(P_n\), \(r_S(\mu(P_n)) = 3\), for \(1 \le n \le 4\).

Theorem 2.8. For any path \(P_n\) with \(n \ge 5\) vertices, \(r_s(\mu(P_n)) = \lceil \frac{n}{3} \rceil + 2\).

Proof. Let \(V=\{v_1,v_2,v_3,\ldots,v_n\}\) be the vertex set and E be the edge set of \(P_n\). Then the Mycielskian of \(P_n\) is \(\mu(P_n)\), which has the vertex set \(V\cup V'\cup\{u\}\) where \(\text{[rumus tidak dapat ditampilkan dengan baik — lihat PDF asli]}\). For each vertex \(w\in V\cup V'\), \(e_{\lceil\frac{n}{3}\rceil+1}(w)=2\lceil\frac{n}{3}\rceil+1\) and \(e_{\lceil\frac{n}{3}\rceil+1}(u)=2\lceil\frac{n}{3}\rceil\). Hence \((\lceil\frac{n}{3}\rceil+1)-\) radius is \(2\lceil\frac{n}{3}\rceil\).

Consider the set S with \(\lceil \frac{n}{3} \rceil\) vertices from V such that \(d(v_i, v_j) \geq 3\) if \(v_i, v_j \in S\). Then the set \(S - \{v_i\} \cup \{u, v_i'\}\) with \((\lceil \frac{n}{3} \rceil + 1)\) vertices has \(SD(2(\lceil \frac{n}{3} \rceil - 1) + 1) < 2\lceil \frac{n}{3} \rceil\). Therefore, u is not adjacent with \(v_i'\) in Steiner \((\lceil \frac{n}{3} \rceil + 1)\) - radial graph of \(\mu(P_n)\). Hence, \(r_s(\mu(P_n)) = \lceil \frac{n}{3} \rceil + 2\).

Now \(e_{\lceil \frac{n}{3} \rceil + 2}(u) = 2\lceil \frac{n}{3} \rceil + 1\) and \(e_{\lceil \frac{n}{3} \rceil + 2}(w) = 2\lceil \frac{n}{3} \rceil + 2\) where \(w \in V \cup V'\) and hence \((\lceil \frac{n}{3} \rceil + 2)\) - radius is \(2\lceil \frac{n}{3} \rceil + 1\). Consider the set \(S' = \{u\} \cup \{v'_j\} \cup S_i\) where \(S_i = \{v_i, v_{i+3}, v_{i+6}, \ldots\}\) with \(|S_i| = \lceil \frac{n}{3} \rceil\) for i = 1, 2, 3 and \(v_j \in S_i\). Clearly, SD of the set S' is \(2\lceil \frac{n}{3} \rceil + 1\). Hence it gives u is adjacent to all vertices of V and V' and all vertices of V is adjacent to V'.

Hence, to prove \(SR_{\lceil \frac{n}{3} \rceil + 2}(\mu(P_n)) = K_{2n+1}\), it is enough to prove the subgraphs [V] and [V'] are complete in \(SR_{\lceil \frac{n}{2} \rceil + 2}(\mu(P_n))\).

Case 1. For every vertices \(v_j \notin S_i\) and \(v_j \in V\), the set \(S_i \cup \{v_j, v_j'\}\) has \(SD \ 2\lceil \frac{n}{3} \rceil + 1\). Hence subgraph [V] is complete in \(SR_{\lceil \frac{n}{3} \rceil + 2}(\mu(P_n))\).

Case 2. Let \(S'_i = \{v' \in V' : v \in S_i \subseteq V\}.\)

Subcase a. For any \(v'_j, v'_k \in S'_i\), the sets \(S_i - \{v_j\} \cup \{v'_{j-1}, v'_j, v_k\}\) or \(S_i - \{v_j\} \cup \{v'_{j+1}, v'_j, v'_k\}\) have \(SD \ 2\lceil \frac{n}{3} \rceil + 1\).

Subcase b. For any \(v_j'\) and \(v_k'\) in different \(S_i'\), then clearly either \(v_{k+1}\) or \(v_{k-1}\) in \(S_i'\). Hence, the sets \(S_i - \{v_{k+1}\} \cup \{v_j', v_k', v_{k+1}'\}\) or \(S_i - \{v_{k-1}\} \cup \{v_j', v_k', v_{k-1}'\}\) have \(SD \ 2\lceil \frac{n}{3} \rceil + 1\). Therefore, the above two subcases make [V'] is complete in \(SR_{\lceil \frac{n}{2} \rceil + 2}(\mu(P_n))\). Hence the result follows. \(\square\)

Acknowledgement

The authors are grateful to the Editor of the journal and the anonymous reviewers for their valuable comments and suggestions that led to a considerable improvement of the paper over its original version.

References

[1] M. Behzad, A criterion for the planarity of the total graph of a graph, Math. Proc. Cambridge Philos. Soc. 63 (1967), 679–681.

• [2] M. Behzad, The connectivity of total graphs, Bull. Aust. Math. Soc. 1 (1969), 175–181.
• [3] M. Behzad and H. Radjavi, The total group of a graph, Proc. Amer. Math. Soc. 19 (1968), 158–163.
• [4] M. Behzad and H. Radjavi, Structure of regular total graphs, J. Lond. Math. Soc. 44 (1969), 433–436.
• [5] S.H. Bertz, Branching in graphs and molecules, Discrete Appl. Math. 19 (1998), 65–83.
• [6] S.H. Bertz and W.F. Wright, The graph theory approach to synthetic analysis: Definition and application of molecular complexity and synthetic complexity, Graph Theory Notes New York 35 (1998), 32–48.
• [7] B. Wang, A. Li, H. Li, and Y. Chen. Graphfl, A federated learning framework for semisupervised node classification on graphs, arXiv preprint arXiv:2012.04187, 2020.
• [8] F. Buckley and F. Harary, Distance in graphs, Addison-Wesley, Reading, 1990.
• [9] G. Chartrand, O.R. Oellermann, S. Tian. and H.B. Zou, Steiner distance in graphs, Casopis Pro Pestovani Matematiky 114 (4) (1989), 399–410.
• [10] A.A. Dobrynin and L.S Melnikov, Wiener index of generalized stars and their quadratic line graphs, Discuss. Math. Graph Theory 26 (1) (2006), 161–175.
• [11] I. Gutman, L. Popovic, B.K. Mishra, M.Kaunar, and N.Guevara, Appliccation of line graphs in physical chemistry. Predicting surface tension of alkanes, Journal of the Serbian Chemical Society 62 (1993), 1025–1029.
• [12] I. Gutman and E. Estrada, Topological indices based on the line graph of the molecular graph, Journal of Chemical Information and Computer Sciences 36 (1996) 541–543.
• [13] D.A. Holton, D.Lou, and K.L.McAvaney, n-Extendability of line graphs, power graphs and total graphs, Australas. J. Combin. 11 (1995), 215–222.
• [14] K.M. Kathiresan, S.Arockiaraj, R. Gurusamy, and K.Amutha, On the Steiner radial number of graphs, In IWOCA 2012, S.Arumugam and W.F. Smyth (Eds.), Springer-Verlag, Lecture Notes in Comput. Sci. 7643 (2012), 65–72.
• [15] K.M. Kathiresan and G. Marimuthu, A study on radial graphs, Ars Combin. 96 (2010), 353– 360.
• [16] J. Mycielski, Sur le coloriage des graphes, Colloquium Mathematicum 3 (1955), 161–162.
• [17] O.R. Oellermann and S. Tian, Steiner centers in graphs, J. Graph Theory 14 (5) (1990), 585– 597.

• [18] O. Russakovsky and A.Y. Ng, A Steiner tree approach to efficient object detection, 2010 IEEE Computer Society Conference on Computer Vision and Pattern Recognition, San Francisco, CA, USA, (2010), 1070–1077, doi: 10.1109/CVPR.2010.5540097.
• [19] L. Schmidt, C. Hegde, P. Indyk, L. Lu, X. Chi, and D. Hohl, Seismic feature extraction using Steiner tree methods, 2015 IEEE International Conference on Acoustics, Speech and Signal Processing (ICASSP), South Brisbane, QLD, Australia, (2015), 1647–1651, doi: 10.1109/ICASSP.2015.7178250.
• [20] Susilawati, E.T. Baskoro, and R. Simanjuntak, Total vertex irregularity strength of trees with maximum degree five, Electron. J. Graph Theory Appl. 6 (2) (2018), 250–257.
• [21] Y. Mao, Steiner Distance in Graphs—A Survey, arXiv:1708.05779, (2017), 1–85.
• [22] Y. Hafidh and E.T. Baskoro, Partition dimension of trees palm approach, Electron. J. Graph Theory Appl. 12 (2) (2024), 265–272.
• [23] Z. Zheng, Y. Zhou, Y. Sun, Z. Wang, B. Liu, and K. Li, Applications of federated learning in smart cities: recent advances, taxonomy, and open challenges, Connection Science 34 (1) (2022), 128.
• [24] Z. Wu, S. Pan, F. Chen, G. Long, C Zhang, and S.Y. Philip, A comprehensive survey on graph neural networks, IEEE transactions on neural networks and learning systems, 32 (1) (2020), 424.