19-25 June 2011
Bled, Slovenia
Europe/Ljubljana timezone
Home > Timetable > Contribution details

The geodetic number of the lexicographic product of graphs

Presented by Dr. Tadeja KRANER ŠUMENJAK
Type: Oral presentation
Track: Metric Graph Theory


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.


Location: Bled, Slovenia
Address: Best Western Hotel Kompas Bled

Primary authors