RUS  ENG
Полная версия
ЖУРНАЛЫ // Algebra and Discrete Mathematics // Архив

Algebra Discrete Math., 2012, том 13, выпуск 1, страницы 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

Аннотация: 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$.

Ключевые слова: Detour, edge-to-vertex detour set, edge-to-vertex detour basis, edge-to-vertex detour number, upper edge-to-vertex detour number.

MSC: 05C12

Поступила в редакцию: 23.11.2011
Исправленный вариант: 30.11.2011

Язык публикации: английский



Реферативные базы данных:


© МИАН, 2024