The strong convexity spectra of grids

DOI10.1007/S00373-017-1805-4MaRDI QIDQ2409510zbMATH OpenOpenAlexFDO

Authors G. Araujo-Pardo, César Hernández-Cruz, Juan José Montellano-Ballesteros

Publication date 11 October 2017

Published in Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1703.02654

zbMATH Keywords

convex setconvexity numbergridoriented graphspectrum

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Distance in graphs (05C12) Directed graphs (digraphs), tournaments (05C20) Connectivity (05C40) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17)

Abstract: Let $D$ be a connected oriented graph. A set $SsubseteqV(D)$ is convex in $D$ if, for every pair of vertices $x,yinS$, the vertex set of every $xy$-geodesic, ($xy$ shortest directed path) and every $yx$-geodesic in $D$ is contained in $S$. The convexity number, $mcon(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 $mcon(D)colonDmisastrongorientationofG$. In this paper we prove that the problem of determining the convexity number of an oriented graph is $mathcalNP$-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,mge2$.

Recommendations

• The convexity spectra of graphs
• Convexity in oriented graphs
• On the convexity number of graphs
• On the spectrum and number of convex sets in graphs
• Geodetic spectra of graphs.

Cites work

• Convexity in oriented graphs
• scientific article; zbMATH DE number 4050423 (Why is no real title available?)
• scientific article; zbMATH DE number 1764950 (Why is no real title available?)
• On the convexity number of graphs
• On the hull number of some graph classes
• Some remarks on the convexity number of a graph
• Some remarks on the geodetic number of a graph
• The convexity number of a graph
• The convexity spectra of graphs
• The geodetic number of a graph
• The geodetic number of an oriented graph
• The hull number of a graph

Cited in

(1)

• The convexity spectra of graphs

This page was built for publication: The strong convexity spectra of grids

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2409510)