19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
The geodetic number of the lexicographic product of graphs
Presented by Dr. Tadeja KRANER ŠUMENJAK
Type: Oral presentation
Track: Metric Graph Theory
Content
A set $S$ of vertices of a graph $G$ is a geodetic set if every
vertex of $G$ lies in an interval between two vertices from $S$.
The size of a minimum geodetic set in $G$ is the geodetic
number $g(G)$ of $G$. We find that the geodetic number of the lexicographic
product $G\circ H$ for non-complete graph $H$ lies between 2 and
$3g(G)$. We characterize the graphs $G$ and $H$ for which $g(G\circ H)=2$,
as well as the lexicographic products $T\circ H$ that enjoy $g(T\circ H)=3g(G)$,
when $T$ is isomorphic to a tree. Using a new concept of the so-called
geodominating triple of a graph $G$, a formula that expresses the exact
geodetic number of $G\circ H$ is established, where $G$ is an arbitrary graph
and $H$ a non-complete graph.
Place
Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled
Co-authors
- Prof. Boštjan BREšAR University of Maribor, IMFM
- Dr. Aleksandra TEPEH University of Maribor, IMFM