Advertisement
Published in:
2012 | OriginalPaper | Chapter
Immediate versus Eventual Conversion: Comparing Geodetic and Hull Numbers in P 3-Convexity
Authors : Carmen Cecilia Centeno, Lucia Draque Penso, Dieter Rautenbach, Vinícius Gusmc̃o Pereira de Sá
Published in: Graph-Theoretic Concepts in Computer Science
Publisher: Springer Berlin Heidelberg
Activate our intelligent search to find suitable subject content or patents.
Select sections of text to find matching patents with Artificial Intelligence. powered by
Select sections of text to find additional relevant content using AI-assisted search. powered by
We study the graphs
G
for which the hull number
h
(
G
) and the geodetic number
g
(
G
) with respect to
P
3
-convexity coincide. These two parameters correspond to the minimum cardinality of a set
U
of vertices of
G
such that the simple expansion process that iteratively adds to
U
, all vertices outside of
U
that have two neighbors in
U
, produces the whole vertex set of
G
either eventually or after one iteration, respectively. We establish numerous structural properties of the graphs
G
with
h
(
G
) =
g
(
G
), which allow the constructive characterization as well as the efficient recognition of all triangle-free such graphs. Furthermore, we characterize the graphs
G
that satisfy
h
(
H
) =
g
(
H
) for every induced subgraph
H
of
G
in terms of forbidden induced subgraphs.