Paper Info
Title
On the Complexity of the P3-Hull Number of the Cartesian Product of Graphs.
Abstract
Let G be a finite, simple, and undirected graph and let S be a set of vertices of G. If no vertex of G that does not belong to S has two neighbors in S, then S is P3-convex. The P3-convex hull H(S) of S is the smallest P3-convex set containing S. If H(S)=V(G) we say that S is a P3-hull set of G. The cardinality h(G) of a minimum P3-hull set in G is called the P3-hull number of G. In this paper w extend the result of Centeno et al. [Theoretical Computer Science 412 (2011), 3693–3700] showing that, given a graph G and an integer k, deciding whether h(G)≤k remains NP-complete for the Cartesian product of graphs.
Year
DOI
Venue
2016
10.1016/j.endm.2016.10.042
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
P3-convexity,P3-hull number,Cartesian product
Integer,Discrete mathematics,Combinatorics,Vertex (geometry),Bound graph,Hull number,Cartesian product,Cartesian product of graphs,Cardinality,Hull,Mathematics
Journal
Volume
ISSN
Citations 
55
1571-0653
0
PageRank 
References 
Authors
0.34
0
4
Name
Order
Citations
PageRank
Julliano R. Nascimento103.38
Erika M. M. Coelho2155.27
Hebert Coelho331.78
Jayme Luiz Szwarcfiter461895.79