The strong convexity spectra of grids

2017/03/08 by Araujo-Pardo, Gabriela, Hernández-Cruz, César, Montellano-Ballesteros, Juan José
#05C12 #05C20 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.1703.02654

Abstract

Let D be a connected oriented graph. A set S ⊆ V(D) is convex in D if, for every pair of vertices x, y ∈ S, the vertex set of every xy-geodesic, (xy shortest directed path) and every yx-geodesic in D is contained in S. The convexity number, \rm con(D), of a non-trivial oriented graph, D, is the maximum cardinality of a proper convex set of D. The strong convexity spectrum of the graph G, S_SC (G), is the set \ \rm con(D) \colon D \rm is a strong orientation of G \. In this paper we prove that the problem of determining the convexity number of an oriented graph is NP-complete, even for bipartite oriented graphs of arbitrary large girth, extending previous known results for graphs. We also determine S_SC (P_n \Box P_m), for every pair of integers n,m ≥ 2.

Related

• On the hull and interval numbers of oriented graphs
• Hull and Geodetic Numbers for Some Classes of Oriented Graphs
• On the convexity number of the complementary prism of a tree
• On the geodetic and the hull numbers in strong product graphs
• Orientable convexity, geodetic and hull numbers in graphs