# Bled'11 - 7th Slovenian International Conference on Graph Theory

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

# 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

More

More