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...
Gespeichert in:
| Datum: | 2018 |
|---|---|
| Hauptverfasser: | , |
| Format: | Artikel |
| Sprache: | English |
| Veröffentlicht: |
Lugansk National Taras Shevchenko University
2018
|
| Schlagworte: | |
| Online Zugang: | https://admjournal.luguniv.edu.ua/index.php/adm/article/view/697 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Algebra and Discrete Mathematics |
Institution
Algebra and Discrete Mathematics| Zusammenfassung: | 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\). |
|---|