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 |
|---|---|
| Автори: | , |
| Формат: | Стаття |
| Мова: | Англійська |
| Опубліковано: |
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| _version_ | 1856543038882447360 |
|---|---|
| author | Santhakumaran, A. P. Athisayanathan, S. |
| author_facet | Santhakumaran, A. P. Athisayanathan, S. |
| author_sort | Santhakumaran, A. P. |
| baseUrl_str | |
| collection | OJS |
| datestamp_date | 2018-04-04T09:42:12Z |
| 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\). |
| first_indexed | 2025-12-02T15:40:42Z |
| format | Article |
| id | admjournalluguniveduua-article-697 |
| institution | Algebra and Discrete Mathematics |
| language | English |
| last_indexed | 2025-12-02T15:40:42Z |
| publishDate | 2018 |
| publisher | Lugansk National Taras Shevchenko University |
| record_format | ojs |
| spelling | admjournalluguniveduua-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 |
| 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 |
| title | 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_short | The upper edge-to-vertex detour number of a graph |
| title_sort | upper edge-to-vertex detour number of a graph |
| topic | Detour edge-to-vertex detour set edge-to-vertex detour basis edge-to-vertex detour number upper edge-to-vertex detour number 05C12 |
| 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 |
| 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 |