The detour hull number of a graph
For vertices \(u\) and \(v\) in a connected graph \(G=(V, E)\), the set \(I_D[u,v]\) consists of all those vertices lying on a \(u-v\) longest path in \(G\). Given a set \(S\) of vertices of \(G\), the union of all sets \(I_D[u,v]\) for \(u,v\in S\), is denoted by \(I_D[S]\). A set \(S\) is a detour...
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/728 |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| Назва журналу: | Algebra and Discrete Mathematics |
Institution
Algebra and Discrete Mathematics| id |
admjournalluguniveduua-article-728 |
|---|---|
| record_format |
ojs |
| spelling |
admjournalluguniveduua-article-7282018-04-04T10:03:23Z The detour hull number of a graph Santhakumaran, A. P. Chandran, S. V. Ullas detour, detour convex set, detour number, detour extreme vertex, detour hull number 05C12 For vertices \(u\) and \(v\) in a connected graph \(G=(V, E)\), the set \(I_D[u,v]\) consists of all those vertices lying on a \(u-v\) longest path in \(G\). Given a set \(S\) of vertices of \(G\), the union of all sets \(I_D[u,v]\) for \(u,v\in S\), is denoted by \(I_D[S]\). A set \(S\) is a detour convex set if \(I_D[S]=S\). The detour convex hull \([S]_D\) of \(S\) in \(G\) is the smallest detour convex set containing \(S\). The detour hull number \(d_h(G)\) is the minimum cardinality among the subsets \(S\) of \(V\) with \([S]_D=V\). A set \(S\) of vertices is called a detour set if \(I_D[S]=V\). The minimum cardinality of a detour set is the detour number \(dn(G)\) of \(G\). A vertex \(x\) in \(G\) is a detour extreme vertex if it is an initial or terminal vertex of any detour containing \(x\). Certain general properties of these concepts are studied. It is shown that for each pair of positive integers \(r\) and \(s\), there is a connected graph \(G\) with \(r\) detour extreme vertices, each of degree \(s\). Also, it is proved that every two integers \(a\) and \(b\) with \(2\leq a\leq b\) are realizable as the detour hull number and the detour number respectively, of some graph. For each triple \(D,k\) and \(n\) of positive integers with \(2\leq k\leq n-D+1\) and \(D\geq 2\), there is a connected graph of order \(n\), detour diameter \(D\) and detour hull number \(k\). Bounds for the detour hull number of a graph are obtained. It is proved that \(dn(G)=dh(G)\) for a connected graph \(G\) with detour diameter at most 4. Also, it is proved that for positive integers \(a,b\) and \(k\geq 2\) with \(a< b\leq 2a\), there exists a connected graph \(G\) with detour radius \(a\), detour diameter \(b\) and detour hull number \(k\). Graphs \(G\) for which \({d}_{h}(G)=n-1\) or \(d_h(G)=n-2\) are characterized. 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/728 Algebra and Discrete Mathematics; Vol 14, No 2 (2012) 2415-721X 1726-3255 en https://admjournal.luguniv.edu.ua/index.php/adm/article/view/728/260 Copyright (c) 2018 Algebra and Discrete Mathematics |
| institution |
Algebra and Discrete Mathematics |
| baseUrl_str |
|
| datestamp_date |
2018-04-04T10:03:23Z |
| collection |
OJS |
| language |
English |
| topic |
detour detour convex set detour number detour extreme vertex detour hull number 05C12 |
| spellingShingle |
detour detour convex set detour number detour extreme vertex detour hull number 05C12 Santhakumaran, A. P. Chandran, S. V. Ullas The detour hull number of a graph |
| topic_facet |
detour detour convex set detour number detour extreme vertex detour hull number 05C12 |
| format |
Article |
| author |
Santhakumaran, A. P. Chandran, S. V. Ullas |
| author_facet |
Santhakumaran, A. P. Chandran, S. V. Ullas |
| author_sort |
Santhakumaran, A. P. |
| title |
The detour hull number of a graph |
| title_short |
The detour hull number of a graph |
| title_full |
The detour hull number of a graph |
| title_fullStr |
The detour hull number of a graph |
| title_full_unstemmed |
The detour hull number of a graph |
| title_sort |
detour hull number of a graph |
| description |
For vertices \(u\) and \(v\) in a connected graph \(G=(V, E)\), the set \(I_D[u,v]\) consists of all those vertices lying on a \(u-v\) longest path in \(G\). Given a set \(S\) of vertices of \(G\), the union of all sets \(I_D[u,v]\) for \(u,v\in S\), is denoted by \(I_D[S]\). A set \(S\) is a detour convex set if \(I_D[S]=S\). The detour convex hull \([S]_D\) of \(S\) in \(G\) is the smallest detour convex set containing \(S\). The detour hull number \(d_h(G)\) is the minimum cardinality among the subsets \(S\) of \(V\) with \([S]_D=V\). A set \(S\) of vertices is called a detour set if \(I_D[S]=V\). The minimum cardinality of a detour set is the detour number \(dn(G)\) of \(G\). A vertex \(x\) in \(G\) is a detour extreme vertex if it is an initial or terminal vertex of any detour containing \(x\). Certain general properties of these concepts are studied. It is shown that for each pair of positive integers \(r\) and \(s\), there is a connected graph \(G\) with \(r\) detour extreme vertices, each of degree \(s\). Also, it is proved that every two integers \(a\) and \(b\) with \(2\leq a\leq b\) are realizable as the detour hull number and the detour number respectively, of some graph. For each triple \(D,k\) and \(n\) of positive integers with \(2\leq k\leq n-D+1\) and \(D\geq 2\), there is a connected graph of order \(n\), detour diameter \(D\) and detour hull number \(k\). Bounds for the detour hull number of a graph are obtained. It is proved that \(dn(G)=dh(G)\) for a connected graph \(G\) with detour diameter at most 4. Also, it is proved that for positive integers \(a,b\) and \(k\geq 2\) with \(a< b\leq 2a\), there exists a connected graph \(G\) with detour radius \(a\), detour diameter \(b\) and detour hull number \(k\). Graphs \(G\) for which \({d}_{h}(G)=n-1\) or \(d_h(G)=n-2\) are characterized. |
| publisher |
Lugansk National Taras Shevchenko University |
| publishDate |
2018 |
| url |
https://admjournal.luguniv.edu.ua/index.php/adm/article/view/728 |
| work_keys_str_mv |
AT santhakumaranap thedetourhullnumberofagraph AT chandransvullas thedetourhullnumberofagraph AT santhakumaranap detourhullnumberofagraph AT chandransvullas detourhullnumberofagraph |
| first_indexed |
2025-12-02T15:27:34Z |
| last_indexed |
2025-12-02T15:27:34Z |
| _version_ |
1850411887615803392 |