Dipayan Chakraborty

Florent Foucaud

Anni Hakanen

Michael A Henning

Annegret K Wagler

Progress towards the two-thirds conjecture on locating-total dominating sets *

We study upper bounds on the size of optimum locating-total dominating sets in graphs. A set S of vertices of a graph G is a locating-total dominating set if every vertex of G has a neighbor in S, and if any two vertices outside S have distinct neighborhoods within S. The smallest size of such a set is denoted by γ L t (G). It has been conjectured that γ L t (G) ≤ 2n 3 holds for every twin-free graph G of order n without isolated vertices. We prove that the conjecture holds for cobipartite graphs, split graphs, block graphs, subcubic graphs and outerplanar graphs.

Introduction

Our aim is to study upper bounds on the smallest size of locating-total dominating sets in graphs. This notion is part of the extended research area of identification problems in graphs and, more generally, discrete structures like hypergraphs. In this type of problems, one seeks to select a small solution set, generally vertices of a graph, in order to uniquely identify each vertex of the graph by its relationship with the selected vertices. More precisely, given a set D of vertices of a graph G, we say that two vertices v and w of G are located by D if they have distinct sets of neighbors in D. Various notions based on this location property have been studied, such as locating-dominating sets [START_REF] Slater | Dominating and reference sets in graphs[END_REF], identifying codes [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF] or separating sets [START_REF] Bollobás | On separating systems[END_REF], to name a few. We refer to the online bibliography on these topics maintained by Lobstein [START_REF] Lobstein | Watching systems, identifying, locating-dominating and discriminating codes in graphs: a bibliography[END_REF] (almost 500 references by the time of writing, in 2022). This type of problems have a wide range of applications, such as fault-detection in sensor or computer networks [START_REF] Karpovsky | On a new class of codes for identifying vertices in graphs[END_REF][START_REF] Ungrangsi | An implementation of indoor location detection systems based on identifying codes[END_REF], biological testing [START_REF] Moret | On minimizing a set of tests[END_REF], machine learning [START_REF] Bonnet | On the parameterized complexity of red-blue points separation[END_REF], or canonical representations of graphs [START_REF] Babai | On the complexity of canonical labeling of strongly regular graphs[END_REF][START_REF] Kim | How complex are random graphs in First Order logic? Random Struct[END_REF], to name a few.

In this paper, we study the notion of a locating-total dominating set. A set D of vertices is a total dominating set, abbreviated TD-set, of a graph G if every vertex in G has a neighbor in D. Total dominating sets are a natural and widely studied variant of the domination problem in graphs. We refer to the book [START_REF] Henning | Total domination in graphs[END_REF] for an overview on the topic. A locating-total dominating set of G is a TD-set D ⊂ V (G) such that any two vertices of G not in D are located by D. The smallest size of such a locating-total dominating set of a graph G is called the locating-total domination number of G and is denoted by γ L t (G). A graph admits a (locating-)total dominating set if and only if it has no isolated vertex. We abbreviate a locating-total dominating set by LTD-set, and we say that a γ L t -set of G is a LTD-set of minimum cardinality, γ L t (G), in G. The concept of a locating-total dominating set was first considered in [START_REF] Haynes | Locating and total dominating sets in trees[END_REF], based on the similar concept of a locating-dominating set (where total domination is replaced with usual domination) introduced by Slater in the 1980s [START_REF] Slater | Dominating and reference sets in graphs[END_REF]. It was studied for example in [START_REF] Argiroffo | The Identifying Code, the Locatingdominating, the Open Locating-dominating and the Locating Total-dominating problems under some graph operations[END_REF][START_REF] Argiroffo | Polyhedra associated with open locatingdominating and locating total-dominating sets in graphs[END_REF][START_REF] Blidia | Locating-domination and identifying codes in trees[END_REF][START_REF] Blidia | A characterization of locating-total domination edge critical graphs[END_REF][START_REF] Blidia | Locating-domination, 2-domination and independence in trees[END_REF][START_REF] Chellali | On locating and differentiating-total domination in trees, Discuss[END_REF][START_REF] Chellali | Locating-total domination critical graphs[END_REF][START_REF] Chen | Bounds on the locating-total domination number of a tree[END_REF][START_REF] Foucaud | Locating-total dominating sets in twin-free graphs: a conjecture[END_REF][START_REF] Foucaud | Location-domination in line graphs[END_REF][START_REF] Henning | Locating-total domination in claw-free cubic graphs[END_REF][START_REF] Henning | Locating-total domination in graphs[END_REF]. The Observation 2. If a graph G of order n is a triangle, a 6-cycle or a 2-corona of any graph, then γ L t (G) = 2 3 n. A graph is cobipartite if its vertex set can be partitioned into two cliques, and split if it can be partitioned into a stable set (also called an independent set in the literature) and a clique. A graph is a block graph if every 2-connected component forms a clique. A graph is subcubic if each vertex has degree at most 3. A graph is outerplanar if it can be embedded in the plane without any edge-crossing, so that all vertices lie on the same face of the embedding.

In this paper, we give further evidence towards Conjecture 1, by showing that it holds for cobipartite graphs (Section 2), split graphs (Section 3), block graphs (Section 4), subcubic graphs (Section 5) and outerplanar graphs (Section 6). We conclude in Section 7.

Some of our results are actually slightly stronger. Indeed, the proved upper bound for cobipartite graphs is in fact ⌈ n 2 ⌉ (which is tight). For twin-free split graphs, we show that the 2n 3 bound of the conjecture can never be reached. However, we construct infinitely many connected split graphs that come very close to the bound; this is interesting in its own right, showing that not only 2-coronas have such large locating-total domination numbers. Moreover, the bound for subcubic graphs is proved to hold for all subcubic graphs, even if they have twins.

We now introduce some of the notations used in the paper. The open and closed neighborhoods of a vertex v in a graph G are denoted N G (v) and N G [v], respectively (or N (v) and N [v] if G is clear from the context). We denote by deg G (v) the degree of the vertex v in the graph G, that is, deg

G (v) = |N G (v)|. The distance in G between two vertices u, v is denoted d G (u, v).
If two graphs G and H are isomorphic, we note G ∼ = H. For a graph G with a vertex or edge x, we denote by G -x the subgraph of G obtained by removing x, and by G + x the supergraph of G obtained by adding x. Similarly, if X is a set of vertices and edges, we use the notations G -X and G + X for the subgraph and supergraph of G obtained by deleting or adding all the elements of X. A leaf is a vertex of degree 1, and its unique neighbor is called a support vertex. We denote by δ(G) and ∆(G) the minimum and maximum degree, respectively, in the graph G. We denote a path, a cycle, and a complete graph on n vertices by P n , C n , and K n , respectively.

Cobipartite graphs

We now prove a stronger variant of the bound of Conjecture 1, whose proof is a refinement of a similar proof for the (non-total) locating-domination number from [START_REF] Foucaud | Locating-dominating sets in twin-free graphs[END_REF]. The bound is tight for complements of half-graphs, which are graphs made from two cliques of the same size [START_REF] Foucaud | Locating-dominating sets in twin-free graphs[END_REF]Definition 5] and whose locating(-total) domination number is equal to n 2 . Theorem 3. For any twin-free cobipartite graph G of order n, we have γ L t (G) ≤ ⌈ n 2 ⌉. Proof. Note that G is connected (as a disconnected cobipartite graph is the disjoint union of two cliques, and thus not twin-free: it either has closed twins if one of the cliques has order at least 2, or is a pair of open twins if both cliques have order 1). Let C 1 and C 2 be two cliques of G that partition its vertex set. Since G is twin-free, both C 1 and C 2 have size at least 2 (assume that |C 1 | ≤ |C 2 |). Moreover, no two vertices of C 1 have the same neighborhood in C 2 , and vice-versa. Thus, if any of C 1 , C 2 is a TD-set, then it is also an LTD-set. Thus, if C 1 is a TD-set, we are done, as

|C 1 | ≤ ⌊ n 2 ⌋. If however C 1 is not a TD-set, it means that some vertex v of C 2 has no neighbor in C 1 ; this vertex is unique since G is twin-free.
If moreover, there is a vertex w in C 1 with no neighbor in C 2 , we select D = (C 1 \ {w}) ∪ {x} as a solution set, where x ̸ = v is any vertex of C 2 other than v. This set is clearly a TD-set. Any two vertices from C 2 are located, as v is only dominated by x, and any two other vertices from C 2 \ {x} have a distinct and nonempty neighborhood within C 1 (and thus, within

C 1 \ {w}). Moreover, w is the only vertex not in D not dominated by x. Hence, D is an LTD-set. Since |D| = |C 1 | ≤ ⌊ n
2 ⌋, we are done. Otherwise, every vertex of C 1 has a neighbor in C 2 , and so C 2 is a TD-set and, in fact, as seen previously, an LTD-set. Thus, if |C 2 | ≤ ⌈ n 2 ⌉, we are done. Otherwise, we have |C 1 | < ⌊ n 2 ⌋, and thus

|C 1 | + 1 ≤ ⌈ n 2 ⌉.
Moreover, by similar arguments as in the previous paragraph, the set C 1 together with any vertex of C 2 other than v produces a LTD-set of size |C 1 | + 1, and we are done.

Split graphs

Consider a split graph G = (Q ∪ S, E) where Q induces a clique and S a stable set. We suppose that G is isolate-free to ensure the existence of an LTD-set in G, which further implies that G is connected and Q non-empty (as every component not containing the clique Q needs to be an isolated vertex from S). Theorem 4. For any twin-free isolate-free split graph G = (Q ∪ S, E) of order n, we have γ L t (G) < 2 3 n. Proof. First, note that we have |Q|, |S| ≥ 2 as otherwise G is a single vertex or not twin-free.

Observe next that Q is an LTD-set of G since Q is a TD-set and no two vertices in S have the same neighbors in Q (as G is twin-free) showing that Q is also locating. Hence, the assertion is true if |Q| < 2 3 n. Consider now a set D consisting of all vertices in S and, for each s ∈ S, some arbitrary neighbor q s ∈ Q (which exists since G is connected). The set D is an LTD-set of G since D is a TD-set and no two vertices in Q \ D have the same neighbors in S (as G is twin-free) implying that D is also locating. Hence, the assertion is true if |Q| > 2 3 n and, thus,

|S| < 1 3 n and |D| = 2|S| < 2 3 n. It is left to consider the case |Q| = 2
3 n and |S| = 1 3 n. We observe that any set D constructed as above is an LTD-set of G, and we are going to show that it is not minimum. In fact, as G is twin-free, there are two vertices s, s ′ ∈ S so that N (s) ∩ N (s ′ ) is non-empty. To see this, observe that otherwise all sets N (s i ) need to be pairwise disjoint, which would imply that either N (s i ) is composed of twins when |N (s i )| ≥ 2 holds, or each set N (s i ) contains exactly one vertex and the 1 3 n vertices in Q without a neighbor in S are twins.

As G is twin-free, none of these cases can happen. Now, the set D ′ obtained from D by replacing q s and q s ′ by a common neighbor q s,s ′ of s and s ′ in Q is an LTD-set of G, indeed: each vertex from S has a neighbor in D ′ , so does every vertex from Q (as all vertices in Q \ {q s,s ′ } have q s,s ′ as a neighbor in D ′ and q s,s ′ has s and s ′ as neighbors in D ′ ) which shows that D ′ is a TD-set; no two vertices in Q \ D ′ have the same neighbors in S (as G is twin-free) which implies that D ′ is also locating. Thus, D ′ is an LTD-set of G of size

|D ′ | = |D| -1 = 2 • |S| -1 = 2 • 1 3 n -1 < 2 3 n ,
which finally proves the assertion.

We next show that the bound of Theorem 4 cannot be improved.

Proposition 5. For each integer k ≥ 3, there is a connected twin-free split graph G k of order n = 3k and

γ L t (G k ) ≥ 2k -1. Proof. Let Q = {q 1 , . . . , q k } ∪ {q ′ 1 , . . . , q ′
k } be a clique and S = {s 1 , . . . , s k } a stable set, so that N (s i ) = {q i , q ′ i } for 1 ≤ i < k and N (s k ) = {q 1 , . . . , q k }. Note that q ′ k has no neighbor in S and that the sets N (s i ) are disjoint for 1 ≤ i < k. See Figure 1 for an illustration.

q 1 q ′ 1 s 1 q 2 q ′ 2 s 2 q k q ′ k s k . . . . . . Q S Figure 1:
The construction of graph G k in the proof of Proposition 5, with an optimal LTD-set (black vertices).

Let C be an LTD-set of G k . Consider the k -

1 closed neighborhoods N [s i ] for 1 ≤ i < k. If we have |N [s i ] ∩ C| ≥ 2 for all i with 1 ≤ i < k, then 1≤i<k (N [s i ] ∩ C) ≥ 2k -2
, and at least one of the remaining vertices s k , q k , q ′ k must belong to C, as otherwise N (q k ) ∩ C = N (q ′ k ) ∩ C would follow, a contradiction. This implies |C| ≥ 2k -1.

If, however, for some i with 1

≤ i < k, we have |N [s i ] ∩ C| = 1, then s i / ∈ C since otherwise s i is not totally dominated by the set C. If N [s i ] ∩ C = {q i }, then N (q ′ i ) ∩ C = Q ∩ C. If N [s i ] ∩ C = {q ′ i }, then N (q i ) ∩ C = (Q ∪ {s k }) ∩ C.
The two possibilities can occur at most once each. Assume that they both occur once each, with

N [s a ] ∩ C = {q ′ a } and N [s b ] ∩ C = {q b } (with 1 ≤ a < b < k).
Note that s k ∈ C, otherwise q a and q ′ b are not located. Moreover, C must contain q ′ k (otherwise q ′ b and q ′ k are not located) and q k (otherwise q a and q k are not located), and so |C| ≥ 2k -1, as claimed.

Similarly, if we have

|N [s i ] ∩ C| ≥ 2 for all i with 1 ≤ i < k except that N [s a ] ∩ C = {q ′ a }, if s k ∈ C, then q k ∈ C, otherwise q a and q k are not located. If s k / ∈ C, then both q k , q ′ k are in C to locate the vertices q a , q k , q ′ k . Thus, again |C| ≥ 2k -1. Finally, if we have |N [s i ] ∩ C| ≥ 2 for all i with 1 ≤ i < k except that N [s b ] ∩ C = {q b }, if s k ∈ C, then q ′ k ∈ C, otherwise q ′ b
and q ′ k are not located. If s k / ∈ C, then both q k , q ′ k are in C to locate the vertices q ′ b , q k , q ′ k , and again |C| ≥ 2k -1. Thus, in all the above cases, we have |C| ≥ 2k -1 and, together with the upper bound γ L t (G k ) <

Block graphs

A block graph is a graph in which every maximal 2-connected subgraph (henceforth referred to as a block ) is complete. Equivalently, block graphs are diamond-free chordal graphs [START_REF] Bandelt | Distance-hereditary graphs[END_REF]. A cut-vertex v of a graph

G is one such that the graph G -v has more components than G. For any block graph G, a leaf block of G is a block that contains only a single cut-vertex of G. In this section, we show that our 2 3 -conjecture (namely, Conjecture 1), holds for block graphs. Trees are a subclass of block graphs in which every block is of order 2. There are some concepts of trees which we use quite often in proving our result for block graphs and we, therefore, define these concepts formally here.

A root of a tree is a fixed vertex of the tree to which the name is designated. Having fixed a root r of a tree T , for any vertex u of T , (1) a child of u is a vertex v of T such that uv is an edge of T and d T (v, r) = d T (u, r) + 1;

(2) a grandchild of u is a vertex w of T such that uv and vw are edges of T and d T (w, r) = d T (u, r) + 2; and

(3) a great-grandchild of u is a vertex x of T such that uv, vw and wx are edges of T and

d T (x, r) = d T (u, r) + 3.
Conversely, the vertex u of T is called the parent, the grandparent and the great-grandparent of v, w and x, respectively. Given any two vertices u and v of a tree T , we say that u is above v in T (or v is below u in T ) if there exists a sequence of vertices

x 1 , x 2 , . . . , x m of T such that, for each i = 1, 2, . . . , m -1, x i+1 is a child of x i in T , where m ≥ 2, x 1 = u and x m = v. Theorem 6. If G ∼ = P 3 or if G is a twin-free isolate-free block graph of order n ≥ 4, then γ L t (G) ≤ 2 3 n. Proof.
Since the locating-total domination number of a graph is the sum of the locating-total domination numbers of each of the components of the graph, it is therefore enough to prove the theorem for a connected twin-free block graph. Thus, let us assume that G is either isomorphic to a 3-path or is a connected twin-free block graph of order n ≥ 4. The proof is by induction on n ≥ 3. The base case of the induction hypothesis is when n = 3, in which case G ∼ = P 3 and γ L t (G) = 2 = 2 3 n. Clearly, any two consecutive vertices of P 3 constitute a minimum LTD-set of P 3 and hence, the result holds for the base case of the induction hypothesis. We now assume, therefore, that n ≥ 4 and that the induction hypothesis is true for all connected twin-free block graphs of order at least 3 and at most n -1. Next, we construct a new graph T G from G in the following way (see Figure 2 for an example of the construction).

For every block B of G, introduce a vertex u B ∈ V (T G ) and for every cut-vertex c ∈ V (G), introduce a vertex v c ∈ V (T G ). Next, introduce edges u B v c ∈ E(T G ) if and only if the cut-vertex c belongs to the block B of G. By construction, therefore, T G is a tree. Thus, the vertices of the tree T G are of two types:

(1) u-type: u B introduced in a one-to-one association with a block B of G; and

(2) v-type: v c introduced in a one-to-one association with a cut-vertex c of G.

Notice that any pair of vertices w, z of the tree T G such that w is the grandparent/grandchild of z in T G are of the same vertex type. For a fixed cut-vertex r ∈ V (G), designate v r ∈ V (T G ) as the root of T G (indeed, such a cut-vertex exists as n ≥ 4 and the twin-free property of G implies that G has at least two blocks). Notice that any leaf of the tree T G is a vertex of the type u B for some leaf block B of G. By the twin-free nature of G every leaf block B of G has order exactly 2. Now, fix a leaf u F of T G that is at the farthest distance, in T G , from the root v r of T G . We now look at the great-grandparent of the leaf u F in the tree T G (indeed, the great-grandparent of u F in T G exists because, on account of G being twin-free, at least one of the blocks of G containing the vertex r has a cut-vertex other than r). Notice that the great-grandparent of u F in T G must be a vertex of the type v p for some cut-vertex p of G. We next define the following.

B p = {B : B is a block of G and u B is either a child or a great-grandchild of v p in T G }; U = ∪ B∈Bp V (B); and A = {x ∈ U : x is a cut-vertex of G}.
We now establish the following two claims related to the sets defined above. )

Claim A. The set A is an LTD-set of G[U ]. r = 1 3 p = 2 B 2 B 1 6 5 B 3 F = B 4 B 5 4 B 6 B 7 (a) u B1 u B2 u B6 u B7 u B3 u F = u B4 u B5 v r = v 1 v p = v 2 v 3 v 4 v 5 v 6 (b)
Proof of claim. That A is a TD-set of G[U ] is clear from the structure of G. We show that A is also a locating set of G[U ]. So, let us assume that vertices w, z ∈ U \ A.
Since G is twin-free, notice that w and z belong to distinct blocks of B p , say B and B ′ , respectively. First, assume that u B and u B ′ are both children of v p in T G . Then, at least one of u B and u B ′ must have a child in T G (or equivalently, at least one of B and B ′ must contain a cut-vertex of G). This is because if none of u B and u B ′ had a child in T G , it would mean that B and B ′ are leaf blocks of G and so, |B| = |B ′ | = 2 (since G is twin-free). That, in turn, would mean that G has open twins (with the leaves of G in the blocks B and B ′ sharing the common support vertex v p ), contrary to our assumption. Thus, if q is a cut-vertex of G in V (B) ∪ V (B ′ ), then q (∈ A) locates w and z. Next, we assume that u B and u B ′ are both great-grandchildren of v p in T G (or equivalently, B and B ′ are both leaf blocks of G). Then, u B and u B ′ have parents v q and v q ′ , say, respectively, in T G , where q ̸ = q ′ due to the fact that G is twin-free. This implies that w and z are located in G by {q, q ′ }. Finally, we assume that u B is a child of v p and that u B ′ is a great-grandchild of v p in T G . Then, w and z are located in G by p. This proves the claim. (2)

Claim B. |U | ≥ 2|A| -1.
Proof of claim. Let u B1 , u B2 , . . . , u Bm be m ≥ 1 children of v p in T G and let each block B i of G be of order n i . Now, due to the twin-free nature of G, each vertex u Bi of T G has at least n i -2 and at most n i -1 children (and hence at least n i -2 and at most n i -1 grandchildren as well). To be more precise, assume that, for 0 ≤ s ≤ m, the vertices u B1 , u B2 , . . . , u Bs have exactly n 1 -2, n 2 -2, . . . , n s -2 children, respectively, in T G ; and that the vertices u Bs+1 , u Bs+2 , . . . , u Bm have exactly n s+1 -1, n s+2 -1, . . . , n m -1 children, respectively, in T G . This implies that we have the following.

|U | = 1 -s + 2 1≤i≤m (n i -1) = 1 -2m -s + 2 1≤i≤m n i .

Moreover, we have

|A| = 1 -s + 1≤i≤m (n i -1) = 1 -m -s + 1≤i≤m n i .
Combining the above two equations, therefore, we have

|U | -(2|A| -1) = s ≥ 0 which proves the claim. (2)
Now, let G ′ = G -U , that is, G ′ is the graph obtained by deleting from G all vertices (and edges incident with them) in the blocks B ∈ B p . Notice that G ′ is still a connected block graph; and assume that the order of G ′ is n ′ (which is strictly less than n). We next divide the proof according to whether G ′ is twin-free, has twins or is isomorphic to a 3-path.

Case 1 (G ′ is either twin-free or is isomorphic to a 3-path). We further subdivide this case into the following.

Subcase 1.1 (n ′ ≤ 2). In this subcase, if n ′ = 2, then the two vertices of G ′ form an edge of G ′ (since G is connected). Hence, the two vertices of G ′ are closed twins of degree 1, contrary to our initial assumption in this case. Therefore, let us assume that n ′ ≤ 1. If n ′ = 1, then v p has no grandparent in T G . In other words, there is no vertex of v-type above v p in T G . This implies that v p must itself be the root vertex of T G . However, this, in turn, implies that G ′ is an empty graph which contradicts the fact that n ′ = 1. Thus, we must have n ′ = 0. In this case too, v p must itself be the root vertex of of T G and so,

G = G[U ] and |U | = n. Therefore, by Claim A, the set A is an LTD-set of G[U ] = G. Moreover, by Claim B, we have |A| ≤ 1 2 (|U | + 1) = 1 2 (n + 1) ≤ 2 3 n,
where the last inequality is true since n ≥ 4.

Subcase 1.2 (n ′ ≥ 3). In this subcase, by the induction hypothesis, we have

γ L t (G ′ ) ≤ 2 3 n ′ . Suppose now that S ′ ⊂ V (G ′ ) is a minimum LTD-set of G ′ , that is with |S ′ | = γ L t (G ′ ).
We then claim that the set S = S ′ ∪ A is an LTD-set of G. To prove so, we first see that the set S is a TD-set of G, since S ′ is a TD-set of G ′ and A is a TD-set of G[U ]. Moreover, S is also a locating set of G due to the following two reasons.

(1) Any two distinct vertices w ∈ V (G ′ ) \ S ′ and z ∈ V (G) \ S are located by S ′ .

(2) By Claim A, the set A is a locating set of G[U ].

Using Claim B, therefore, the two-thirds bound on γ L t (G) in this subcase is established by the following inequality.

γ L t (G) ≤ |S| = |S ′ | + |A| ≤ γ L t (G ′ ) + 2 3 2|A| -1 [since |A| ≥ 2] ≤ 2 3 n ′ + 2|A| -1 ≤ 2 3 n ′ + |U | = 2 3 n.
We next turn to the case that G ′ has twins.

Case 2 (G ′ is neither twin-free nor is isomorphic to a 3-path). Assume that x and y are two vertices of G ′ which are twins in G ′ . Then, without loss of generality, there exists an edge in G between the vertices p and x and there is no edge in G between p and y. This implies that x and p belong to the same block X, say, of G to which y does not belong. Let the block of G to which y belongs be called Y . Next, we prove the following claim.

Claim C. The vertex x also belongs to the block Y of G.

Proof of claim. Toward a contradiction, let us assume that x / ∈ V (Y ). If the blocks X and Y of G had no common vertex in G ′ , by the connectedness of G ′ , it would mean that the symmetric difference of the sets N G ′ (x) and N G ′ (y) is non-empty, and so, x and y would not be twins in G ′ , a contradiction. So, let V (X) ∩ V (Y ) = {v} (note that two blocks of a block graph can intersect at not more than a single vertex). Now, if either of x and y were cut-vertices of G, or if V (X) ∪ V (Y ) contained any vertex other than p, x, v and y, then again, x and y would not be twins in G ′ , the same contradiction as before. This implies that V (G ′ ) = {x, v, y} and that G ′ is isomorphic to a 3-path, again a contradiction to our assumption in this case. Hence, the claim holds. [START_REF] Argiroffo | Polyhedra associated with open locatingdominating and locating total-dominating sets in graphs[END_REF] Now, clearly, X ̸ = Y , or else, py would be an edge in G, contradicting our earlier observation. Thus, x is a cut-vertex of G belonging to the distinct blocks X and Y of G. Moreover, |X| = 2, or else, again, x and y would not be twins in G ′ , a contradiction. More precisely, V (X) = {x, p}. We also observe here that y cannot be a cut-vertex of G, or else, x and y would not be twins in G ′ , again the contradiction as before. Therefore, since G is twin-free, every vertex other than y of the block Y must be a cut-vertex of G.

Now, look at the block graph G ′′ = G ′ -x on, say, n ′′ vertices (the graph induced by the vertices on the right of the dashed curve in Figure 3a). Notice that, in the tree T G , the vertex v x cannot have any children other than u X , or else, x and y cannot be twins in G ′ , contrary to our assumption for this case. This implies that the block graph G ′′ is also connected. We also have y ∈ V (G ′′ ). Thus, n ′′ ≥ 1. However, we claim that n ′′ ̸ = 2.

Claim D. The order n ′′ of the block graph G ′′ cannot be 2.

Proof of claim. Toward a contradiction, let us assume n ′′ = 2 such that z is the vertex of G ′′ other than y. That is, V (G ′′ ) = {y, z} and that yz is an edge of G, by the connectedness of G ′′ . Therefore, y and z belong to the same block Z, say, of G. If Z = Y , then by our observation preceding this claim, the vertex z, being different from y, must be a cut-vertex of G making n ′′ ≥ 3, contradicting our assumption. So, Z and Y are distinct blocks of G to both of which the vertex y belongs. This makes y a cut-vertex of G, again contradicting our earlier observation that y cannot be a cut-vertex of G. This proves the claim.

(2) Thus, we next divide this case into the following two subcases according to the order of G ′′ . Subcase 2.1 (n ′′ = 1). In this subcase, we claim that S = A ∪ {x} is an LTD-set of G. It is clear that S is a TD-set of G; by Claim A, A is an LTD-set of G[U ]. The vertex y is located from any vertex in U \ A by the vertex x, and thus the set S is also locating. Therefore, in this case, we have

γ L t (G) ≤ |S| = |A| + 1 < 2 3 2|A| -1 + 4 3 [since |A| ≥ 2] ≤ 2 3 |U | + 2 = 2 3 n. [by Claim B]
Subcase 2.2 (n ′′ ≥ 3 and G ′′ is either twin-free or is isomorphic to a 3-path). Since n ′′ is at least 3 and is strictly less than n, by the induction hypothesis, we have γ L t (G ′′ ) ≤ 2 3 n ′′ . Moreover, let S ′′ be a minimum LTD-set of G ′′ , that is with |S ′′ | = γ L t (G ′′ ). We next claim the following. Claim E. The set S = S ′′ ∪ A is an LTD-set of G.

Proof of claim. Since S ′′ is a TD-set of G ′′ and A is a TD-set of G[U ∪ {x}],
S is therefore a TD-set of G. Next we show that S is also a locating set of G. To begin with, we note that Y ′′ = Y -x is a block of G ′′ containing the vertex y. Now, since y is not a cut-vertex of G, we have S ′′ ∩ Y ′′ ̸ = ∅ (or else, y is not dominated by S ′′ ). This implies that x is located by S ′′ from all vertices in U \ A. Moreover, x is also located by p from all vertices in V (G ′′ ) \ S ′′ . Next, any pair w, z of distinct vertices with w ∈ V (G ′′ ) \ S ′′ and z ∈ V (G) \ (S ∪ {x}) are located by S ′′ . Finally, any distinct pair of vertices w, z ∈ U \ A are located by A, since the latter is an LTD-set of G[U ] by Claim A. [START_REF] Argiroffo | Polyhedra associated with open locatingdominating and locating total-dominating sets in graphs[END_REF] Therefore, in this subcase, using Claim B again, the theorem follows from the following inequality.

γ L t (G) ≤ |S| = |S ′′ | + |A| ≤ γ L t (G ′′ ) + 2 3 2|A| -1 [since |A| ≥ 2] ≤ 2 3 n ′′ + 2|A| -1 ≤ 2 3 n ′′ + |U | < 2 3 n.
Subcase 2.3 (n ′′ ≥ 3 and G ′′ is neither twin-free nor is isomorphic to a 3-path). Assume that x ′′ and y ′′ are a pair of twins of G ′′ . Moreover, for x ′′ and y ′′ to be twins in G ′′ , at least one of them must be in the block Y . Let us, without loss of generality, assume that y ′′ ∈ V (Y ). We next observe that the vertices y and y ′′ are the same. To prove so, by contradiction, let us assume that y ′′ ̸ = y. Then y ′′ is a cut-vertex of G and so, for x ′′ and y ′′ to be twins in G ′′ , x ′′ must not belong to the block Y of G. However, this, in turn, implies that y is a neighbor of y ′′ but not of x ′′ and so, x ′′ and y ′′ are not twins in G ′′ , a contradiction all the same. This, therefore, proves the observation.

Again, the vertex x ′′ / ∈ Y , since otherwise, x ′′ ̸ = y ′′ = y implies that x ′′ is a cut-vertex of G, thus forcing x ′′ and y ′′ to not be twins, contrary to our assumption. Let x ′′ belong to the block X ′′ (̸ = Y ) of G ′′ (and of G). We now try to establish the structure of the block Y of G. Notice that, by the structure of a block graph, the twins x ′′ and y in G ′′ must have a single common neighbor z, say, in G ′′ such that z is a cut-vertex of G belonging to both the blocks Y and X ′′ of G. Furthermore, if the block Y contains any vertex of G other than the vertices x, y and z, then x ′′ and y are not twins in G ′′ , a contradiction. Thus, we have V (Y ) = {x, y, z}.

Next, to understand the structure of the block X ′′ of G ′′ , we see that neither can X ′′ contain any vertex other than z and x ′′ , nor can x ′′ be a cut-vertex of G; or else, we again have the contradiction that x ′′ and y are not twins in G ′′ . Therefore, this implies that V (X ′′ ) = {x ′′ , z}, that is, X ′′ is a leaf block of G ′′ (and of G). See Figure 3 for the structure of the blocks X ′′ and Y .

With that, we look at the block graph G ⋆ = G ′′ -y (the graph induced by the vertices on the right of the dashed curve in Figure 3b). Then, G ⋆ is again a connected graph, since y is not a cut-vertex of G. Moreover, the order n ⋆ of G ⋆ is at least 2 (since x ′′ , z ∈ V (G ⋆ )). If, however, n ⋆ = 2, then we have V (G ′′ ) = {x ′′ , y, z} and thus, G ′′ is isomorphic to a 3-path, contrary to our assumption in this subcase. Therefore, we have n ⋆ ≥ 3. We next show the following claim.

Claim F. The graph G ⋆ is twin-free.

Proof of claim. Toward a contradiction, let us assume that the block graph G ⋆ has a pair of twins. Then one of them must be the cut-vertex z of G. Let x ⋆ be the other vertex of G ⋆ such that x ⋆ and z are twins in G ⋆ . Since x ′′ is a neighbor of z alone in G ⋆ , therefore z cannot be a twin in G ⋆ of any vertex other than x ′′ . In other words, x ⋆ = x ′′ . However, since deg G ⋆ (x ′′ ) = 1, we have deg G ⋆ (z) = 1 and, hence, the graph G ⋆ is simply the edge x ′′ z of G. This however, contradicts the fact that n ⋆ ≥ 3. Hence, this proves that G ⋆ is twin-free. [START_REF] Argiroffo | Polyhedra associated with open locatingdominating and locating total-dominating sets in graphs[END_REF] Since n ⋆ is at least 3 and is strictly less than n, by the induction hypothesis, we have

γ L t (G ⋆ ) ≤ 2 3 n ⋆ . Moreover, let S ⋆ be a minimum LTD-set of G ⋆ , that is with |S ⋆ | = γ L t (G ⋆ ). We next claim the following. Claim G. The set S = S ⋆ ∪ A ∪ {x} is an LTD-set of G. Proof of claim. Since S ⋆ is a TD-set of G ⋆ and A ∪ {x} is a TD-set of G[U ∪ {x, y}],
S is therefore a TD-set of G. Next we show that S is also a locating set of G. To begin with, we note that, since x ′′ is a leaf in G ⋆ , its support vertex z must be in the LTD-set S ⋆ of G ⋆ . Thus, the vertex y is located from every other vertex in V (G) \ S by the set {x, z}. Next, any pair w 1 , w 2 of distinct vertices with Therefore, again using Claim B, in this subcase, the theorem follows from the following inequality.

w 1 ∈ V (G ⋆ ) \ S ⋆ and w 2 ∈ V (G) \ S,
γ L t (G) ≤ |S| = |S ⋆ | + |A| + 1 < γ L t (G ⋆ ) + 2 3 2|A| + 1 [since |A| ≥ 2] ≤ 2 3 n ⋆ + 2|A| + 1 ≤ 2 3 n ⋆ + |U | + 2 = 2 3 n.
This completes the proof.

For any block graph H of order k ≥ 2, the 2-corona G = H • P 2 is a twin-free block graph of order n = 3k and by Observation 2, it has locating-total domination number equal to its total domination number, that is, 4 for an illustration with H a complete graph. Thus, we obtain the following. Proposition 7. There are infinitely many connected twin-free block graphs G of order n with γ L t (G) =

γ L t (G) = γ t (G) = 2k = 2 3 n. See Figure

Subcubic graphs

In this section, we establish a tight upper bound on the locating-total domination number of a subcubic graph, where a subcubic graph is a graph with maximum degree at most 3. For this purpose, let F tdom be the family consisting of the three complete graphs K 1 , K 2 , and K 4 , and a star K 1,3 , that is,

F tdom = {K 1 , K 2 , K 4 , K 1,3 }.
We denote a path, a cycle, and a complete graph on n vertices by P n , C n , and K n , respectively. A diamond is the graph K 4 -e where e is an arbitrary edge of the K 4 . A paw is the graph obtained from a γ L t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that

γ L t (G) ≤ γ L t (G ′ ) + 2 ≤ 2
3 n, a contradiction. (b) Suppose that there is a (1, 2, 2)-sequence in G. Let v ′ be the second neighbor of v 3 . As in the previous case, n ′ = n -3 ≥ 4 and G ′ is connected. By part (a), there is no (1, 3, 1)-sequence, implying that G ′ / ∈ F tdom and γ L t (G ′ ) ≤ 2 3 n ′ = 2 3 n -2. As before every γ L t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that γ L t (G) ≤ 2 3 n, a contradiction. (c) Suppose that there is a (1, 2, 3, 1)-sequence in G. In this case, n ′ = n -4 ≥ 3 and G ′ is connected. By part (a), there is no (1, 3, 1)-sequence, implying that

G ′ / ∈ F tdom and γ L t (G ′ ) ≤ 2 3 n ′ = 2 3 (n-4) < 2 3 n-2. Every γ L
t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that γ L t (G) ≤ 2 3 n, a contradiction. (d) Suppose that there is a (1, 2, 3, 2, 1)-sequence in G. In this case, G ′ is connected and

n ′ = n-5 ≥ 2. If G ′ ∈ F tdom , then G ′ ∼ = K 2 by
the fact that there is no (1, 3, 1)-sequence in G by part (a). The graph G is therefore determined, and is obtained a star K 1,3 by subdividing every edge once. We note that G has order n = 7 and the set

N [v 3 ] (of non-leaves of G) is a LTD-set of G, implying that γ L t (G) ≤ 4 < 2 3 n, a contradiction. Hence, G ′ / ∈ F tdom . Thus, γ L t (G ′ ) ≤ 2 3 n ′ = 2 3 (n -5) < 2 3 n -3. Every γ L t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 , v 3 , and v 4 , implying that γ L t (G) < 2 3 n, a contradiction.
(e) Suppose that there is a (1, 2, 3)-sequence in G. In this case, n ′ = n-3 ≥ 4 and G ′ contains at most two components. Let v 4 and v ′ 4 be the two neighbors of v 3 different from v 2 . By our earlier observations, each of v 4 and v ′ 4 has degree at least 2 in G, and therefore degree at least 1 in G ′ . Suppose that G ′ is disconnected. In this case, since there is no (1, 3, 1)-sequence, no (1, 2, 3, 1)sequence, and no (1, 2, 3, 2, 1)-sequence in G, neither component of G ′ belongs to F tdom . By linearity, we therefore have that

γ L t (G ′ ) ≤ 2 3 n ′ = 2 3 n -2. Every γ L t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that γ L t (G) ≤ 2 3 n, a contradiction. Hence, G ′ is connected. Recall that n ′ ≥ 4. Suppose now that G ′ is connected. If G ′ ∈ F tdom , then G ′ ∼ = K 1,3 . Let v 5 be the central vertex of G ′ , and so each of v 4 and v ′ 4 is a leaf neighbor of v 5 in G ′ . The graph G is therefore determined and n = 7. The set {v 2 , v 3 , v 4 , v 5 } is a LTD-set of G, implying that γ L t (G) ≤ 4 < 2 3 n, a contradiction. Hence, G ′ / ∈ F tdom . Thus, γ L t (G ′ ) ≤ 2 3 n ′ = 2 3 n -2.
Every γ L t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that γ L t (G) ≤ 2 3 n, a contradiction. (f) Since there is no (1, 2, 1)-sequence (since n ≥ 7), no (1, 2, 2)-sequence by (b) and no (1, 2, 3)sequence by (e), there can be no (1, 2)-sequence in G. Hence, part (f) follows immediately from parts (b) and (e).

(g) Suppose that there is a (1, 3, 2)-sequence in G. In this case, n ′ = n -3 ≥ 4. If G ′ is disconnected, then by parts (a)-(f), neither component of G ′ belongs to F tdom . By linearity, we therefore have that [START_REF] Babai | On the complexity of canonical labeling of strongly regular graphs[END_REF] . In this case, the graph G has order n = 7 and is obtained from a 5-cycle by selecting two non-adjacent vertices on the cycle and adding a pendant edge to these two vertices. In this case, the set consisting of the two vertices of degree 3 and any two vertices of degree 2 is a LTD-set of G, implying that

γ L t (G ′ ) ≤ 2 3 n ′ = 2 3 n -2. Every γ L t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that γ L t (G) ≤ 2 3 n, a contradiction. Hence, G ′ is connected. If G ′ ∈ F tdom , then G ′ ∼ = K 1,
γ L t (G) ≤ 4 < 2 3 n, a contradiction. Hence, G ′ / ∈ F tdom . Thus, γ L t (G ′ ) ≤ 2 3 n ′ = 2 3 n -2. Every γ L t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that γ L t (G) ≤ 2 3 n, a contradiction.
(h) Suppose that there is a (1, 3, 3, 1)-sequence in G. In this case, n ′ = n -4 ≥ 3 and G ′ contains at most two components. Let u i be the neighbor of v i not on P for i ∈ {2, 3}. Possibly, u 2 = u 3 . By parts (a) and (g), the vertex u i has degree 3 in G for i ∈ {2, 3}. Suppose that G ′ is disconnected. In this case, by parts (a)-(g), neither component of G ′ belongs to F tdom . By linearity, we therefore have that

γ L t (G ′ ) ≤ 2 3 n ′ = 2 3 (n -4) < 2 3 n -2.
Every γ L t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that γ L t (G) < 2 3 n, a contradiction. Hence, G ′ is connected. Recall that n ′ ≥ 3. By parts (a)-(g), we note that

G ′ / ∈ F tdom , implying that γ L t (G ′ ) ≤ 2 3 n ′ < 2 3 n -2. Every γ L
t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that γ L t (G) < 2 3 n, a contradiction. Thus, the proof of the subclaim is complete.

L t (G ′ ) ≤ 2 3 n ′ = 2 3 n -2.
Every γ L t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that

γ L t (G) ≤ γ L t (G ′ ) + 2 ≤ 2 3 n, a contradiction.
(c) Suppose that there is a (2, 2, 3)-sequence in G. Since there is no (2, 2, 2)-sequence and no (2, 3, 2)sequence in G, every vertex different from v 2 that is adjacent to v 1 or v 3 has degree 3 in G. Together with our earlier observations, the graph G ′ therefore cannot contain a component that belongs to F tdom . By linearity, we have

γ L t (G ′ ) ≤ 2 3 n ′ = 2 3 n -2. As before this yields γ L t (G) ≤ γ L t (G ′ ) + 2 ≤ 2 3 n, a contradiction.
(d) Since there is no (2, 2, 2)-sequence and no (2, 2, 3)-sequence, there can be no (2, 2)-sequence in G noting that every vertex has degree 2 or 3.

(e) Suppose that there is a (2, 3, 3)-sequence in G. Since there is no (2, 2, 2)-sequence, no (2, 3, 2)sequence, and no (2, 2, 3)-sequence in G, the graph G ′ cannot contain a component that belongs to F tdom . By linearity, this yields γ L t (G ′ ) ≤2 3 n ′ = 2 3 n -2. Every γ L t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that γ L t (G) ≤ γ L t (G ′ ) + 2 ≤ 2 3 n, a contradiction. Thus, the proof of the subclaim is complete. (⋄) By Subclaim J.1(d), there is no (2, 2)-sequence. Hence every vertex of degree 2 has both its neighbors of degree 3. Moreover since there is no (2, 3, 2)-sequence, every vertex of degree 3 has at most one neighbor of degree 2. But this would imply the existence of a (2, 3, 3)-sequence, contradicting Subclaim J.1(e). Therefore, there can be no vertex of degree 2 in G, that is, G is a cubic graph. This completes the proof of Claim J. [START_REF] Argiroffo | Polyhedra associated with open locatingdominating and locating total-dominating sets in graphs[END_REF] By Claim J, the graph G is a cubic graph. Recall that G is triangle-free. We now consider a (3, 3, 3)sequence. The graph G ′ cannot contain a component that belongs to F tdom . By linearity, this yields

γ L t (G ′ ) ≤ 2 3 n ′ = 2 3 n -2. Every γ L t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that γ L t (G) ≤ γ L t (G ′ ) + 2 ≤ 2
3 n, a contradiction. This completes the proof of Theorem 8.

For k ≥ 3, the 2-corona G = C k •P 2 of a cycle C k has order n = 3k and by Observation 2, it has locating total domination number equal to its total domination number, that is, γ L t (G) = γ t (G) = 2k = 2 3 n. See Figure 5 for an illustration. Moreover for k ≥ 1, the 2-corona G = P k • P 2 of a path P k has order n = 3k and also satisfies γ L t (G) = γ t (G) = 2k = 2 3 n. Thus, we obtain the following. Proposition 9. There are infinitely many connected twin-free subcubic graphs G of order n with γ L t (G) =

Outerplanar graphs

In this section, we prove that Conjecture 1 holds for twin-free outerplanar graphs. The conjecture was shown to hold for trees in [START_REF] Foucaud | Locating-total dominating sets in twin-free graphs: a conjecture[END_REF] (as trees are C 4 -free). Thus, we focus on outerplanar graphs that are not trees. We use the following well-known characterisation of outerplanar graphs in our proofs.

Theorem 10 ([12]

). A graph G is outerplanar if and only if it does not contain K 4 or K 2,3 as a minor.

A leg l 0 • • • l k at l 0 of length k ≥ 1 is an induced subgraph of G such that it is isomorphic to a path of length k, and deg G (l 0 ) ≥ 3, deg G (l k ) = 1, and deg G (l i ) = 2 for all i ∈ {1, . . . , k -1}. When there exists a leg l 0 • • • l k , we say that vertex l 0 has a leg. Lemma 11. Let G be a connected twin-free outerplanar graph of order n that is not a tree. If the smallest component of G -e has at most three vertices for every bridge e ∈ E(G), then γ L t (G) ≤ 2 3 n. Proof. Since G is twin-free, every bridge of G is an edge of a leg of length at most 3. The structure of G can be described as follows. Denote by G ′ the graph we obtain from G by removing all bridges and resulting isolated vertices. The graph G ′ is a connected outerplanar graph with δ(G ′ ) ≥ 2. We denote the maximal 2-connected components of G ′ by G ′ i , where i ∈ {1, . . . , k}. As the 2-connected components form a tree-like structure, we choose the indexing of the components G ′ i so that

|V (G ′ i ) ∩ j<i V (G ′ j )| ≤ 1
for all i ∈ {1, . . . , k} (such an indexing can be found by choosing a leaf-component as a root and indexing the components in a breadth-first ordering starting from the root). We denote by G i the induced subgraph of G obtained by adding the necessary legs to G ′ i for each i ∈ {1, . . . , k}. If a cut-vertex v separating some 2-connected components has legs, then those legs are in the subgraph G i where i

= min{j | v ∈ V (G ′ j )} and no others. Now, we have |V (G i ) ∩ V (G j )| ≤ 1 when i ̸ = j, and V (G) = k i=1 V (G i ).
In what follows, we construct a LTD-set S ⊆ V (G) of G by considering the subgraphs G i in the order of their indexing. Denote by c i the unique element of V (G ′ i ) ∩ j<i V (G ′ j ) if such a vertex exists (i.e. the vertex c i is the cut-vertex separating G i from previous subgraphs G j ). If c i exists, then whether c i is contained in S or not has already been decided when considering some previous subgraph G j , and this decision will not change in later steps. Recall that any 2-connected outerplanar graph is Hamiltonian [START_REF] Chartrand | Planar permutation graphs[END_REF].

Let v i 0 v i 1 • • • v i ni v i 0 be a Hamiltonian cycle of G ′ i such that v i 0 = c i if c i exists, otherwise v i 0
can be chosen arbitrarily. We include vertices from G i to the set S as follows: 2. Assume that v i j has a leg of length 1, and v i j-1 has at least one leg. If v i j+1 ̸ = c i has no legs, then let v i j+1 ∈ S. If v i j+1 = c i , then let v i j-1 ∈ S. Similarly, assume that v i j has a leg of length 1, and v i j+1 has at least one leg. If v i j-1 ̸ = c i has no legs, then let v i j-1 ∈ S. If v i j-1 = c i , then let v i j+1 ∈ S.

1. For each leg l 0 • • • l k , let      l 0 ∈ S if k = 1, l 0 , l 1 ∈ S if k = 2, l 1 , l 2 ∈ S if k = 3, (notice that l 0 = v i j for some j). v i 0 ̸ = c i v i 1 v i ni • • • • • • (a) v i 0 ̸ = ci and j = 1, ni v i 0 = c i v i 1 v i ni • • • • • • (b) v i 0 = ci and j = 1, ni v i 0 v i 1 v i ni • • • • • • (c) j = 2, ni -1
3. If v i j has a leg of length 1, and v i j-1 and v i j+1 have no legs, then let

         v i 0 ∈ S if j ∈ {1, n i } and v i 0 ̸ = c i , v i ni-1 ∈ S if j = n i and v i 0 = c i , v i 1 ∈ S if j = 2, v i j+1 ∈ S otherwise.
See Figure 6 for illustrations of the different cases.

4. Relabel the vertices v i j that have not been included in S in the previous steps as u i 0 , . . . , u i n ′ i such that u i 0 = v i m , where m = min{j | v i j ̸ = c i and v i j / ∈ S}, and if j < l, u i j = v i j ′ and u i l = v i l ′ , then j ′ < l ′ (for some l ∈ [n ′ i ] and l ′ ∈ [n i ]). Let u i j ∈ S if and only if j ≡ 1, 2 (mod 3), except let u i n ′ i / ∈ S and u i n ′ i -1 ∈ S when n ′ i ≡ 1 (mod 3).

See Figure 7 for an example of the set S in one subgraph G i . Notice that the edges of G ′ i that are not in the Hamiltonian cycle do not affect the construction. The vertices outside the dotted outlines (other than c i ) are the vertices u i j considered in step 4. Notice that in this example we have the exceptional case of step 4. Claim K. The set S is a total dominating set of G.

Proof of claim. Let v ∈ V (G i ) \ V (G ′
i ) for some i. Now v = l j for some leg l 0 • • • l k and j ̸ = 0. Due to step 1 of the construction of S, we have l j-1 ∈ S or l j+1 ∈ S.

Let us then consider the vertices of G ′ i for some i. Consider a vertex v i j ̸ = c i . Due to step 1, if the vertex v i j has a leg of length 2 or 3, then l 1 ∈ N (v i j ) ∩ S for such a leg. Assume that the vertex v i j has a leg of length 1. If at least one of v i j-1 and v i j+1 has no legs, then one of them is in N (v i j ) ∩ S by step 2 or 3. Assume that both v i j-1 and v i j+1 have legs. Suppose to the contrary that v i j-1 / ∈ S and v i j+1 / ∈ S. Since v i j ∈ S by step 1, we have v i j-1 = u i j ′ and v i j+1 = u i j ′ +1 for some j ′ ∈ {0, . . . , n ′ i -1}. However, according to step 4, we have u i j ′ ∈ S or u i j ′ +1 ∈ S, a contradiction. If |N G1 (v) \ {u}| = 2, then one of the twins must be u, s or t (possibly, the two twins are among these three vertices). If u is a twin with some vertex other than s, t, then we would have a K 2,3 subgraph in G, contradicting Theorem 10. Thus, either s or t is one of the twins. However, the vertices s and t are not twins with each other in G ′ 1 , since if they were, they would be twins also in G, and G would not be twin-free. Thus, s or t has a neighbor that is not a neighbor of the other, say, x ∈ N (s) \ N (t), x ̸ = t. Since N G ′ 1 (u) = {s, t}, if s or t has a twin, then it must be u. However, the vertex u cannot be a twin of s, because the vertex x is not a neighbor of u. Thus, if G ′ 1 has twins, then these twins are u and t, N G ′ 1 (t) = {u, s} and N G ′ 1 (u) = {s, t} (see Figure 9b). Let us return to the original components G 1 and G 2 of G -e.

Claim N. There is a LTD-set of G 1 of size at most 2 3 n 1 which contains v and which is also a LTD-set of G 1 + {e, s ′ }.

Conclusion

We have proved Conjecture 1 for several important graph classes: cobipartite graphs, split graphs, block graphs, subcubic graphs and outerplanar graphs.

It would be interesting to extend these results to larger classes, for example chordal graphs (which include split graphs and block graphs) or K 4 -minor-free graphs (which include outerplanar graphs). Another interesting subclass of chordal graphs to consider is the class of interval graphs.

It would also be interesting to prove that the bound γ L t (G) ≤ n 2 holds for sufficiently large (twin-free) cubic graphs, as conjectured in [START_REF] Henning | Locating-total domination in claw-free cubic graphs[END_REF].

2 3 ×

 3 3k = 2k from Theorem 4, we finally obtain γ LT D (G k ) = 2k -1.

Figure 2 :

 2 Figure 2: Figure (a) represents a twin-free block graph G and Figure (b) represents T G . The vertices underneath the dashed curve represent those deleted from G to obtain G ′ . The black vertices represent vertices in the set A. (All notations are as in the proof of Theorem 6.)

  The vertices to the left of the dashed curve represent those deleted from G to obtain G ′′ . G ′′ ∼ = P3. The black vertices constitute the set A and the grey vertices constitute an LTDset S ′′ of G ′′ . The vertices to the left of the dashed curve represent those deleted from G to obtain G ⋆ . G ′′ has twins x ′′ and y; and G ⋆ is a twin-free block graph. The black vertices constitute the set A ∪ {x} and the grey vertices constitute an LTD-set S ⋆ of G ⋆ .

Figure 3 :

 3 Figure 3: Twin-free block graph G. The dotted boxes mark the blocks X, X ′′ and Y of G as in the proof of Theorem 6.

  respectively, are located by S ⋆ . Finally, by Claim A, any pair of distinct vertices w 1 , w 2 ∈ U \ A are located by the set A.[START_REF] Argiroffo | Polyhedra associated with open locatingdominating and locating total-dominating sets in graphs[END_REF]

Figure 4 :

 4 Figure 4: The 2-corona K 6 • P 2 of a complete graph of order 6.

  (⋄)(a) There is no (2, 2, 2)-sequence.(b) There is no (2, 3, 2)-sequence.(c) There is no (2, 2, 3)-sequence.(d) There is no (2, 2)-sequence.(e) There is no (2, 3, 3)-sequence.Proof of subclaim. (a) Suppose that there is a (2, 2, 2)-sequence in G. In this case, n ′ = n -3 ≥ 4. Since n ≥ 7, δ(G) = 2, and G contains no triangle, no component of G ′ belongs to F tdom . Hence by linearity,γ L t (G ′ ) ≤ 2 3 n ′ = 2 3 n -2.Every γ L t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that γ L t (G) ≤ 2 3 n, a contradiction. (b) Suppose that there is a (2, 3, 2)-sequence in G. As before, n ′ = n-3 ≥ 4. Suppose that G ′ contains a component that belongs to F tdom . Since there is no (2, 2, 2)-sequence and n ≥ 7, and since δ(G) ≥ 2 and G contains no triangle, this is only possible if G ′ ∼ = K 1,3 . But then the graph G is determined and n = 7, andγ L t (G ′ ) = 4 < 2 3 n (by considering the set N [v 2 ]), a contradiction. Hence, no component of G ′ belongs to F tdom . By linearity, this yields γ

Figure 5 :

 5 Figure 5: The 2-corona C 6 • P 2 of a 6-cycle.

Figure 6 :

 6 Figure 6: Illustrations for step 3 of the construction in the proof of Lemma 11. The black vertices are in S by steps 1 and 3. The dotted lines depict a possible partition of the vertices to obtain an upper bound on |S|.

Figure 9 :

 9 Figure 9: Illustrations for Case 2, where (a) |N G1 (v) \ {u}| = 1, and (b) |N G1 (v) \ {u}| = 2.

n.

* This work was sponsored by a public grant overseen by the French National Research Agency as part of the "Investissements d'Avenir" through the IMobS3 Laboratory of Excellence (ANR-10-LABX-0016) and the IDEX-ISITE initiative CAP 20-25 (ANR-16-IDEX-0001). We also acknowledge support of the ANR project GRALMECO (ANR-21-CE48-0004). Saint-Étienne, Clermont-Auvergne-INP, LIMOS, 63000 Clermont-Ferrand, France Research supported by Jenny and Antti Wihuri Foundation § Department of Mathematics and Applied Mathematics, University of Johannesburg 1

triangle K 3 by adding a new vertex and joining it with an edge to one vertex of the triangle. Equivalently, a paw is obtained from K 1,3 by adding an edge between two leaves.

For k ≥ 2, we say a graph G contains a (d 1 , d 2 , . . . , d k )-sequence if there exists a path v 1 v 2 . . . v k such that deg G (v i ) = d i for all i ∈ [k]. We are now in a position to prove the following upper bound on the locating-total domination number of a subcubic graph.

Theorem 8. If G /

∈ F tdom is a connected subcubic graph of order n ≥ 3, then γ L t (G) ≤ 2 3 n. Proof. Suppose, to the contrary, that the theorem is false. Among all counterexamples, let G be one of minimum order n. If n = 3, then G ∼ = P 3 or G ∼ = K 3 , and in both cases γ L t (G) = 2 = 2 3 n, a contradiction. Hence, n ≥ 4. Suppose n = 4. By assumption, G / ∈ {K 4 , K 1,3 }. If G is a diamond or a paw, then let S consist of one vertex of degree 2 and one vertex of degree 3, and if G is a path or a cycle, then let S consist of two adjacent vertices of degree 2. In all cases, S is a LTD-set of G of cardinality 2, and so γ L t (G) ≤ 2 < 2 3 n, a contradiction. Hence, n ≥ 5. Suppose that n = 5. If G is a path P 5 or a cycle C 5 , then γ L t (G) = 3 < 2 3 n (choose three consecutive vertices of degree 2), a contradiction. Hence, ∆(G) = 3. Let v be a vertex of degree 3 in G with neighbors v 1 , v 2 , v 3 . Let v 4 be the remaining vertex of G. Since G is connected, we may assume, renaming vertices if necessary, that v 1 v 4 is an edge. The set {v, v 1 , v 2 } is a LTD-set of G, and so γ L t (G) ≤ 3 < 2 3 n, a contradiction. Hence, n ≥ 6.

Suppose that n = 6. If G is a path P 6 or a cycle C 6 , then γ L t (G) = 4 = 2 3 n (choose four consecutive vertices of degree 2), a contradiction. Hence, ∆(G) = 3. Let v be a vertex of degree 3 in G with neighbors v 1 , v 2 , v 3 , and let v 4 and v 5 be the two remaining vertices of G. Since G is connected, we may assume, renaming vertices if necessary, that v 1 v 4 is an edge. One of the sets {v,

In what follows, we adopt the notation that if there is a (

We show firstly that there is no vertex of degree 1.

Proof of claim. Suppose, to the contrary, that δ(G) = 1. We proceed further with a series of structural properties of the graph G that show that certain (d 1 , d 2 , . . . , d k )-sequences are forbidden.

Subclaim H.1. The following properties hold in the graph G.

(a) There is no (1, 3, 1)-sequence.

(b) There is no (1, 2, 2)-sequence.

(c) There is no (1, 2, 3, 1)-sequence.

(d) There is no (1, 2, 3, 2, 1)-sequence.

(e) There is no (1, 2, 3)-sequence.

(f) There is no (1, 2)-sequence.

(g) There is no (1, 3, 2)-sequence.

(h) There is no (1, 3, 3, 1)-sequence.

Proof of subclaim. (a) Suppose that there is a (1, 3, 1)-sequence in G. In this case,

Since G is connected, so too is the graph G ′ . Thus, G ′ is not a counterexample to our theorem, except possibly when n = 4 and G ′ ∈ F tdom . Let v ′ be the third neighbor of v 2 in G not on the path P . Suppose

The graph G is therefore determined, and has order n = 7. In this case, choosing S to consist of the two support vertices (of degree 3) and a leaf neighbor of each support vertex produces a LTD-set of G of cardinality 4, and so

We now return to the proof of Claim H. By Subclaim H.1(f), the neighbor of every vertex of degree 1 has degree 3 in G. Further by Subclaim H.1(g), such a vertex of degree 3 has both its other two neighbors of degree 3. Therefore the existence of a vertex of degree 1 implies that there is a (1, 3, 3)-sequence in G. In this case, n ′ = n -3 ≥ 4. Let u 2 be the neighbor of v 2 not on P , and let u 3 and w 3 be the two neighbors of v 3 not on P . By our earlier observations, the vertex u 2 has degree 3 in G, and, by Subclaim H.1(h), both vertices u 3 and w 3 have degree at least 2 in G.

Suppose that G ′ contains a component that belongs to F tdom . By Subclaim H.1, this is only possible if u 3 and w 3 are adjacent and both vertices have degree 2 in G. In this case, G[{v 3 , u 3 , w 3 }] is a triangle in G. We now consider the connected graph G * = G-{v 1 , v 2 , v 3 , u 3 , w 3 } of order n * = n-5. Since u 2 has degree 2 in G * , we note that n * ≥ 3 and By Claim H, every vertex in G has degree 2 or 3.

Claim I. The graph G is triangle-free.

Proof of claim. Suppose that G contains a triangle K 3 . Among all triangles in G, let T contain the maximum number of vertices of degree 2 in G.

Since n ≥ 7, the triangle T contains at most two vertices of degree 2, and so deg

, implying that every vertex in T has degree 3 in G. Hence by our choice of the triangle T , no vertex of degree 2 in G belongs to a triangle.

Let u i be the neighbor of v i not in the triangle T for i ∈ [START_REF] Babai | On the complexity of canonical labeling of strongly regular graphs[END_REF]. We note that the vertices u 1 , u 2 , and u 3 are not necessarily distinct. Suppose that G ′ contains no component that belongs to F tdom . By linearity, this yields

Every γ L t -set of G ′ can be extended to a LTD-set of G by adding to it the vertices v 2 and v 3 , implying that γ L t (G) ≤ 2 3 n, a contradiction. Hence, G ′ contains a component that belongs to F tdom . Since n ≥ 7 and no vertex of degree 2 in G belongs to a triangle, this is only possible if either

On the one hand, if G ′ ∼ = K 1,3 , then the three vertices u 1 , u 2 , and u 3 are leaves in G ′ that are adjacent to a common neighbor (of degree 3) in G ′ . In this case, the graph G is determined and n = 7, and the set

3 n, a contradiction. On the other hand, if G ′ contains a K 2 -component, then renaming vertices if necessary, we may assume that u 1 and u 2 belong to such a component. We note that u 1 and u 2 both have degree 2 in G, and

Further we note that in this case, G ′ contains two components, where the second component contains the vertex u 3 . We now consider the graph

By Claim I, the graph G is triangle-free. We show next that there is no vertex of degree 2.

Claim J. The graph G is a cubic graph.

Proof of claim. Suppose, to the contrary, that δ(G) = 2. As before, we obtain a series of structural properties of the graph G that show that certain (d 1 , d 2 , . . . , d k )-sequences are forbidden. These forbidden sequences will enable us to deduce the desired result of the claim that G must be a cubic graph.

Subclaim J.1. The following properties hold in the graph G. Assume then that the vertex v i j has no legs. If v i j-1 or v i j+1 has a leg of length 1 or 2, then v i j-1 or v i j+1 is in N (v i j ) ∩ S due to step 1. Assume that v i j-1 and v i j+1 have no legs of length 1 or 2. Suppose to the contrary that v i j-1 / ∈ S and v i j+1 / ∈ S. Now v i j = u i j ′ , v i j-1 = u i j ′ -1 , and v i j+1 = u i j ′ +1 for some j ′ ∈ {0, . . . , n ′ i }, and N (v i j ) ∩ S is nonempty due to step 4. The vertex c i also has a neighbor in S, however, this neighbor is not necessarily in V (G i ). Let G j be the subgraph with the smallest index that contains c i . Now, c i ̸ = c j and c i has a neighbor in S by the arguments above. [START_REF] Argiroffo | Polyhedra associated with open locatingdominating and locating total-dominating sets in graphs[END_REF] The following claim is used repeatedly in the final part of the proof where we prove that the set S is locating.

, and due to step 4, either v i j ∈ S or v i j+1 ∈ S, a contradiction. Assume then that j / ∈ {0, 1}, and suppose, to the contrary, that v i j-1 / ∈ S. Now j -1 ≥ 1, and thus v i j-1 ̸ = c i . As in the previous case, we have v i j-1 = u i j ′ -1 , and either v i j ∈ S or v i j-1 ∈ S, a contradiction.

(

Claim M. The set S is a LTD-set of G.

Proof of claim. By Claim K, the set S is a TD-set of G. What remains to be shown is that for all distinct v, w / ∈ S, we have N (v) ∩ S ̸ = N (w) ∩ S. Consider a vertex v that is a leaf. Suppose, to the contrary, that there exists a vertex w ∈ V (G) \ S such that w ̸ = v and N (v) ∩ S = N (w) ∩ S. Since the vertex v is a leaf, its support vertex is in S due to step 1 of the construction of S. The vertex w is not a leaf, since otherwise the graph G would have twins. Due to step 1, the vertex w cannot be in the same leg as v. Thus, w = v i j for some i and j, and v is a leaf of a leg of length 1. Without loss of generality, we may assume that i is the minimum index such that w ∈ V (G ′ i ). This implies that w ̸ = c i . Since w / ∈ S, due to step 1 the vertex w either has no legs or all the legs of w are of length 3. If w has a leg of length 3, then that leg contains an element of N (w) ∩ S that is not in N (v). Thus, the vertex w has no legs. Since the vertex v is a leaf of a leg of length 1, we have N (v) ∩ S = {v i ′ l } for some l and i ′ . If j / ∈ {0, 1, n i }, then |N (w) ∩ S| ≥ 2 due to Claim L as w ̸ = c i . Assume that j ∈ {0, 1, n i }.

Since w = v i 1 has no legs and v i 2 has a leg of length 1, we have w ∈ S due to step 2 or 3, a contradiction.

no legs and v i

ni-1 has a leg of length 1, we have w ∈ S due to step 2 or 3, a contradiction. Assume that j = 0. According to (the proof of) Claim K and the minimality of i, the vertex w has a neighbor in V (G i ) ∩ S. Now N (v) ∩ S = {v i l } = N (w) ∩ S. Since w ̸ = c i and w / ∈ S, we have w = u i 0 and v i 1 ∈ S, which implies that l = 1 and i = i ′ . However, now w ∈ S due to step 2 or 3, a contradiction.

Thus, all leaves are located by S.

Consider then the case where v and w are in the same 2-connected component of G, that is, v = v i j and w = v i l for some j, l and i. Assume without loss of generality that j < l. Assume that v i j ̸ = c i . Since j < l ≤ n i , we have v i j+1 ∈ S according to Claim L. This implies that l ≥ 2, and thus v i l-1 ∈ S. If j + 1 = l -1, then having both v i j / ∈ S and v i l / ∈ S contradicts step 4 of the construction of S. Thus, j + 1 ̸ = l -1. However, now N (v i j ) ∩ S = N (v i l ) ∩ S implies that the graph G contains K 4 as a minor. Indeed, the vertices v i j+1 and v i l-1 are both neighbors of v i j and

, whose edges can be contracted to obtain the minor K 4 . Now the graph G is not outerplanar according to Theorem 10, a contradiction.

Assume that j = 0 and v = v i j = c i . Now for some i ′ < i, we have v ∈ V (G i ′ ) and w / ∈ V (G i ′ ). Due to (the proof of) Claim K, the vertex v has a neighbor in V (G i ′ ) ∩ S. This neighbor cannot be a neighbor of w, since the only vertex of G i that can have neighbors in G i ′ is the cut-vertex v.

Consider finally the case where v and w belong to two different 2-connected components of G, that is, v = v i j and w = v i ′ l for some j, l, i and i

, and we can handle this case as in the previous case. So assume that neither v nor w is the cut-vertex separating G i and G i ′ . Assume without loss of generality that i ′ < i. Now the cut-vertex separating G i and

To conclude the proof, we note that |S| ≤ 2 3 n. This is easy to see when each V (G i )\{c i } is partitioned into small sets according to the steps of the construction as illustrated in Figures 6 and7. The dotted outlines group vertices considered in steps 1-3. Each set of three vertices contains two elements of S, and each set of two elements contains one element of S. The vertices outside the dotted lines are the vertices u i j considered in step 4, of which at most two thirds are in S.

Theorem 12. If G is a connected twin-free isolate-free outerplanar graph of order n, then γ L t (G) ≤ 2 3 n. Proof. We prove the claim by induction on n. If the graph G is a tree, the claim holds by [START_REF] Foucaud | Locating-total dominating sets in twin-free graphs: a conjecture[END_REF] as trees do not contain 4-cycles. If G is not a tree and does not contain a bridge e ∈ E(G) such that both components of G -e have at least four vertices, then the claim holds by Lemma 11.

In particular, for sufficiently small n, the claim holds by Lemma 11, or the graph G is a tree and the claim holds due to [START_REF] Foucaud | Locating-total dominating sets in twin-free graphs: a conjecture[END_REF].

Thus, assume that G contains a bridge e ∈ E(G) such that both components of G -e have at least four vertices.

For the inductive step, assume that when G ′ is a connected twin-free outerplanar graph of order n ′ < n, then there exists a LTD-set S ⊂ V (G ′ ) such that |S| ≤ 2 3 n ′ . The graph G -e consists of two components G 1 and G 2 . Assume that both G 1 and G 2 are twinfree. By the induction hypothesis, there exist LTD-sets S 1 and S 2 of G 1 and G 2 , respectively, such that

) be the end-point of e in G 1 . There exists exactly one pair of twins, and v is one of the twins (otherwise the graph G is not twin-free). Let u be the twin of v in G 1 . If |N G1 (v) \ {u}| ≥ 3, then v and u together with their shared neighborhood contains K 2,3 , and the graph G is not outerplanar according to Theorem 10. Thus, |N G1 (v) \ {u}| ∈ {1, 2}. We denote N G1 (v) \ {u} = {s} and N G1 (v) \ {u} = {s, t} when |N G1 (v) \ {u}| equals 1 and 2, respectively. In what follows, we have combined the case analyses of both of these cases. Thus, the vertex t is included in the case analysis, when in fact t may not exist. The places where the existence of t truly matters are clearly indicated. In other places, keep in mind that t may or may not exist.

Instead of G -e, let us now consider the graph G -{vs, vt, vu} (note that the edge vu may or may not be present). The graph G -{vs, vt, vu} has two components, which are clearly outerplanar, and we denote them by

∪ {v} (see Figure 8). Case 1. Assume that G ′ 1 is twin-free. By the induction hypothesis, there exists a LTD-set

Notice that since the set S 1 totally dominates the vertex u, we have {s, t} ∩ S 1 ̸ = ∅. Let us then consider G ′ 2 . Notice that the vertex v is a leaf in G ′ 2 . Denote the support vertex of v by s ′ . Assume that G ′ 2 is twin-free. By the induction hypothesis, there exists a LTD-set

Notice that s ′ ∈ S 2 , since s ′ is a support vertex. Assume that G ′ 2 is not twin-free. Then, there exists a leaf v ′ ̸ = v attached to s ′ . Now the graph G ′ 2 -v is connected, outerplanar, and twin-free. By the induction hypothesis, there exists a LTD-set

2 is a LTD-set of G depending on whether the graph G ′ 2 has twins. Indeed, the vertex v is the unique vertex that is dominated by a vertex of G ′ 1 and a vertex of

Case 2. Assume that G ′ 1 contains twins. Then, one of the twins must be a neighbor of v in G. If |N G1 (v) \ {u}| = 1, then one of the twins is u, since u is a leaf in G ′ 1 , and thus s cannot have a twin in G ′ 1 . The other twin is a leaf u ′ ̸ = u attached to s (see Figure 9a). Notice that the edge vu is present in G, since otherwise u and u ′ would be twins also in G.

Proof of claim. Denote

1 is twin-free, then by the induction hypothesis, there exists a LTD-set S 1 1 of G * 1 such that |S 1 1 | ≤ 2 3 (n 1 -2), and we have s ∈ S 1 1 , since s is the support vertex of u ′ or u. Now, the set S 1 = S 1 1 ∪ {v} is a LTD-set of G 1 . Indeed, S 1 is clearly a TD-set, and it is a locating set as v dominates u (resp. t) and the only neighbor of v in G * 1 is s. Since v ∈ S 1 , the set S 1 is also a TD-set of G 1 + {e, s ′ }. We have N (s ′ ) ∩ S 1 = {v}. Since u and t are dominated by s ∈ S 1 , the set S 1 is also locating in G 1 + {e, s ′ }. We have |S 1 | ≤ 2 3 (n 1 -2) + 1 = 2 3 (n 1 -1 2 ). Assume then that G * 1 has twins. Then, |N G1 (v) \ {u}| = 2 and there exists a leaf w ̸ = u attached to s. Now, the graph G * 1 -u is either twin-free or K 2 . If G * 1 -u = K 2 , then the set S ′ 1 = {v, s, u} fulfils the claim. Indeed, it is clearly a TD-set of both G 1 and G 1 + {e, s ′ }. Since the neighbors of t, w, and s ′ in S ′ 1 are {v, s, u}, s, and v, respectively, the set S ′ 1 is a locating set of both G 1 and G 1 + {e, s ′ }. Additionally, we have |S ′ 1 | < If there exists a LTD-set of G 2 of cardinality at most 2 3 n 2 , then it forms a LTD-set of G together with the set of Claim N. If G 2 is twin-free, then such a LTD-set of G 2 exists by the induction hypothesis. If G 2 is not twin-free, then we can repeat the same case analysis as for G 1 and obtain a LTD-set of G 2 of cardinality at most 2 3 n 2 .

The bound in Theorem 12 is tight due to Observation 2. Indeed, if G is an outerplanar graph, then so is its 2-corona G • P 2 , and we have γ L t (G • P 2 ) = 2|V (G)| = 2 3 |V (G • P 2 )|. Proposition 13. There are infinitely many connected twin-free outerplanar graphs G of order n with γ L t (G) = 2 3 n.