Search

Abstract: In this paper, we study the geodetic convexity of graphs, focusing on the problem of the complexity of computing a minimum hull set of a graph in several graph classes. For any two vertices of a connected graph , the closed interval of and is the set of vertices that belong to some shortest -path. For any , let . A subset is geodesically convex or convex if . In other words, a subset is convex if, for any and for any shortest -path , . Given a subset , the convex hull of is the smallest convex set that contains . We say that is a hull set of if . The size of a minimum hull set of is the hull number of , denoted by . The Hull Number problem is to decide whether , for a given graph and an integer . Dourado et al. showed that this problem is NP-complete in general graphs. In this paper, we answer an open question of Dourado et al. (2009) [1] by showing that the Hull Number problem is NP-hard even when restricted to the class of bipartite graphs. Then, we design polynomial-time algorithms to solve the Hull Number problem in several graph classes. First, we deal with the class of complements of bipartite graphs. Then, we generalize some results in Araujo et al. (2011) [2] to the class of -graphs and to cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an -node graph without simplicial vertices is at most in general, at most if is regular or has no triangle, and at most if has girth at least . [Copyright &y& Elsevier]

Abstract: Given a bipartite graph such that and every edge is labelled true or false or both, the perfect matching free subgraph problem is to determine whether or not there exists a subgraph of containing, for each node of , either all the edges labelled true or all the edges labelled false incident to , and which does not contain a perfect matching. This problem arises in the structural analysis of differential-algebraic systems. The purpose of this paper is to show that this problem is NP-complete. We show that the problem is equivalent to the stable set problem in a restricted case of tripartite graphs. Then we show that the latter remains NP-complete in that case. We also prove the NP-completeness of the related minimum blocker problem in bipartite graphs with perfect matching. [Copyright &y& Elsevier]

Abstract: Given a bipartite graph , a 2-layered drawing consists of placing nodes in the first node set V on a straight line and placing nodes in the second node set W on a parallel line . For a given ordering of nodes in W on , the one-sided crossing minimization problem asks to find an ordering of nodes in V on so that the number of arc crossings is minimized. A well-known lower bound LB on the minimum number of crossings is obtained by summing up over all node pairs , where denotes the number of crossings generated by arcs incident to u and when u precedes in an ordering. In this paper, we prove that there always exists a solution whose crossing number is at most if the minimum degree of a node in V is at least 5. [Copyright &y& Elsevier]