Partitioning a graph into convex sets

Let G be a finite simple graph. Let S⊆V(G), its closed interval I[S] is the set of all vertices lying on shortest paths between any pair of vertices of S. The set S is convex if I[S]=S. In this work we define the concept of a convex partition of graphs. If there exists a partition of V(G) into p convex sets we say that G is p-convex. We prove that it is NP-complete to decide whether a graph G is p-convex for a fixed integer p≥2. We show that every connected chordal graph is p-convex, for 1≤p≤n. We also establish conditions on n and k to decide if the k-th power of a cycle C_n is p-convex. Finally, we develop a linear-time algorithm to decide if a cograph is p-convex.     

On 3-Steiner simplicial orderings

Let G be a connected graph and S a nonempty set of vertices of G. A Steiner tree for S is a connected subgraph of G containing S that has a minimum number of edges. The Steiner interval for S is the collection of all vertices in G that belong to some Steiner tree for S. Let k≥2 be an integer. A set X of vertices of G is k-Steiner convex if it contains the Steiner interval of every set of k vertices in X. A vertex x∈X is an extreme vertex of X if X?{x} is also k-Steiner convex. We call such vertices k-Steiner simplicial vertices. We characterize vertices that are 3-Steiner simplicial and give characterizations of two classes of graphs, namely the class of graphs for which every ordering produced by Lexicographic Breadth First Search is a 3-Steiner simplicial ordering and the class for which every ordering of every induced subgraph produced by Maximum Cardinality Search is a 3-Steiner simplicial ordering.     

Coloring, location and domination of corona graphs

A vertex coloring of a graph G is an assignment of colors to the vertices of G so that every two adjacent vertices of G have different colors. A coloring related property of a graphs is also an assignment of colors or labels to the vertices of a graph, in which the process of labeling is done according to an extra condition. A set S of vertices of a graph G is a dominating set in G if every vertex outside of S is adjacent to at least one vertex belonging to S. A domination parameter of G is related to those structures of a graph that satisfy some domination property together with other conditions on the vertices of G. In this article we study several mathematical properties related to coloring, domination and location of corona graphs. We investigate the distance-k colorings of corona graphs. Particularly, we obtain tight bounds for the distance-2 chromatic number and distance-3 chromatic number of corona graphs, through some relationships between the distance-k chromatic number of corona graphs and the distance-k chromatic number of its factors. Moreover, we give the exact value of the distance-k chromatic number of the corona of a path and an arbitrary graph. On the other hand, we obtain bounds for the Roman dominating number and the locating–domination number of corona graphs. We give closed formulaes for the k-domination number, the distance-k domination number, the independence domination number, the domatic number and the idomatic number of corona graphs.     

On the Convexity Number of Graphs

A set of vertices S in a graph is convex if it contains all vertices which belong to shortest paths between vertices in S. The convexity number c(G) of a graph G is the maximum cardinality of a convex set of vertices which does not contain all vertices of G. We prove NP-completeness of the problem to decide for a given bipartite graph G and an integer k whether c(G) ≥ k. Furthermore, we identify natural necessary extension properties of graphs of small convexity number and study the interplay between these properties and upper bounds on the convexity number.     

Convexity in oriented graphs

For vertices u and v in an oriented graph D, the closed interval I[u,v] consists of u and v together with all vertices lying in a u−v geodesic or v−u geodesic in D. For S⊆V(D), I[S] is the union of all closed intervals I[u,v] with u,v∈S. A set S is convex if I[S]=S. The convexity number con(D) is the maximum cardinality of a proper convex set of V(D). The nontrivial connected oriented graphs of order n with convexity number n−1 are characterized. It is shown that there is no connected oriented graph of order at least 4 with convexity number 2 and that every pair k, n of integers with 1⩽k⩽n−1 and k≠2 is realizable as the convexity number and order, respectively, of some connected oriented graph. For a nontrivial connected graph G, the lower orientable convexity number con⁻(G) is the minimum convexity number among all orientations of G and the upper orientable convexity number con⁺(G) is the maximum such convexity number. It is shown that con⁺(G)=n−1 for every graph G of order n⩾2. The lower orientable convexity numbers of some well-known graphs are determined, with special attention given to outerplanar graphs.     

Characterizations of 2-variegated graphs and of 3-variegated graphs

A graph is said to be k-variegated if its vertex set can be partitioned into k equal parts such that each vertex is adjacent to exactly one vertex from every other part not containing it. We prove that a graph G on 2n vertices is 2-variegated if and only if there exists a set S of n independent edges in G such that no cycle in G contains an odd number of edges from S. We also characterize 3-variegated graphs.     

3-Factor-criticality in domination critical graphs

A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k-1 vertices. The structure of k-γ-critical graphs remains far from completely understood when k?3.A graph G is factor-critical if G-v has a perfect matching for every vertex v∈V(G) and is bicritical if G-u-v has a perfect matching for every pair of distinct vertices u,v∈V(G). More generally, a graph is said to be k-factor-critical if G-S has a perfect matching for every set S of k vertices in G. In three previous papers [N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs, Discrete Math. 272 (2003) 5-15; N. Ananchuen, M.D. Plummer, Matching properties in domination critical graphs, Discrete Math. 277 (2004) 1-13; N. Ananchuen, M.D. Plummer, Some results related to the toughness of 3-domination-critical graphs. II. Utilitas Math. 70 (2006) 11-32], we explored the toughness of 3-γ-critical graphs and some of their matching properties. In particular, we obtained some properties which are sufficient for a 3-γ-critical graph to be factor-critical and, respectively, bicritical. In the present work, we obtain similar results for k-factor-critical graphs when k=3.     

Graphs with a Minimal Number of Convex Sets

Let G be a graph with vertex set V(G). A set C of vertices of G is g-convex if for every pair \({u, v \in C}\) the vertices on every u–v geodesic (i.e. shortest u–v path) belong to C. If the only g-convex sets of G are the empty set, V(G), all singletons and all edges, then G is called a g-minimal graph. It is shown that a graph is g-minimal if and only if it is triangle-free and if it has the property that the convex hull of every pair of non-adjacent vertices is V(G). Several properties of g-minimal graphs are established and it is shown that every triangle-free graph is an induced subgraph of a g-minimal graph. Recursive constructions of g-minimal graphs are described and bounds for the number of edges in these graphs are given. It is shown that the roots of the generating polynomials of the number of g-convex sets of each size of a g-minimal graphs are bounded, in contrast to their behaviour over all graphs. A set C of vertices of a graph is m-convex if for every pair \({u, v \in C}\) , the vertices of every induced u–v path belong to C. A graph is m-minimal if it has no m-convex sets other than the empty set, the singletons, the edges and the entire vertex set. Sharp bounds on the number of edges in these graphs are given and graphs that are m-minimal are shown to be precisely the 2-connected, triangle-free graphs for which no pair of adjacent vertices forms a vertex cut-set.     

Some results related to the toughness of 3-domination critical graphs

A graph G is said to be k-γ-critical if the size of any minimum dominating set of vertices is k, but if any edge is added to G the resulting graph can be dominated with k−1 vertices. The structure of k-γ-critical graphs remains far from completely understood, even in the special case when the domination number γ=3. In a 1983 paper, Sumner and Blitch proved a theorem which may regarded as a result related to the toughness of 3-γ-critical graphs which says that if S is any vertex cutset of such a graph, then G−S has at most |S|+1 components. In the present paper, we improve and extend this result considerably.     

2-Coherent and 2-convex conditional lower previsions

In this paper we explore relaxations of (Williams) coherent and convex conditional previsions that form the families of n-coherent and n-convex conditional previsions, at the varying of n. We investigate which such previsions are the most general one may reasonably consider, suggesting (centered) 2-convex or, if positive homogeneity and conjugacy is needed, 2-coherent lower previsions. Basic properties of these previsions are studied. In particular, we prove that they satisfy the Generalised Bayes Rule and always have a 2-convex or, respectively, 2-coherent natural extension. The role of these extensions is analogous to that of the natural extension for coherent lower previsions. On the contrary, n-convex and n-coherent previsions with $n\ge 3$ either are convex or coherent themselves or have no extension of the same type on large enough sets. Among the uncertainty concepts that can be modelled by 2-convexity, we discuss generalisations of capacities and niveloids to a conditional framework and show that the well-known risk measure Value-at-Risk only guarantees to be centered 2-convex. In the final part, we determine the rationality requirements of 2-convexity and 2-coherence from a desirability perspective, emphasising how they weaken those of (Williams) coherence.     

Total domination dot-stable graphs

A set S of vertices in a graph G is a total dominating set if every vertex of G is adjacent to some vertex in S. The minimum cardinality of a total dominating set of G is the total domination number of G. Two vertices of G are said to be dotted (identified) if they are combined to form one vertex whose open neighborhood is the union of their neighborhoods minus themselves. We note that dotting any pair of vertices cannot increase the total domination number. Further we show it can decrease the total domination number by at most 2. A graph is total domination dot-stable if dotting any pair of adjacent vertices leaves the total domination number unchanged. We characterize the total domination dot-stable graphs and give a sharp upper bound on their total domination number. We also characterize the graphs attaining this bound.     

Edge-dominating cycles in graphs

A set S of vertices in a graph G is said to be an edge-dominating set if every edge in G is incident with a vertex in S. A cycle in G is said to be a dominating cycle if its vertex set is an edge-dominating set. Nash-Williams [Edge-disjoint hamiltonian circuits in graphs with vertices of large valency, Studies in Pure Mathematics, Academic Press, London, 1971, pp. 157-183] has proved that every longest cycle in a 2-connected graph of order n and minimum degree at least is a dominating cycle. In this paper, we prove that for a prescribed positive integer k, under the same minimum degree condition, if n is sufficiently large and if we take k disjoint cycles so that they contain as many vertices as possible, then these cycles form an edge-dominating set. Nash-Williams’ Theorem corresponds to the case of k=1 of this result.     

Some Defective Parameters in Graphs

Given a graph G and an integer k, a set S of vertices in G is k-sparse if S induces a graph with a maximum degree of at most k. Many parameters in graph theory are defined in terms of independent sets. Accordingly, their definitions can be expanded taking into account the notion of k-sparse sets. In this discussion, we examine several of those extensions. Similarly, S is k-dense if S induces a k-sparse graph in the complement of G. A partition of V(G) is a k-defective cocoloring if each part is k-sparse or k-dense. The minimum order of all k-defective cocolorings is the k-defective cochromatic number of G and denoted z _k (G). Analogous notions are defined similarly for k-defective coloring where V(G) is partitioned into k-sparse parts. We show the NP-hardness of computing maximum k-defective sets in planar graphs with maximum degree at most k + 1 and arbitrarily large girth. We explore the extension of Ramsey numbers to k-sparse and k-dense sets of vertices. Lastly, we discuss some bounds related to k-defective colorings and k-defective cocolorings.     

Some remarks on the geodetic number of a graph

A set of vertices D of a graph G is geodetic if every vertex of G lies on a shortest path between two not necessarily distinct vertices in D. The geodetic number of G is the minimum cardinality of a geodetic set of G.We prove that it is NP-complete to decide for a given chordal or chordal bipartite graph G and a given integer k whether G has a geodetic set of cardinality at most k. Furthermore, we prove an upper bound on the geodetic number of graphs without short cycles and study the geodetic number of cographs, split graphs, and unit interval graphs.     

Partial Convexity

We study OC-convexity, which is defined by the intersection of conic semispaces of partial convexity. We investigate an optimization problem for OC-convex sets and prove a Krein--Milman type theorem for OC-convexity. The relationship between OC-convex and functionally convex sets is studied. Topological and numerical aspects, as well as separability properties are described. An upper estimate for the Carathéodory number for OC-convexity is found. On the other hand, it happens that the Helly and the Radon number for OC-convexity are infinite. We prove that the OC-convex hull of any finite set of points is the union of finitely many polyhedra.     

Polyhedral studies on the convex recoloring problem

A coloring of the vertices of a graph G is convex if, for each assigned color d, the vertices with color d induce a connected subgraph of G. We address the convex recoloring problem, defined as follows. Given a graph G and a coloring of its vertices, recolor a minimum number of vertices of G, so that the resulting coloring is convex. This problem is known to be NP-hard even when G is a path. We show an integer programming formulation for the weighted version of this problem on arbitrary graphs, and then specialize it for trees. We study the facial structure of the polytope defined as the convex hull of the integer points satisfying the restrictions of the proposed ILP formulation, present several classes of facet-defining inequalities and discuss separation algorithms.     

Domination Defect in Graphs: Guarding With Fewer Guards

In this paper, we introduce a new graph parameter called the domination defect of a graph. The domination number γ of a graph G is the minimum number of vertices required to dominate the vertices of G. Due to the minimality of γ, if a set of vertices of G has cardinality less than γ then there are vertices of G that are not dominated by that set. The k-domination defect of G is the minimum number of vertices which are left un-dominated by a subset of γ - k vertices of G. We study different bounds on the k-domination defect of a graph G with respect to the domination number, order, degree sequence, graph homomorphisms and the existence of efficient dominating sets. We also characterize the graphs whose domination defect is 1 and find exact values of the domination defect for some particular classes of graphs.     

On realizations of point determining graphs, and obstructions to full homomorphisms

A graph is point determining if distinct vertices have distinct neighbourhoods. A realization of a point determining graph H is a point determining graph G such that each vertex-removed subgraph G-x which is point determining, is isomorphic to H. We study the fine structure of point determining graphs, and conclude that every point determining graph has at most two realizations.A full homomorphism of a graph G to a graph H is a vertex mapping f such that for distinct vertices u and v of G, we have uv an edge of G if and only if f(u)f(v) is an edge of H. For a fixed graph H, a full H-colouring of G is a full homomorphism of G to H. A minimal H-obstruction is a graph G which does not admit a full H-colouring, such that each proper induced subgraph of G admits a full H-colouring. We analyse minimal H-obstructions using our results on point determining graphs. We connect the two problems by proving that if H has k vertices, then a graph with k+1 vertices is a minimal H-obstruction if and only if it is a realization of H. We conclude that every minimal H-obstruction has at most k+1 vertices, and there are at most two minimal H-obstructions with k+1 vertices.We also consider full homomorphisms to graphs H in which loops are allowed. If H has ? loops and k vertices without loops, then every minimal H-obstruction has at most (k+1)(?+1) vertices, and, when both k and ? are positive, there is at most one minimal H-obstruction with (k+1)(?+1) vertices.In particular, this yields a finite forbidden subgraph characterization of full H-colourability, for any graph H with loops allowed.     

Netlike partial cubes I. General properties

A set A of vertices of a graph G is C-convex if the vertex set of any cycle of the subgraph of G induced by the union of the intervals between each pair of elements of A is contained in A. A partial cube (isometric subgraph of a hypercube) is a netlike partial cube if, for each edge ab, the sets U_ab and U_ba are C-convex (U_ab being the set of all vertices closer to a than to b and adjacent to some vertices closer to b than to a, and vice versa for U_ba). Particular netlike partial cubes are median graphs, even cycles, benzenoid graphs and cellular bipartite graphs. In this paper we give different characterizations and properties of netlike partial cubes. In particular, as median graphs and cellular bipartite graphs, these graphs have a pre-hull number which is at most one, and moreover the convex hull of any isometric cycle of a netlike partial cube is, as in the case of bipartite cellular graphs, this cycle itself or, as in the case of median graphs, a hypercube. We also characterize the gated subgraphs of a netlike partial cube, and we show that the gated amalgam of two netlike partial cubes is a netlike partial cube.