Ratio Mathematica Volume 44, 2022 The Edge-To-Vertex Triangle Free Detor Distance in Graphs S. Lourdu Elqueen1 G. Priscilla Pacifica2 Abstract For every connected graph G, the triangle free detour distance D∆f (u, v) is the length of a longest u- v triangle free path in G, where u, v are the vertices of G. A u-v triangle free path of length D∆f (u, v) is called the u-v triangle free detour. In this article, the edge-to-vertex triangle free detour distance is introduced. It is found that the edge -to- vertex triangle free detour distance differs from the edge -to-vertex distance and edge- to-vertex detour distance. The edge-to-vertex triangle free detour distance is found for some standard graphs. Their bounds are determined and their sharpness is checked. Certain general properties satisfied by them are studied. Keywords: connected graph, edge -to-vertex distance and edge-to-vertex detour distance 2010 AMS subject classification: 05C12, 05C693 1Reg No: 19212212092009, Ph. D Research Scholar (Full Time) of Mathematics. Mary’s College (Autonomous) Thoothukudi affiliated under Manonmaniam Sundaranar University, Abishekapatti, Tirunelveli, Tamil Nadu, South India. sahayamelqueen@gmail.com. 2Department of Mathematics, St. Mary’s College (Autonomous), Thoothukudi, India, priscillamelwyn@gmail.com. 3 Received on June28th, 2022. Accepted on Sep 1st, 2022.Published on Nov 30th, 2022.doi: 10.23755/rm.v44i0.894. ISSN: 1592-7415. eISSN: 2282-8214. ©The Authors. This paper is published under the CC-BY licence agreement. 86 S. Lourdu Elqueen & G. Priscilla Pacifica 1. Introduction The facility location problem was introduced as edge-to-vertex distance by Santhakumaran [9], in 2010. For an edge e and a vertex v in a connected graph, the edge-to-vertex distance is defined by 𝑑(𝑒, 𝑣) = 𝑚𝑖𝑛{𝑑(𝑢, 𝑣) ∶ 𝑢 ∈ 𝑒}. The edge-to- vertex eccentricity of e is defined by 𝑒2(𝑒) = 𝑚𝑎𝑥{𝑑(𝑒, 𝑣) ∶ 𝑣 ∈ 𝑉}. A vertex v of G such that 𝑒2 (𝑒) = 𝑑(𝑒, 𝑣) is called an edge-to-vertex eccentric vertex of v. The edge- to-vertex radius 𝑟2 of G is defined by 𝑟2 = 𝑚𝑖𝑛{𝑒2(𝑒) ∶ 𝑒 ∈ 𝐸} and the edge-to-vertex diameter 𝑑2 of G is defined by𝑑2 = 𝑚𝑎𝑥{𝑒2 (𝑒) ∶ 𝑒 ∈ 𝐸}. An edge e for which 𝑒2(𝑒) is minimum is called an edge-to-vertex central edge of 𝐺and the set of all edge-tovertex central edges of 𝐺 is the edge-to-vertex center 𝐶2(𝐺) of𝐺. An edge 𝑒 for which 𝑒2(𝑒) is maximum is called an edge-to-vertexperipheral edge of 𝐺 and the set of all edge-to- vertex peripheraledges of 𝐺 is the edge-to-vertex periphery 𝑃2 (𝐺) of 𝐺. If every edgeof 𝐺is an edge-to-vertex central edge then 𝐺 is called the edge-to-vertex self-centered graph. This concept is useful in channel assignment problem in radio technology and security-based communication network design. The concept of edge-to-vertex detour distance was introduced by I. Keerthi Asir [6], Let 𝑒 be an edge and 𝑣 a vertex in a connected graph 𝐺. An edge-to-vertex 𝑒 − 𝑣 path 𝑃 is a 𝑢 − 𝑣 path, where𝑢 is a vertex in 𝑒 such that 𝑃 contains no vertices of e other than 𝑢. The edge-to-vertex detour distance 𝐷(𝑒, 𝑣) is the length of a longest 𝑒 − 𝑣path in 𝐺. An𝑒 − 𝑣 path of length 𝐷(𝑒, 𝑣) is called an edge-to-vertex 𝑒 − 𝑣 detour or simply 𝑒 − 𝑣 detour. Forour convenience an𝑒 − 𝑣 path of length 𝑑(𝑒, 𝑣) is called an edge-to-vertex 𝑒 − 𝑣 geodesic or simply 𝑒– 𝑣 geodesic. The following theorems are used in the article. Theorem: 1.1.[6] For any edge 𝑒 and a vertex 𝑣in a non-trivial connected graph of order𝑛, 0 ≤ 𝑑(𝑒, 𝑣) ≤ 𝐷(𝑒, 𝑣) ≤ 𝑛 − 2 . Theorem: 1.2.[6] Let𝐾𝑛,𝑚 (𝑛 < 𝑚) be a complete bipartite graph with partition𝑉1, 𝑉2 of 𝑉(𝐾𝑛,𝑚) such that |𝑉1| = 𝑛 and |𝑉2| = 𝑚. Let 𝑒 be an edge and 𝑣 a vertex such that 𝑣 ∉ 𝑒 in 𝐾𝑛,𝑚, then 𝐷(𝑒, 𝑣) = { 2𝑛 − 2 𝑖𝑓𝑣 ∈ 𝑉1 2𝑛 − 1 𝑖𝑓𝑣 ∈ 𝑉2 2. Edge-To-Vertex Triangle Free Detour Distance Definition. 2.1 Let 𝐺be a connected graph. Let 𝑒be an edge and 𝑢 a vertex in𝐺. An edge-to-vertex 𝑒 − 𝑢triangle free path 𝑃is a 𝑢 − 𝑣 triangle free path, where𝑣is a vertex in 𝑒such that 𝑃contains no vertices of 𝑒 other than 𝑣. The edge-to-vertex triangle free detour distance is the length of the longest 𝑒 − 𝑢 triangle free path in 𝐺.It is denoted by 𝐷∆f (𝑒, 𝑣). An𝑒 − 𝑢 triangle free path of length𝐷∆f (𝑒, 𝑣)is called an edge-to-vertex 𝑒 − 𝑢triangle free detour. 87 The Edge-To-Vertex Triangle Free Detor Distance In Graphs Example: 2.1 Consider the graph 𝐺given in the figure: 2.1. Let 𝑒 = {𝑢6, 𝑢7}and 𝑣 = 𝑢4. The paths between 𝑒and 𝑣 are 𝑃1: 𝑢6, 𝑢5, 𝑢4;𝑃2: 𝑢7, 𝑢2, 𝑢4;𝑃3: 𝑢7, 𝑢2, 𝑢3, 𝑢4 ;𝑃4: 𝑢7, 𝑢8, 𝑢9, 𝑢1, 𝑢2, 𝑢4; and 𝑃5: 𝑢7, 𝑢8, 𝑢9, 𝑢1, 𝑢2, 𝑢3, 𝑢4 ;The paths 𝑃1, 𝑃2, 𝑃4are triangle free 𝑒 − 𝑣 paths and 𝑃3 and 𝑃5 are not triangle free 𝑒 − 𝑣 paths. Thus edge-to-vertex distance 𝑑(𝑒, 𝑣) = 2, edge-to-vertex triangle free detour distance 𝐷∆f (𝑒, 𝑣) = 5 and edge-to-vertex detour distance D(e, v) = 6. Figure: 2.1 G Thus edge-to-vertex triangle free detour distance differs from the edge-to-vertex distance and edge-to-vertex detour distance. Theorem. 2.1 Let 𝐺 be a connected graph of order 𝑛. Let 𝑒 be an edge and 𝑢a vertex of𝐺, then 0 ≤ 𝑑(𝑒, 𝑣) ≤ 𝐷∆𝑓 (𝑒, 𝑣) ≤ 𝐷(𝑒, 𝑣) ≤ 𝑛 − 2 . Proof. By theorem 1.1 , we can conclude that 0 ≤ 𝑑(𝑒, 𝑣) ≤ 𝐷(𝑒, 𝑣) ≤ 𝑛 − 2 . It is enough to prove that (i)𝑑(𝑒, 𝑣) ≤ 𝐷∆𝑓 (𝑒, 𝑣) and (ii) 𝐷∆𝑓 (𝑒, 𝑣) ≤ 𝐷(𝑒, 𝑣). Thus (i) is true by the definition of edge-to-vertex distance and edge-to-vertex triangle free detour distance. To prove :(ii) Case(i): If the detour path does not induce a triangle in G, then𝐷∆𝑓 (𝑒, 𝑣) = 𝐷(𝑒, 𝑣) . Case(ii): If the detour path induces a triangle in G, then 𝐷∆𝑓 (𝑒, 𝑣) < 𝐷(𝑒, 𝑣) Remark 2.1. The bounds in the theorem 2.1 are sharp. Let 𝐺be a graph and 𝑒 be an edge, 𝑑(𝑒, 𝑢) = 𝐷∆𝑓 (𝑒, 𝑢) = 𝐷(𝑒, 𝑢) = 0iff𝑢 ∈ 𝑒.Let 𝐺be a path with vertices {𝑣1 , 𝑣2, … . 𝑣𝑛 }. Then𝑑(𝑒, 𝑢) = 𝐷∆𝑓 (𝑒, 𝑢) = 𝐷(𝑒, 𝑢) = 𝑛 − 2, where 𝑒 = 88 S. Lourdu Elqueen & G. Priscilla Pacifica {𝑣𝑛−1, 𝑣𝑛 }and 𝑢 = 𝑣1. Let 𝐺be a tree, 𝑑(𝑒, 𝑢) = 𝐷∆𝑓 (𝑒, 𝑢) = 𝐷(𝑒, 𝑢) for every edge 𝑒and vertex 𝑢of 𝐺. For the graph 𝐺 given in the figure:2.1, 𝑒 = {𝑢6, 𝑢7} and 𝑣 = 𝑢4. The paths between 𝑒and 𝑣 are 𝑃1: 𝑢6, 𝑢5, 𝑢4; 𝑃2: 𝑢7, 𝑢2, 𝑢4; 𝑃3: 𝑢7, 𝑢2, 𝑢3, 𝑢4 ; 𝑃4: 𝑢7, 𝑢8, 𝑢9, 𝑢1, 𝑢2, 𝑢4; and 𝑃5: 𝑢7, 𝑢8, 𝑢9, 𝑢1, 𝑢2, 𝑢3, 𝑢4 ;The paths 𝑃1, 𝑃2, 𝑃4are triangle free 𝑒 − 𝑣 paths and 𝑃3 and 𝑃5 are not triangle free 𝑒 − 𝑣 paths. Thus edge-to- vertex distance 𝑑(𝑒, 𝑣) = 2, edge-to-vertex triangle free detour distance 𝐷∆f (𝑒, 𝑣) = 5 and edge-to-vertex detour distanceD(e, v) = 6. Thus 0 < 𝑑(𝑒, 𝑣) < 𝐷∆𝑓 (𝑒, 𝑣) < 𝐷(𝑒, 𝑣) < 𝑛 − 2 . Theorem. 2.2 For a complete bipartite graph 𝐺with partitions 𝑉1and 𝑉2such that |𝑉1| = 𝑛and |𝑉2| = 𝑚(𝑛 < 𝑚).Let 𝑒 be an edge of 𝐺 and 𝑢a vertex such that 𝑢 ∉ 𝑒 in G. Then, 𝐷∆𝑓 (𝑒, 𝑢) = { 2𝑛 − 2 𝑖𝑓𝑢 ∈ 𝑉1 2𝑛 − 1 𝑖𝑓𝑢 ∈ 𝑉2 Proof. Since any vertex subset of 𝐺 do not induce a cycle 𝐶3in 𝐺. Thus edge-to-vertex triangle free detour distance is equal to edge-to-vertex detour distance. By theorem: 1.2, 𝐷∆𝑓 (𝑒, 𝑢) = { 2𝑛 − 2 𝑖𝑓𝑢 ∈ 𝑉1 2𝑛 − 1 𝑖𝑓𝑢 ∈ 𝑉2 Corollary:2.1 Let 𝐺 be a complete bipartite graph 𝐾𝑛,𝑛 with partitions 𝑉1and 𝑉2 .Let 𝑒 be an edge and 𝑢 be a vertex such that 𝑢 ∉ 𝑒in𝐺. Then𝐷∆𝑓 (𝑒, 𝑢) = 2𝑛 − 2. Theorem: 2.3 Let 𝐺 be a tree, then for every edge 𝑒 and a vertex 𝑣in 𝐺, 𝑑(𝑒, 𝑣) = 𝐷∆𝑓 (𝑒, 𝑣) = 𝐷(𝑒, 𝑣). Remark: 2.2 The converse of the theorem:2.3 need not be true. Consider the graph,𝐺 = 𝐶4, where 𝑑(𝑒, 𝑣) = 𝐷∆𝑓 (𝑒, 𝑣) = 𝐷(𝑒, 𝑣) = 1 if 𝑣 ∉ 𝑒 and 𝑑(𝑒, 𝑣) = 𝐷∆𝑓 (𝑒, 𝑣) = 𝐷(𝑒, 𝑣) = 0 if 𝑣 ∈ 𝑒. Definition: 2.2 The edge-to-vertex triangle free detour eccentricity 𝑒∆𝑓2 (𝑒) of an edge 𝑒 in a connected graph 𝐺 is defined as𝑒∆𝑓2(𝑒) = 𝑚𝑎𝑥{𝐷∆𝑓 (𝑒, 𝑣) ∶ 𝑣 ∈ 𝑉}. A vertex 𝑣 for which 𝑒∆𝑓2(𝑒) = 𝐷∆𝑓 (𝑒, 𝑣) is called an edge-to-vertex triangle free detour eccentric vertex of 𝑒. The edge-to-vertex triangle free detour radius of G is defined as 𝑅∆𝑓2 = 𝑟𝑎𝑑∆𝑓2(𝐺) = 𝑚𝑖𝑛{𝑒∆𝑓2(𝑒): 𝑒 ∈ 𝐸}. The edge-to-vertex triangle free detour diameter of G is defined as 𝐷∆𝑓2 = 𝑑𝑖𝑎𝑚∆𝑓2(𝐺) = 𝑚𝑎𝑥{𝑒∆𝑓2(𝑒): 𝑒 ∈ 𝐸}. Definition: 2.3 An edge 𝑒 is called an edge-to-vertex triangle free detour central edge if 𝑒∆𝑓2(𝑒) = 𝑅∆𝑓2. The edge-to-vertex triangle free detour center of 𝐺is defined as 𝐶∆𝑓2(𝐺) = 𝐶𝑒𝑛∆𝑓2(𝐺) = {𝑒 ∈ 𝐸: 𝑒∆𝑓2(𝑒) = 𝑅∆𝑓2}. Definition: 2.4 An edge 𝑒 is called an edge-to-vertex triangle free detour peripheral edge if 𝑒∆𝑓2(𝑒) = 𝐷∆𝑓2. The edge-to-vertex triangle free detour periphery of 𝐺 is defined as 𝑃∆𝑓2(𝐺) = 𝑃𝑒𝑟∆𝑓2(𝐺) = {𝑒 ∈ 𝐸: 𝑒∆𝑓2(𝑒) = 𝐷∆𝑓2}. 89 The Edge-To-Vertex Triangle Free Detor Distance In Graphs Definition. 2.5 If every edge of a graph 𝐺 is a edge-to-vertex triangle free detour central edge, then 𝐺 is called edge-to-vertex triangle free detour self centered graph. Definition. 2.6 If 𝐺 is the edge-to-vertex triangle free detour self centered graph, then𝐺 is called edge-to-vertex triangle free detour periphery. Example. 2.2 For the graph 𝐺given in the figure: 2.2, 𝑒1 = {𝑢1, 𝑢2}, 𝑒2 = {𝑢2, 𝑢3}, 𝑒3 = {𝑢3, 𝑢4}, 𝑒4 = {𝑢4, 𝑢5}, 𝑒5 = {𝑢5, 𝑢6}, 𝑒6 = {𝑢6, 𝑢7}, 𝑒7 = {𝑢7, 𝑢8}, 𝑒8 = {𝑢1, 𝑢8}, 𝑒9 = {𝑢8, 𝑢2}, 𝑒10 = {𝑢7, 𝑢5}, 𝑒11 = {𝑢5, 𝑢2}, 𝑒12 = {𝑢3, 𝑢5} are the edges of 𝐺. Figure:2.2 𝐺 The edge-to- vertex triangle free detour distances of the graph 𝐺, are provided in the following table. 𝒖𝟏 𝒖𝟐 𝒖𝟑 𝒖𝟒 𝒖𝟓 𝒖𝟔 𝒖𝟕 𝒖𝟖 𝒆∆𝒇𝟐 𝒆𝟏 0 0 4 4 3 3 2 3 4 𝒆𝟐 1 0 0 4 3 3 2 3 4 𝒆𝟑 4 4 0 0 1 4 3 3 4 𝒆𝟒 3 3 1 0 0 5 4 3 5 𝒆𝟓 3 3 4 5 0 0 3 2 5 𝒆𝟔 3 2 3 4 3 0 0 3 4 𝒆𝟕 3 2 2 3 2 3 0 0 3 𝒆𝟖 0 3 3 3 2 3 3 0 3 𝒆𝟗 1 0 3 3 2 2 2 0 3 𝒆𝟏𝟎 2 2 3 4 0 1 0 2 4 𝒆𝟏𝟏 3 0 2 2 0 3 2 2 3 𝒆𝟏𝟐 3 3 0 1 0 4 3 2 4 Table:2.1 The following table provides the edge-to- vertex distances, edge-to-vertex triangle free detour distances and edge-to- vertex detour distances of the graph 𝐺in figure:2.2 90 S. Lourdu Elqueen & G. Priscilla Pacifica 𝒆𝟏 𝒆𝟐 𝒆𝟑 𝒆𝟒 𝒆𝟓 𝒆𝟔 𝒆𝟕 𝒆𝟖 𝒆𝟗 𝒆𝟏𝟎 𝒆𝟏𝟏 𝒆𝟏𝟐 𝒆𝟐 2 2 2 2 2 2 2 3 2 2 1 2 𝒆∆𝒇𝟐 4 4 4 5 5 4 3 3 3 4 3 4 𝒆𝑫𝟐 6 6 6 6 6 6 6 6 5 5 4 5 Table: 2.2 The edge-to-vertex radius𝑟2 = 1, the edge-to-vertex triangle free detour radius 𝑅∆𝑓2 = 3 , the edge-to- vertex detour radius 𝑅2 = 4. Thus, the edge-to-vertex triangle free detour radius is different from the edge-to- vertex radius and the edge-to- vertex detour radius. The edge-to-vertex diameter 𝑑2 = 3, the edge-to- vertex triangle free detour diameter 𝐷∆𝑓2 = 6 , the edge-to- vertex detour diameter 𝐷2 = 6. Thus, the edge- to- vertex triangle free detour diameter is different from the edge-to- vertex diameter and the edge-to- vertex detour diameter. The edge-to-vertex center 𝐶2(𝐺) = {𝑒11}, the edge-to-vertex triangle free detour center 𝐶∆𝑓2(𝐺) = {𝑒7, 𝑒8, 𝑒9, 𝑒11}, the edge-to-vertex detour center 𝐶𝐷2(𝐺) = {𝑒9, 𝑒10, 𝑒11}Thus the edge-to- vertex triangle free detour center is different from the edge-to- vertex center and the edge-to- vertex detour center. The edge-to-vertex periphery 𝑃2(𝐺) = {𝑒8}, the edge-to-vertex triangle free detour periphery 𝑃∆𝑓2(𝐺) = {𝑒4, 𝑒5}, the edge-to-vertex detour periphery 𝑃𝐷2(𝐺) = {𝑒1, 𝑒2 , 𝑒3 , 𝑒4, 𝑒5, 𝑒6, 𝑒7, 𝑒8}. Thus, the edge-to- vertex triangle free detour periphery is different from the edge-to- vertex periphery and the edge-to- vertex detour periphery. The edge-to-vertex triangle free detour radius 𝑅∆𝑓2 and the edge-to-vertex triangle free detour diameter 𝐷∆𝑓2 of some standard graphs are provided in the table:2.3 𝑮 𝑲𝒏 𝑷𝒏 𝑪𝒏 (𝒏 ≥ 𝟒) 𝑾𝒏(𝒏 ≥ 𝟓) 𝑲𝒏,𝒎(𝒏 ≥ 𝒎) 𝑹∆𝒇𝟐 1 ⌊ 𝑛 − 2 𝑛 ⌋ 𝑛 − 2 𝑛 − 2 { 2(𝑛 − 1), 𝑖𝑓𝑛 = 𝑚 2𝑛 − 1, 𝑖𝑓𝑛 > 𝑚 𝑫∆𝒇𝟐 1 𝑛 − 2 𝑛 − 2 𝑛 − 2 { 2(𝑛 − 1), 𝑖𝑓𝑛 = 𝑚 2𝑛 − 1, 𝑖𝑓𝑛 > 𝑚 Example: 2.3 The complete graph 𝐾𝑛, the Cycle graph 𝐶𝑛 (𝑛 ≥ 4) and the wheel graph 𝑊𝑛(𝑛 ≥ 5) are the edge-to-vertex triangle free detour self centered graph. Theorem:2.4 For a connected graph 𝐺 of order 𝑛. Then (i)0 ≤ 𝑒2(𝑒) ≤ 𝑒∆𝑓2(𝑒) ≤ 𝑒𝐷2(𝑒) ≤ 𝑛 − 2, for every edge 𝑒of 𝐺. (ii)0 ≤ 𝑟2 ≤ 𝑅∆𝑓2 ≤ 𝑅2 ≤ 𝑛 − 2. (iii) 0 ≤ 𝑑2 ≤ 𝐷∆𝑓2 ≤ 𝐷2 ≤ 𝑛 − 2. Remark: 2.3 The bounds in the theorem:2.4are sharp. If 𝐺 = 𝑃2, then 𝑒2(𝑒) = 𝑒∆𝑓2(𝑒) = 𝑒𝐷2(𝑒) = 0. If 𝐺 = 𝐶𝑛 (𝑛 ≥ 4), then 𝑒2(𝑒) = 𝑒∆𝑓2(𝑒) = 𝑒𝐷2(𝑒) = 𝑛 − 2. For the graph 𝐺 given in the figure:2.2, 0 < 𝑒2(𝑒) < 𝑒∆𝑓2(𝑒) < 𝑒𝐷2(𝑒) < 𝑛 − 2, for the edges 𝑒 = 𝑒9, 𝑒10, 𝑒11, 𝑒12. 91 The Edge-To-Vertex Triangle Free Detor Distance In Graphs References [1] H. Bielak and M. M. Syslo, Peripheral vertices in graphs, Studies. Math. Ungar., 18 (1983), 269-275. [2] G. Chartrand and H. Escuadro and P. Zhang, Detour Distance in Graphs, J. Combin. Math. Combin. Comput., 53 (2005), 75-94. [3] G. Chartrand and P. Zhang, Distance in Graphs - Taking the Long View, AKCEJ. Graphs. Combin., 1 (2004), 1–13. [4] G. Chartrand and P. Zhang, Introduction to Graph Theory, Tata McGraw-Hill New Delhi, 2006. [5] I. Keerthi Asir and S. Athisayanathan, Triangle Free Detour Distance in Graphs, J. Combin. Math. Combin. Comput.,105(2016). [6] I. Keerthi Asir and S. Athisayanathan, Edge-to-Vertex Detour Distance in Graphs, ScienciaActaXaverianaAn International Science Journal, Volume 8 No. 1, 115-133 [7] P.A. Ostrand, Graphs and specified radius and diameter, Discrete Math., 4(1973),71- 75. [8] A. P. Santhakumaran and P. Titus, Monophonic Distance in Graphs, Discrete Math. Algorithms Appl., 3 (2011), 159–169. [9] A. P. Santhakumaran, Center of a graph with respect to edges, SCIENTIA series A: Mathematical Sciences, 19 (2010), 13-23. [10] Sr Little Femilin Jana. D., Jaya. R., Arokia Ranjithkumar, M., Krishnakumar. S., “Resolving Sets and Dimension in Special Graphs”, Advances And Applications In Mathematical Sciences 21 (7) (2022), 3709 – 3717. 92 https://scholar.google.com/citations?view_op=view_citation&hl=en&user=xWCP70YAAAAJ&sortby=pubdate&authuser=1&citation_for_view=xWCP70YAAAAJ:IjCSPb-OGe4C