Paper Info
Title
Geodetic Number versus Hull Number in P3-Convexity.
Abstract
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 which iteratively adds to U all vertices outside of U having 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), allowing for the constructive characterization as well as the efficient recognition of all such graphs that are triangle-free. Furthermore, we characterize-in terms of forbidden induced subgraphs-the graphs G that satisfy h(G') = g(G') for every induced subgraph G' of G.
Year
DOI
Venue
2013
10.1137/110859014
SIAM JOURNAL ON DISCRETE MATHEMATICS
Keywords
DocType
Volume
hull number,geodetic number,P-3-convexity,irreversible 2-threshold processes
Journal
27
Issue
ISSN
Citations 
2
0895-4801
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Carmen C. Centeno1613.66
Lucia Draque Penso219620.46
Dieter Rautenbach3946138.87
Vinícius Gusmão Pereira de Sá43710.37