The upper edge-to-vertex detour number of~a~graph

A. P. Santhakumaran ; S. Athisayanathan

Algebra and discrete mathematics, Tome 13 (2012) no. 1, pp. 128-138.

Résumé

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 $d{n}_2(G)=a$ and $d{n}_2^{+}(G)=b$.

Détail

Keywords: edge-to-vertex detour basis, edge-to-vertex detour number, upper edge-to-vertex detour number.
Mots-clés : Detour, edge-to-vertex detour set

Bibliographie

[1] F. Buckley, F. Harary, Distance in Graphs, Addison-Wesley, Reading, MA, 1990 | MR | Zbl

[2] G. Chartrand, H. Escuadro, P. Zhang, “Detour Distance in Graphs”, J. Combin. Math. Combin. Comput., 53 (2005), 75–94 | MR | Zbl

[3] G. Chartrand, G. L. Johns, P. Zhang, “Detour Number of a Graph”, Util. Math., 64 (2003), 97–113 | MR | Zbl

[4] G. Chartrand, P. Zang, “Distance in Graphs–Taking the Long View”, AKCE J. Graphs. Combin., 1:1 (2004), 1–13 | MR | Zbl

[5] G. Chartrand, P. Zang, Introduction to Graph Theory, Tata McGraw-Hill, New Delhi, 2006

[6] A. P. Santhakumaran, S. Athisayanathan, “Weak Edge Detour Number of a Graph”, Ars Combin., 98 (2011), 33–61 | MR | Zbl

[7] A. P. Santhakumaran, S. Athisayanathan, “Edge Detour Graphs”, J. Combin. Math. Combin. Comput., 69 (2009), 191–204 | MR | Zbl

[8] A. P. Santhakumaran, S. Athisayanathan, “Connected detour number of a graph”, J. Combin. Math. Combin. Comput., 69 (2009), 205–218 | MR | Zbl

[9] A. P. Santhakumaran, S. Athisayanathan, “Edge-to-vertex detour number of a graph”, Adv. Studies Contem. Math., 21:4 (2011), 395–412 | MR | Zbl