The upper edge-to-vertex detour number of a graph
For two vertices \(u\) and \(v\) in a graph \(G = (V, E)\), the detour distance \(D(u, v)\) is the length of a longest \(u\)-\(v\) path in \(G\). A \(u\)-\(v\) path of length \(D(u, v)\) is called a \(u\)-\(v\) detour. For subsets \(A\) and \(B\) of \(V\), the detour distance \(D(A, B)\) is defined...
Збережено в:
| Дата: | 2018 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | English |
| Опубліковано: |
Lugansk National Taras Shevchenko University
2018
|
| Теми: | |
| Онлайн доступ: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/697 |
| Теги: |
Додати тег
Немає тегів, Будьте першим, хто поставить тег для цього запису!
|
| Назва журналу: | Algebra and Discrete Mathematics |
Репозитарії
Algebra and Discrete Mathematics| id |
oai:ojs.admjournal.luguniv.edu.ua:article-697 |
|---|---|
| record_format |
ojs |
| spelling |
oai:ojs.admjournal.luguniv.edu.ua:article-6972018-04-04T09:42:12Z The upper edge-to-vertex detour number of a graph Santhakumaran, A. P. Athisayanathan, S. Detour, edge-to-vertex detour set, edge-to-vertex detour basis, edge-to-vertex detour number, upper edge-to-vertex detour number 05C12 For two vertices \(u\) and \(v\) in a graph \(G = (V, E)\), the detour distance \(D(u, v)\) is the length of a longest \(u\)-\(v\) path in \(G\). A \(u\)-\(v\) path of length \(D(u, v)\) is called a \(u\)-\(v\) detour. For subsets \(A\) and \(B\) of \(V\), the detour distance \(D(A, B)\) is defined as \(D(A, B) = \min\{D(x, y): x \in A\), \(y \in B\}\). A \(u\)-\(v\) path of length \(D(A, B)\) is called an \(A\)-\(B\) detour joining the sets \(A\), \(B \subseteq V\) where \(u\in A\) and \(v \in B\). A vertex \(x\) is said to lie on an \(A\)-\(B\) detour if \(x\) is a vertex of an \(A\)-\(B\) detour. A set \(S\subseteq E\) is called an edge-to-vertex detour set if every vertex of \(G\) is incident with an edge of \(S\) or lies on a detour joining a pair of edges of \(S\). The edge-to-vertex detour number \({dn}_{2}(G)\) of \(G\) is the minimum order of its edge-to-vertex detour sets and any edge-to-vertex detour set of order \({dn}_{2}(G)\) is an edge-to-vertex detour basis of \(G\). An edge-to-vertex detour set \(S\) in a connected graph \(G\) is called a minimal edge-to-vertex detour set of \(G\) if no proper subset of \(S\) is an edge-to-vertex detour set of \(G\). The upper edge-to-vertex detour number, \({dn}_{2}^{+} (G)\) of \(G\) is the maximum cardinality of a minimal edge-to-vertex detour set of \(G\). The upper edge-to-vertex detour numbers of certain standard graphs are obtained. It is shown that for every pair \(a\), \(b\) of integers with \(2 \le a \le b\), there exists a connected graph \(G\) with \(dn_{2}(G)=a\) and \(dn_{2}^{+}(G)=b\). Lugansk National Taras Shevchenko University 2018-04-04 Article Article Peer-reviewed Article application/pdf https://admjournal.luguniv.edu.ua/index.php/adm/article/view/697 Algebra and Discrete Mathematics; Vol 13, No 1 (2012) 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/697/230 Copyright (c) 2018 Algebra and Discrete Mathematics |
| institution |
Algebra and Discrete Mathematics |
| collection |
OJS |
| language |
English |
| topic |
Detour edge-to-vertex detour set edge-to-vertex detour basis edge-to-vertex detour number upper edge-to-vertex detour number 05C12 |
| spellingShingle |
Detour edge-to-vertex detour set edge-to-vertex detour basis edge-to-vertex detour number upper edge-to-vertex detour number 05C12 Santhakumaran, A. P. Athisayanathan, S. The upper edge-to-vertex detour number of a graph |
| topic_facet |
Detour edge-to-vertex detour set edge-to-vertex detour basis edge-to-vertex detour number upper edge-to-vertex detour number 05C12 |
| format |
Article |
| author |
Santhakumaran, A. P. Athisayanathan, S. |
| author_facet |
Santhakumaran, A. P. Athisayanathan, S. |
| author_sort |
Santhakumaran, A. P. |
| title |
The upper edge-to-vertex detour number of a graph |
| title_short |
The upper edge-to-vertex detour number of a graph |
| title_full |
The upper edge-to-vertex detour number of a graph |
| title_fullStr |
The upper edge-to-vertex detour number of a graph |
| title_full_unstemmed |
The upper edge-to-vertex detour number of a graph |
| title_sort |
upper edge-to-vertex detour number of a graph |
| description |
For two vertices \(u\) and \(v\) in a graph \(G = (V, E)\), the detour distance \(D(u, v)\) is the length of a longest \(u\)-\(v\) path in \(G\). A \(u\)-\(v\) path of length \(D(u, v)\) is called a \(u\)-\(v\) detour. For subsets \(A\) and \(B\) of \(V\), the detour distance \(D(A, B)\) is defined as \(D(A, B) = \min\{D(x, y): x \in A\), \(y \in B\}\). A \(u\)-\(v\) path of length \(D(A, B)\) is called an \(A\)-\(B\) detour joining the sets \(A\), \(B \subseteq V\) where \(u\in A\) and \(v \in B\). A vertex \(x\) is said to lie on an \(A\)-\(B\) detour if \(x\) is a vertex of an \(A\)-\(B\) detour. A set \(S\subseteq E\) is called an edge-to-vertex detour set if every vertex of \(G\) is incident with an edge of \(S\) or lies on a detour joining a pair of edges of \(S\). The edge-to-vertex detour number \({dn}_{2}(G)\) of \(G\) is the minimum order of its edge-to-vertex detour sets and any edge-to-vertex detour set of order \({dn}_{2}(G)\) is an edge-to-vertex detour basis of \(G\). An edge-to-vertex detour set \(S\) in a connected graph \(G\) is called a minimal edge-to-vertex detour set of \(G\) if no proper subset of \(S\) is an edge-to-vertex detour set of \(G\). The upper edge-to-vertex detour number, \({dn}_{2}^{+} (G)\) of \(G\) is the maximum cardinality of a minimal edge-to-vertex detour set of \(G\). The upper edge-to-vertex detour numbers of certain standard graphs are obtained. It is shown that for every pair \(a\), \(b\) of integers with \(2 \le a \le b\), there exists a connected graph \(G\) with \(dn_{2}(G)=a\) and \(dn_{2}^{+}(G)=b\). |
| publisher |
Lugansk National Taras Shevchenko University |
| publishDate |
2018 |
| url |
https://admjournal.luguniv.edu.ua/index.php/adm/article/view/697 |
| work_keys_str_mv |
AT santhakumaranap theupperedgetovertexdetournumberofagraph AT athisayanathans theupperedgetovertexdetournumberofagraph AT santhakumaranap upperedgetovertexdetournumberofagraph AT athisayanathans upperedgetovertexdetournumberofagraph |
| first_indexed |
2024-04-12T06:25:47Z |
| last_indexed |
2024-04-12T06:25:47Z |
| _version_ |
1796109210890534912 |