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 u,v∈V of ...a connected graph G=(V,E), the closed interval Iu,v of u and v is the set of vertices that belong to some shortest (u,v)-path. For any S⊆V, let IS=⋃u,v∈SIu,v. A subset S⊆V is geodesically convex or convex if IS=S. In other words, a subset S is convex if, for any u,v∈S and for any shortest (u,v)-path P, V(P)⊆S. Given a subset S⊆V, the convex hull IhS of S is the smallest convex set that contains S. We say that S is a hull set of G if IhS=V. The size of a minimum hull set of G is the hull number of G, denoted by hn(G). The Hull Number problem is to decide whether hn(G)≤k, for a given graph G and an integer k. 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 (q,q−4)-graphs and to cacti. Finally, we prove tight upper bounds on the hull numbers. In particular, we show that the hull number of an n-node graph G without simplicial vertices is at most 1+⌈3(n−1)5⌉ in general, at most 1+⌈n−12⌉ if G is regular or has no triangle, and at most 1+⌈n−13⌉ if G has girth at least 6.
We study the class of 1‐perfectly orientable graphs, that is, graphs having an orientation in which every out‐neighborhood induces a tournament. 1‐perfectly orientable graphs form a common ...generalization of chordal graphs and circular arc graphs. Even though they can be recognized in polynomial time, little is known about their structure. In this article, we develop several results on 1‐perfectly orientable graphs. In particular, we (i) give a characterization of 1‐perfectly orientable graphs in terms of edge clique covers, (ii) identify several graph transformations preserving the class of 1‐perfectly orientable graphs, (iii) exhibit an infinite family of minimal forbidden induced minors for the class of 1‐perfectly orientable graphs, and (iv) characterize the class of 1‐perfectly orientable graphs within the classes of cographs and of cobipartite graphs. The class of 1‐perfectly orientable cobipartite graphs coincides with the class of cobipartite circular arc graphs.
An edge-coloring is an association of colors to the edges of a graph, in such a way that no pair of adjacent edges receive the same color. A graph
G
is Class 1 if it is edge-colorable with a number ...of colors equal to its maximum degree
Δ
(
G
)
. To determine whether a graph
G
is Class 1 is NP-complete I. Holyer, The NP-completeness of edge-coloring, SIAM J. Comput. 10 (1981) 718–720. First, we propose edge-decompositions of a graph
G
with the goal of edge-coloring
G
with
Δ
(
G
)
colors. Second, we apply these decompositions for identifying new subsets of Class 1 join graphs and cobipartite graphs. Third, the proposed technique is applied for proving that the chromatic index of a graph is equal to the chromatic index of its semi-core, the subgraph induced by the maximum degree vertices and their neighbors. Finally, we apply these decomposition tools to a classical result A.J.W. Hilton, Z. Cheng, The chromatic index of a graph whose core has maximum degree 2, Discrete Math. 101 (1992) 135–147 that relates the chromatic index of a graph to its core, the subgraph induced by the maximum degree vertices.
We study properties of graphs related to the existence of certain vertex and edge partitions. These properties give sufficient conditions for a graph to be Class 1 (i.e., edge-colorable with maximum ...degree colors). We apply these conditions for solving the classification problem for graphs with acyclic
core (the subgraph induced by the maximum degree vertices), and for subclasses of join graphs and cobipartite graphs.
We prove that a locally cobipartite graph on n vertices contains a family of at most n cliques that cover its edges. This is related to Opsut's conjecture that states the competition number of a ...locally cobipartite graph is at most two.
A hypergraph is said to be 1‐Sperner if for every two hyperedges the smallest of their two set differences is of size one. We present several applications of 1‐Sperner hypergraphs to graphs. First, ...we consider several ways of associating hypergraphs to graphs, namely, vertex cover, clique, independent set, dominating set, and closed neighborhood hypergraphs. For each of them, we characterize graphs yielding 1‐Sperner hypergraphs. These results give new characterizations of threshold and domishold graphs. Second, we apply a characterization of 1‐Sperner hypergraphs to derive decomposition theorems for two classes of split graphs, a class of bipartite graphs, and a class of cobipartite graphs. These decomposition theorems, based on certain matrix partitions, lead to new classes of graphs of bounded clique‐width and new polynomially solvable cases of three basic domination problems: domination, total domination, and connected domination.
PDF
