In this paper, we introduce the concept of vertex-edge locating Roman dominating functions in graphs. A vertex-edge locating Roman dominating \({(ve-LRD)}\) function of a graph \(G=(V,E)\) is a function \(f:V(G)\rightarrow\{0,1,2\}\) such that the following conditions are satisfied: (i) for every adjacent vertices \(u,v\) with \(f(u)=0\) or \(f(v)=0\), there exists a vertex \(w\) at distance \(1\) or \(2\) from \(u\) or \(v\) with \(f(w)=2\), (ii) for every edge \(uv\in E\), \(\max[f(u),f(v)]\neq 0\), and (iii) any pair of distinct vertices \(u,v\) with \(f(u)=f(v)=0\) does not have a common neighbour \(w\) with \(f(w)=2\). The weight of ve-LRD function is the sum of its function values over all the vertices. The vertex-edge locating Roman domination number of \(G\), denoted by \(\gamma_{veLR}(G)\), is the minimum weight of a {ve-LRD} function in \(G\). We proved that the vertex-edge locating Roman domination problem is NP-complete for bipartite graphs. Also, we present the upper and lower bounds of \({ve-LRD}\) function for trees. Lastly, we give the upper bounds of \({ve-LRD}\) function for some connected graphs.
In this paper, we introduce the concept of vertex-edge Locating Roman dominating function. Let \(G=(V,E)\) be an undirected graph with vertex set \(V\) and edge set \(E\). The number of vertices in \(G\) is the order of \(G\) and the number of the edges in \(G\) is the size of the graph \(G\). The set of all neighbors of vertex \(u\) in \(G\) is the open neighborhood of \(u\); that is \(N_G(u)=\{v\in V|uv\in E(G)\}\). The closed neighborhood of \(u\) in \(G\) is \(G[u]=\{u\}\cup N_G(u)\). The number of vertices at distance \(2\) from vertex \(v\) in \(G\) is denoted as \(N_2(v)\). The degree of vertex \(u\) in \(G\) is \(d(u)=|N_G(u)|\).
The path of order \(n\) is written as \(P_n\), the size of \(P_n\) is \(n-1\). The graphs \(C_n,K_n\) denote the cycle and complete graphs of order \(n\) respecticely. The diameter of \(G\), denoted by \(diam(G)\) is define as the shortest maximum distance between two vertices in \(G\), that is \(diam(G)=max\{dist(x,y):x,y\in V(G)\}\).
A rooted tree is a tree whereby the vertex called the root is distinguished from the other vertices of the tree. Let \(T\) denotes the rooted tree. Vertex of degree one is the leaf of a tree and the support vertex is a vertex adjacent to a leaf. A star and Bistar are trees with one and two non-leaf vertices respectively.
Let \(S(T)\) and \(L(T)\) denotes the set of all support vertices and the set of leaves in \(T\) respectively. Let \(|L(T)|=l(T)\) and \(s(T)=|S(T)|\), we denote \(L(u)\) as the set of all leaves adjacent to a support vertex \(u\) and \(l(u)=|L(u)|\). Let the core internal vertices \(I(T)\) denotes the set of vertices in \(T\) that are not root, support and leaf vertices. Also, let \(i(T)=|I(T)|\) and note that \(i(T)=n-l(T)-s(T)\).
A subset \(D\subset V\) is known as a dominating set of \(G\) if every vertex \(u\) in \(V\setminus D\) has a neighbor in \(D\). The dominating set with minimum cardinality is known as the domination number \(\gamma(G)\) of \(G\). Let \(\beta \in \{0,1,2\}\) and for any vertex \(u\in G\), we denote the set of vertices with \(f(u)=\beta\) by \(V_\beta\).
Slater [15] introduced the study of locating dominating sets in graphs whereby he studied many graph related problems with various types of protection. His objective in the work is to locate the intruder. A locating dominating set \(D\subset V(G)\) is a dominating set with the property that the set \(N(u)\cap D\) is unique for each vertex \(u\in V(G)\setminus D\). The locating dominating set of \(G\) with minimum cardinality is known as locating domination number of \(G\). Several domination parameters in the concept of locating domination has been considered, for more result, see [2,8,5,7].
A Roman dominating function (\(RDF\)) on \(G\) is a function \(f:V(G)\rightarrow \{0,1,2\}\) such that every vertex \(v\in V(G)\) with \(f(v)=0\) is adjacent to at least one vertex \(u\) with \(f(u)=2\). The weight of \(RDF\) is the value \(f(V(G))=\sum_{v\in V(G)}f(v)\), denoted by \(w(f)\). Roman domination number denoted by \(\gamma_R(G)\) is the \(RDF\) on \(G\) with minimum weight. Cockayne et al. [9] introduced Roman domination which was motivated by the work of Re Velle and Rosing [14] and Stewart [16]. See [4,6] for more results on Roman domination.
A \(RD\)-function is called a locating Roman dominating function (\(LRD\)-function) if for any pair of vertices \(u,v\) with \(f(u)=f(v)=0,N(u)\cap V_2 \neq N(v)\cap V_2\). The minimum weight of \(LRD\)-function is known as the locating Roman domination number denoted as \(\gamma_R^L(G)\). See [10,3] for more result on \(LRD\)-function.
In this paper, we consider the case whereby there will be optimal location of intruder, this lead to the study of vertex-edge locating Roman dominating function. Nares Kumar and Venkatakrishnan [13,12] studied the vertex-edge Roman domination. A vertex-edge Roman dominating (\(ve\)-LRD) function on a graph \(G\) is a function \(f : V(G) \rightarrow \{0, 1, 2\}\) with the property that for every edge \(uv \in E\), either \(max\{f(u), f(v)\} \neq 0\), or there exists \(w \in N(u)\) or \(N(v)\) such that \(f(w) = 2\). The vertex-edge Roman domination number of a graph \(G\) denoted by \(\gamma_{veR}(G)\) is the minimum weight of a \(ve\)-RDF, i.e., \(\gamma_{veR}(G) = min\{w(f) : f \ is \ a \ ve-RDF \ on \ G\}\). More result on vertex-edge domination number can be found in [1,11,7].
Our aim in this work, is to apply the analogue of vertex-edge on locating Roman domination and establish the variation vertex-edge locating Roman domination as follows.
A vertex-edge locating Roman dominating function of a graph \(G\), abbrevated \(ve\)-LRD function is a function \(f:V(G)\rightarrow \{0,1,2\}\) satisfying the conditions that (i) every adjacent vertices \(u,v\) with \(u\in V_0\) or \(v\in V_0\), there exists a vertex \(w\in V_2\) such that \(w\in N(u)\cup N(v)\); (ii) \(max\{f(u),f(v)\}\neq 0\) for every edge \(uv\in E\); and (iii) for any pair of distinct vertices \(u,v\) of \(V_0\), \(N(u)\cap V_2\neq N(v)\cap V_2\).
In Section 2, we show that the vertex-edge locating Roman domination is NP complete for bipartite graphs and in Section 3, we present the upper and lower bonds of \(ve\)-LRD function for trees. In section 4, we presented the \(ve\)-LRD function of complete graphs and upper bounds of \(ve\)-LRD function for some connected graphs.
In this section, we examine the computational complexity of the vertex-edge locating Roman domination (ve-LRD) problem in bipartite graphs. Formally, the ve-LRD problem is defined as follows: given a graph \(G = (V, E)\) and a positive integer \(k \leq |V|\), the task is to determine whether \(G\) admits a vertex-edge locating Roman dominating function of weight at most \(k\). To prove that this problem is NP-complete, we present a polynomial-time reduction from the well-known NP-complete problem, Exact 3-Cover (X3C). In the X3C problem, the input consists of a finite set \(X\) with \(|X| = 3q\) and a collection \(C\) of 3-element subsets of \(X\). The goal is to determine whether there exists a subcollection \(C' \subseteq C\) such that every element of \(X\) appears in exactly one member of \(C'\). By constructing an appropriate bipartite graph from a given instance of X3C and showing that the existence of a solution to the ve-LRD problem corresponds to the existence of an exact 3-cover, we establish that the ve-LRD problem is NP-complete, even when restricted to bipartite graphs.
Theorem 2.1. \(ve-LRD\) is \(NP\)-complete for bipartite graphs.
Proof. \(ve\)-LRD is NP since it can be check in polynomial time that the function \(f:V \rightarrow \{0,1,2\}\) is an ve-LRD and has weight at most \(k\). Given an instance \((X,C)\) of \(X3C\) with \(X=\{x_1,x_2,…,x_{3q}\}\) and \(C=\{C_1,C_2,…,C_t\}\).
Bipartite graph \(G\) can be constructed as follows: for any \(x_i\in X\), create a single vertex \(x_i\). A tree \(T_j\) can be built for any \(C_j\in C\) which comprises of paths \(P_6=\{u_j,v_j,w_j,y_j,z_j,c_j\}\) and \(Q=\{r_1,…r_t\}\) such that edges \(r_jz_j\) are added to \(P_{j6}\). To achieve the construction of \(G\), we add edges \(c_jx_i\) when \(x_i\in C_j\) (see Figure 1). Set \(k=5t+q\). Observe that for every ve-LRD, each \(P_6\) has weight at least \(5\). The leaf neighbor \(r_j\) of \(z_j\), \(w_j\) and \(c_j\) has weight \(0\), while vertices \(u_j,v_j\) and \(z_j\) are assign \(1\) and \(y_j\) must be assigned \(2\).
Suppose \(C'\) is a solution of the instance \((X,C)\) of \(X3C\). Then ve-LRD function \(f\) on \(G\) of weight \(k\) can be constructed as follows: Assign value \(0\) to \(x_i\) for each \(i\), then for each \(j\), if \(C_j\in C'\), assign value \(2\) to vertex \(z_j\), value \(0\) to vertex \(w_j\) and \(1\) to the remaining vertices of \(P_{j6}\). Also, assign \(0\) to the vertices of \(Q_j\).
If \(C_j\notin C'\), assign \(2\) to vertex \(y_j\) in each \(P_{j6}\), assign \(0\) to vertices \(w_j,c_j\) and the set \(Q_j\). Assign \(1\) to the remaining vertices of \(P_{j6}\).
Note that since \(C'\) exists, the order of \(C'\) is \(q\) and so the number of \(c_j\) with value \(1\) is \(q\) and every vertex in \(X\) is at distance two to vertex \(z_j\) with value \(2\). Therefore, \(f\) is ve-LRD with weight \(f(V)=5t+q=k\).
Conversely, suppose that \(G\) has ve-LRD function with weight at most \(k\). Let \(\alpha=(V_0,V_1,V_2)\), observe from above, each \(P_{j6}\) has weight at least \(5\). We may assume that \(\alpha(z_j)=2\) if \(C_j\in C'\) and \(\alpha(y_j)=2\) if \(C_j\notin C'\). It is clear that vertices of \(P_{j6}\) with value \(0\) is at distance two or one from the vertex assign \(2\) such that any pair of vertices with value \(0\) does not have a common neighbor assign \(2\) under \(\alpha\). Now since \(w(\alpha)\leq 5t+q\), we can see that \(X\cap V_0\neq \phi\). If \(\alpha(x_i)>0\) for some \(i\), then this provides an ve-LRD function of weight at most \(k\) with weight greater than \(\alpha\). Therefore \(X\subset V_0\). Now, since each vertex of \(X\) is at distance two from a vertex in \(V_2\) and the sum of end points of each edge must be greater than \(0\), each \(\alpha\) has exactly three neighbors in \(\{x_1,x_2,…,x_{3q}\}\). This will be possible only if there are \(q\) vertices \(z_j\) of \(T_j\) that are assign \(2\) and \(q\) vertices \(c_j\) of \(T_j\) that are assign \(1\). We conclude that \(C'=\{C_j:\alpha(c_j)=1\}\) is an exact cover for \(C\). ◻
In this section, we gave the lower and upper bounds of \(ve\)-LRD function of tree \(T\) in terms of \(s\) support vertices. Note that the core internal vertices \(i=n-l-s\). We begin with the following result.
Proposition 3.1. For \(n\geq 3\), \[\begin{aligned}\gamma_{veLR}(P_n)=\begin {cases} \frac{4n+k}{5}, &\text { if } n\equiv k\mod 5 \text{ and } k\neq 4,\\ \frac{4n+k}{5}-1, & \text{ if } n\equiv k \mod 5 \text { and } k=4. \end{cases}\end{aligned}\]
Proof. Let \(P_n=u_1,u_2,…,u_n\) be a path of order \(n>2\). Let \(f\) be a function defined on the \(V(P_n)\) as \(f:V(P_n)\rightarrow \{0,1,2\}\). The problem can be split into the following two cases.
Case 1. If \(n\equiv k\mod 4, 0\leq k\leq 3\). The function \(f\) is define as \[f(u_j)=\begin{cases}0, & \text{ if } j\equiv 1 \text{ or } 4\mod 5 \text{ and } j<n-k,\\ 1, & \text { if } j\equiv 0 \text { or }2\mod 5, j<n-k \text{ and } n-(k+1)\leq j\leq n,\\ 2, & \text{ if } j\equiv 3 \mod 5 \text { and } j<n-k. \end{cases}\]
Case 2. If \(n\equiv k \mod 5\) and \(k=4\). Define \(f\) on \(V(P_n)\) as follows: \[f(u_j)=\begin{cases}0, & \text{ if } j=n-3,n,\\ 1, & \text { if } j=n-2,\\ 2, & \text{ if } j=n-1,\\ f(u_j)\ \ \ \text{in case 1 above}, & \text{ otherwise. } \end{cases}\]
Clearly, \(f\) is a ve-LRD of \(P_n\) and thus \[\gamma_{veLR}(P_n)\leq \begin {cases} \frac{4n+k}{5}, & \text { if } n\equiv k\mod5 \text{ and } k\neq 4,\\ \frac{4n+k}{5}-1, & \text{ if } n\equiv k\mod5 \text { and } k=4. \end{cases}\]
To proof the inverse inequality, we establish it by induction on \(n\). Let \(P'\) be the a path obtained from path \(P_n\) by removing one vertex (say \(u_n\)) from the path \(P_n\). Then \(P'\) is a path of order \(n'=n-1\). If \(f(u_n)\geq 1\), then the retriction of \(f\) on \(P'\) will give ve-LRD on \(P'\) , that is \(w(f)\geq \gamma_{veLR}(P')+1\). Thus, if \(k\neq 4\), \[\begin{aligned} w(f) &\geq \gamma_{veLR}(P')+1 =\frac{4n'+k'}{5}+1 =\frac{4(n-1)+k-1}{5}+1 = \frac{4n+k}{5}. \end{aligned}\]
If \(k=4\), we have \[\begin{aligned} w(f) &\geq \gamma_{veLR}(P')+1 =\frac{4n'+k'}{5}-1+1 =\frac{4(n-1)+k-1}{5}-1+1 = \frac{4n+k}{5}-1. \end{aligned}\]
Thus, \[\gamma_{veLR}(P_n)\geq \begin {cases} \frac{4n+k}{5}, & \text { if } n\equiv k\mod 5 \text{ and } k\neq 4,\\ \frac{4n+k}{5}-1, & \text{ if } n\equiv k \mod 5 \text { and } k=4. \end{cases}\]
Using the induction hypothesis, we get the desired lower bound. Hence, the equality holds. ◻
Observation 3.2. For any star graph \(S_n\), \(\gamma_{veLR}(S_n)=3\).
Theorem 3.3. If \(T\) is a tree of order \(n\geq 6\) with \(l\) leaves, \(s\) support vertices, \(i\) core internal vertices with \(i\leq 2s\) and \(T\) is not a path, then \(\gamma_{veLR}(T)\leq 3s\).
Proof. We establish the proof by induction on \(n\). Assume that \(diam(T)\geq 4\), let \(u_0,…,u_t\) be a diametral path . Then \(u_0\) and \(u_t\) are the root and leaf respectively and \(u_{t-1}\) is a support vertex. We split the proof into the following cases:
Case 1. \(d(u_{t-1})\geq 3\). Then \(u_{t-1}\) is adjacent to atleast two leaves. Let \(T'\) be the tree obtained from \(T\) by deleting \(u_t\). Then \(T'\) has order \(n'=n-1\) with \(l'=l-1\), \(s'=s\) and \(i'=i\). By induction hypothesis, \(T'\) admits \(ve\)-LRD function \(f'\) such that \(w(f')\leq 3s'=n'-l'+2s'-i'\), since \(i'=n-l'-s'\). Define a function \(f:V(T) \rightarrow \{0,1,2\}\) as follows:
If \(f'(u_{t-2})=2\) or \(f'(u_{t-1})\geq 1\), set \(f(u_t)=0\) and \(f(x)=f'(x)\) for all \(x\in T-u_t\), if \(f'(u_{t-2})<2\) and \(f'(u_{t-1})\leq 1\), then \(u_{t-1}\) is adjacent to a leaf \(y\) in \(T'\) with \(f'(y)\geq 1\), set \(f(u_{t-2})=2,f(u_{t-1})=1\) and \(f(y)=f(u_t)=0\). Also, \(f(v)=f'(v)\) for all \(v\in T-\{u_{t-2},u_{t-1},u_t,y\}\). Then \(f\) is a ve-LRD function on \(T\) of weight \[\begin{aligned} w(f) &\leq w(f')\\ & \leq n'-l'+2s'-i'\\ & =n-1-l+1+2s-i\\ & =n-l+2s-i\\ & =n-l+2s-(n-l-s)=3s. %\frac{4n+k}{5}-1. \end{aligned}\] Thus the statement is true.
Case 2. If \(d(u_{t-1})=2\).
Subcase 1. If \(d(u_{t-2})=2\). Let \(T'\) be the tree obtained from \(T\) by deleting \(u_{t-1}\) and \(u_t\). Then \(n'=n-2,l'=l, s'\leq s\) and \(i'\leq i\). \(T'\) admits ve-LRD function \(f'\) by induction hypothesis such that \(w(f')\leq 3s'=n'-l'+2s'-i'\). Define \(f:V(T)\rightarrow \{0,1,2\}\) by \(f(u_{t-1})=f(u_t)=1\) and \(f(x)=f'(x)\) for all \(x\in T-\{u_{t-1},u_t\}\). The assignment gives a ve-LRD function \(f\) on \(T\) with weight \[\begin{aligned} w(f) &= w(f')+2\\ & \leq n'-l'+2s'-i'+2\\ & \leq n-2-l+2s-i+2\\ & = n-l+2s-i\\ & =n-l+2s-(n-l-s)=3s. \end{aligned}\]
Therefore, the statement holds.
Subcase 2. \(d(t_{t-2})\geq 3\).
Let \(T'\) be the tree obtained from \(T\) by deleting \(u_{t-1}\) and \(u_t\). Then \(n'=n-2,l'=l-1, s'\leq s\) and \(i'=i\). By induction hypothesis, \(T'\) admits a ve-LRD function \(f'\) with \(w(f')\leq 3s'= n'-l'+2s'-i'\). Define function \(f\) in \(T\) as follows: If \(f'(u_{t-2})=1\) and \(f'(u_{t-3})=2\), set \(f(u_{t-1})=0\) and \(f(u_t)=1\). Also, if \(f'(u_{t-3})=2\) and \(f'(u_{t-2})=0\), set \(f(u_{t-1})=1\) and \(f(u_t)=0\). If \(f'(u_{t-3})=1\) and \(f'({t-2})=2\), set \(f(u_{t-1})=1\) and \(f(u_t)=0\). Therefore, the labeling gives a ve-LRD function \(f\) on \(T\) with weight \[\begin{aligned} w(f) &= w(f')+1\\ & \leq n'-l'+2s'-i'+1\\ & \leq n-2-l+1+2s-i+1\\ & = n-l+2s-i\\ & =n-l+2s-(n-l-s)=3s. \end{aligned}\] ◻
Theorem 3.4. If \(T\) is a treee with \(diam(T)\geq 4\), \(l\) leaves, \(s\) support vertices and \(i\) core internal vertices, then \(\gamma_{veLR}(T)\geq s\).
Proof. We use induction on \(n\) to establish the proof. Assume that \(|T|\geq 5\) and \(i=n-l-s\), let \(T'\) be an arbitrary tree of order \(n'\) such that \(|T'|<|T|\) with \(diam(T')\geq 3\). Assume that the statement is true for any tree \(T'\). Also, let \(l',s',i'\) be the order of leaves, support vertices and core internal vertices in \(T'\) respectively. Assume that \(diam(T)\geq 4\). Let \(u_0,…,u_t\) be a diametral path and \(f\) a ve-LRD function on \(T\) with minimum weight, that is \(w(f)=\gamma_{veLR}(T)\)
Claim 1. If \(d(u_1)>2\), then the statement is true.
Proof. The vertex \(u_1\) is adjacent to atleast two vertices \(u_0\) and say leaf \(y\). Let \(T'\) be the tree obtained from \(T\) by deleting \(y\). Then \(n'=n-1, l'=l-1,s'=s\) and \(i'\geq i\). Define a function \(f:V(T)\rightarrow \{0,1,2\}\) on \(T\) and \(f'\) is a function define on \(T'\). If \(f'(u_1)=1\) and \(f'(u_0)=2\) or \(f'(u_2)=2\), set \(f(y)=0\). Then the restriction of \(f\) on \(T'\) is a ve-LRD function on \(T'\), that is \(w(f)\geq \gamma_{veLR}(T')\). If \(f'(u_1)=0\) and any of the vertices \(u_j, j=0,2,3\) is assign \(2\), set \(f(y)=1\). If \(f'(u_1)=2\) and \(f(u_0)=0\) or \(f'(u_2)=0\) or \(f'(u_3)=0\), set \(f(y)=1\). The restriction of \(f\) on \(T'\) is a ve-LRD function on \(T'\), so \(w(f)\geq \gamma_{veLR}(T')\). Therefore in all cases, we have \[\begin{aligned} w(f) &\geq w(f')\\ & \geq \frac{n'-l'+s'-i'}{2}\\ & \geq \frac{n-1-l+1+s-i}{2}\\ & = \frac{n-l+s-i}{2}\\ & = \frac{n-l+s-(n-l-s)}{2}=s. \end{aligned}\] ◻
Let assume that \(d(u_1)=2\).
Claim 2. If there exist \(j\in \{2,..,t-2\}\) such that \(u_j\) is a support vertex in \(T\), then the statement is true.
Proof. Let denote the leaf adjacent to \(u_i\) in \(T\) by \(z\). Let \(T'\) be the tree obtained from \(T\) by deleting \(z\). Then \(n'=n-1, l'=l-1, s'\leq s\) and \(i'\geq i\). By induction hypothesis, \(\gamma_{veLR}(T')\geq \frac{n'-l'+s'-i'}{2}\), since \(i'=n'-l'-s'\). If \(f'(u_i)=1\) and \(f'(u_{i-1})\) or \(f'(u_{i+1})=2\), then set \(f(z)=0\). The restiction of \(f\) on \(T'\) is a ve-LRD function on \(T'\); so \(w(f)\geq \gamma_{veLR}(T')\). If \(f'(u_i) =0\), set \(f(z)=1\). If \(f'(u_i)=2\) and either \(f'(u_{i-1})\) or \(f'(u_{i+1})\) or \(f'(u_{i+2})=0\), set \(f(z)=1\) and \(f'=f\) otherwise. If neither \(f'(u_{i-1})\) nor \(f'(u_{i+1})\) nor \(f'(u_{i+2})=0\) and \(f'(u_i)=2\), set \(f(z)=0\) and \(f'=f\) otherwise. Thus \(w(f)\geq w(f')\geq \gamma_{veLR}(T')\). If there exist \(v\in N(u_j )\setminus \{z\}\) with \(f'(v)=2\), set \(f(z)=0\), the restriction of \(f\) on \(T'\) is a ve-LRD function on \(T'\), so \(w(f)\geq \gamma_{veLR}(T')\). Therefore, in all cases we have \[\begin{aligned} w(f) &\geq \gamma_{veLR}(T')\\ & \geq \frac{n'-l'+s'-i'}{2}\\ & \geq \frac{n-1-l+1+s-i}{2}\\ & = \frac{n-l+s-i}{2}\\ & = \frac{n-l+s-(n-l-s)}{2}=s. \end{aligned}\] Thus, the statement holds. ◻
Assume that the set \(\{u_0,…,u_t\}\) does not have a support vertex in \(T\). Then we have the following two cases:
Case 1. \(d(u_2)>2\).
Vertex \(u_2\) is adjacent to a support vertex say \(y\) since \(u_2\) is not adjacent to any leaf and the path \(\{u_0,…,u_t\}\) is the diametral path. Note that \(y\notin \{u_1,u_3\}\) and \(y\) is adjacent to a leaf \(z\). Let \(T'\) be a tree obtained from \(T\) by deleting vertices \(y\) and \(z\). Then \(diam(T')=diam(T)\), \(n'=n-2, l'=l-1, s'=s-1\) and \(i'=i\). If \(f(u_2)\geq 1\), then the restriction of \(f\) on \(T'\) will give a ve-LRD function on \(T'\), i.e., \(w(f)\geq \gamma_{veLR}(T')\). If \(f'(u_2)=0\), then \(f(y)+f(z)>1\). Define a ve-LRD function \(f\) on \(T\) as follows: If \(f'(u_2)=1\) and either \(f'(u_1)\) or \(f'(u_3)=2\), set \(f(y)=0\), \(f(z)=1\) and \(f'=f\) otherwise. Also, if \(f'(u_2)=2\), set \(f(y)=1\) and \(f(z)=0\). If \(f'(u_2)=0\), set \(f(y)=f(z)=1\) and \(f'=f\) otherwise. Thus in all cases, we have \[\begin{aligned} w(f) &\geq \gamma_{veLR}(T')+1\\ & \geq \frac{n'-l'+s'-i'}{2}+1\\ & \geq \frac{n-2-l+1+s-1-i}{2}+1\\ & = \frac{n-l+s-i}{2}\\ & = \frac{n-l+s-(n-l-s)}{2}=s. \end{aligned}\]
Thus the statement holds.
Case 2. \(d(u_2)=2\).
If \(diam(T)=4\), then \(T=P_5\) and by Proposition 3.1, \(\gamma_{veLR}(P_5)=4> s\). Let assume that \(diam(T)\geq 5\). Let \(T'\) be the tree obtained from \(T\) by deleting vertices \(u_0\) and \(u_1\). So \(diam(T')\geq 3\). Also, \(n'=n-2, l'=l,s'=s\) and \(i'=n'-l'-s'\leq i\). Assume that \(f(u_0)+f(u_1)\geq 1\) and the restriction of \(f\) on \(f'\) is a ve-LRD function on \(T'\) with \(w(f')\geq s'= \frac{n-l+s-i}{2}\). Define \(f\) on \(T\) as follows: If \(f'(u_2)=2\), set \(f(u_1)=1\), \(f(u_0)=0\) and \(f=f'\) otherwise. If \(f'(u_2)=1\) and \(f'(u_3)=2\), set \(f(u_1)=0\) and \(f(u_0)=1\), \(f'=f\) otherwise. Also, If \(f'(u_2)=1\) and \(f'(u_3)\neq 2\), set \(f(u_0)=f(u_1)=1\) and \(f=f'\) otherwise. If \(f'(u_2)=0\), set \(f(u_0)=f(u_1)=1\) and \(f=f'\) otherwise. Therefore, in all cases above, we have \[\begin{aligned} w(f) &\geq \gamma_{veLR}(T')+1\\ & \geq \frac{n'-l'+s'-i'}{2}+1\\ & \geq \frac{n-2-l+s-i }{2}+1\\ & = \frac{n-l+s-i}{2}\\ & = \frac{n-l+s-(n-l-s)}{2}=s. \end{aligned}\]
Thus, the statement holds. ◻
In this section, we gave the vertex-edge locating domination number of complete graphs and upper bound for the vertex-edge locating domination number of connected graphs. We begin with the following result on ve-LRD function of connected graphs.
Lemma 4.1. Let \(G\) be a connected graph of order \(n>3\) and \(G\neq K_n\). If \(v\in V(G)\) with \(d(v)\geq 2\), then \(\gamma_{veLR}(G)\leq n-1\).
Proof. Let \(u_1,u_2\in N_2(v)\) and let \(v_1\in N(v)\cap N(u_1)\) and \(v_2\in N(v)\cap N(u_2)\) such that \(\{u_1,v_1,v,v_2,u_2\}\) is a path in \(G\). If \(v\) has a leaf neighbor say \(x\), the function \(f:V(G)\rightarrow \{0,1,2\}\) defined by \(f(v_2)=2\), \(f(v_1)=f(x)=f(u_2)=0\) and \(f(y)=1\) for \(y\in V(G)\setminus \{v_1,v_2,x,u_2\}\) is a ve-LRD function on \(G\) with weight \(n-1\). Therefore, \(\gamma_{veLR}(G)\leq n-1\).
If only \(v_1\) has leaf neighbor say \(x\in l_{v_1}\), then define \(f:V(G)\rightarrow \{0,1,2\}\) by \(f(v)=2\), \(f(x)=f(u_1)=f(v_2)=0\) and \(f(y)=1\) for \(y\in V(G)\setminus \{v,x,u_1,v_2\}\). The function \(f\) define above is a ve-LRD function on \(G\) with \(w(f)\leq n-1\).
If only \(v_2\) has a leaf neighbor, say \(x\in l_{v_2}\), then define \(f:V(G)\rightarrow \{0,1,2\}\) by \(f(v)=2\), \(f(x)=f(v_1)=f(u_2)=0\) and \(f(z)=1\) for \(z\in V(G)\setminus \{v,x,v_1,u_2\}\). The function \(f\) gives a ve-LRD function with \(w(f)\leq n-1\). If \(u_1\) and \(u_2\) has leaves neighbors, say \(x\in l_{u_1}\cup l_{u_2}\), define function \(f:V(G)\rightarrow \{0,1,2\}\) by \(f(u_1)=f(u_2)=2\), \(f(x)=f(v)=0\) and \(f(t)=1\) for \(t\in V(G)\setminus \{u_1,u_2,x,v\}\). The function gives ve-LRD function with \(w(f)\leq n-1\). Thus \(\gamma_{veLR}(G)\leq n-1\). ◻
Corollary 4.2. If \(T\) is a tree of order \(n>3\), then \(\gamma_{veLR}(T)\leq n-1\).
Theorem 4.3. Let \(G\) be a connected graph of order \(n\geq 2\), then \(\gamma_{veLR}(G)=n\) if and only if \(G=P_3,K_n\).
Proof. Obviously, if \(G=P_3\), \(\gamma_{veLR}(P_3)=3\) by Proposition 3.1. Now let \(G=K_n\). Suppose \(\gamma_{veLR}(G)=n\), then this implies that all vertices in \(G\) are adjacent , that is, \(G=K_n\). Suppose all vertices in \(G\) are not adjacent . Let \(u,v\in V(G)\) such that \(uv\notin E(G)\). Then \(d(v)\leq n-2\) and \(u,v\) are at distance \(2\) from each other. Let vertex \(x\in N(u)\cap N(v)\) in \(G\). Since \(G\) is connected with \(n\geq 3\), then \(uxv\) is a path of length \(2\) and the function \(f\) define on \(V(G)\setminus \{v\}\) is a ve-LRD function in \(G\) which implies that \(\gamma_{ve-LR}{G}\leq n-1\), a contradiction.
Assume that \(G=K_n\), then all the vertices are adjacent. For \(u,v\in V(G)\), define the function \(f:V(G)\rightarrow \{0,1,2\}\) by \(f(u)=2,f(v)=0\) and \(f(y)=1\) for \(y\in V(G)\setminus\{u,v\}\). The above function \(f\) gives ve-LRD function of \(G\) with weight \(n\). Therefore, \(\gamma_{veLR}(G)=n\). ◻
Corollary 4.4. Let \(G\) be a connected graph of order \(n\) such that \(\gamma_{veLR}(G)=n\), then \(diam(G)\leq 2\).
Proof. We establish the proof by contradiction. Assume that \(diam(G)\geq 3\) and let \(P=u_1,u_2,…,u_d\) be a diametral path in \(G\). The vertices \(\{u_2,u_6\}\in N_2(u_4)\) which implies that \(d(u_2)\geq 2\) and by Lemma 4.1, \(\gamma_{veLR}(G)\leq n-1\). This is a contradiction. ◻
Theorem 4.5. Let \(G\) be a cycle of order \(n\geq 3\), then \(\gamma_{veLR}(G)=\frac{4n+k}{5}\), \(n\equiv (k \mod 5)\).
Proof. Applying Proposition 3.1 (Case \(1\)) for all values of \(k\) gives the desired result. ◻