|
Algebra and Discrete Mathematics, 2012, Volume 13, Issue 1, Pages 128–138
(Mi adm70)
|
|
|
|
RESEARCH ARTICLE
The upper edge-to-vertex detour number of a graph
A. P. Santhakumaran, S. Athisayanathan Department of Mathematics, St. Xavier's College (Autonomous), Palayamkottai - 627 002, India
Abstract:
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$.
Keywords:
Detour, edge-to-vertex detour set, edge-to-vertex detour basis, edge-to-vertex detour number, upper edge-to-vertex detour number.
Received: 23.11.2011 Revised: 30.11.2011
Citation:
A. P. Santhakumaran, S. Athisayanathan, “The upper edge-to-vertex detour number of a graph”, Algebra Discrete Math., 13:1 (2012), 128–138
Linking options:
https://www.mathnet.ru/eng/adm70 https://www.mathnet.ru/eng/adm/v13/i1/p128
|
Statistics & downloads: |
Abstract page: | 242 | Full-text PDF : | 105 | References: | 57 | First page: | 1 |
|