On the k-tuple domination of generalized de Brujin and Kautz digraphs

A vertex u in a digraph G = (V, A) is said to dominate itself and vertices v such that (u, v) ∈ A. For a positive integer k, a k-tuple dominating set of G is a subset D of vertices such that every vertex in G is dominated by at least k vertices in D. The k-tuple domination number of G is the minimum cardinality of a k-tuple dominating set of G. This paper deals with the k-tuple domination problem on generalized de Bruijn and Kautz digraphs. We establish bounds on the k-tuple domination number for the generalized de Bruijn and Kautz digraphs and we obtain some conditions for the k-tuple domination number attaining the bounds.     

Signed and minus clique-transversal functions on graphs

A minus (respectively, signed) clique-transversal function of a graph G=(V,E) is a function (respectively, {−1,1}) such that _∑u∈Cf(u)?1 for every maximal clique C of G. The weight of a minus (respectively, signed) clique-transversal function of G is f(V)=_∑v∈Vf(v). The minus (respectively, signed) clique-transversal problem is to find a minus (respectively, signed) clique-transversal function of G of minimum weight. In this paper, we present a unified approach to these two problems on strongly chordal graphs. Notice that trees, block graphs, interval graphs, and directed path graphs are subclasses of strongly chordal graphs. We also prove that the signed clique-transversal problem is NP-complete for chordal graphs and planar graphs.     

On the k-tuple domination of de Bruijn and Kautz digraphs

In a digraph G, a vertex u is said to dominate itself and vertices v such that (u,v) is an arc of G. For a positive integer k, a k-tuple dominating set D of a digraph is a subset of vertices such that every vertex is dominated by at least k vertices in D. The k-tuple domination number of a given digraph is the minimum cardinality of a k-tuple dominating set of the digraph. In this letter, we give the exact values of the k-tuple domination number of de Bruijn and Kautz digraphs.     

Embeddings of Hypercubes and Grids into de Bruijn Graphs

An embedding of a graph G into a graph H is an injective mapping f from the vertices of G into the vertices of H together with a mapping P_f of edges of G into paths in H. The dilation of the embedding is tile maximum taken over all the lengths of the paths P_f(xy) associated with the edges xy of G. We show that it is possible to embed a D-dimensional hypercube into the binary de Bruijn graph of the same order and diameter with dilation at most [D/2]. Similarly a majority of planar grids can be embedded into a binary de Bruijn graph of the same or nearly the same order with dilation at most [D/2] where D is the diameter of the de Bruijn graph.     

Improved Approximation Algorithms for the Spanning Star Forest Problem

A star graph is a tree of diameter at most two. A star forest is a graph that consists of node-disjoint star graphs. In the spanning star forest problem, given an unweighted graph G, the objective is to find a star forest that contains all vertices of G and has the maximum number of edges. This problem is the complement of the dominating set problem in the following sense: On a graph with n vertices, the size of the maximum spanning star forest is equal to n minus the size of the minimum dominating set. We present a 0.71-approximation algorithm for this problem, improving upon the approximation factor of 0.6 of Nguyen et al. (SIAM J. Comput. 38:946–962, 2008). We also present a 0.64-approximation algorithm for the problem on node-weighted graphs. Finally, we present improved hardness of approximation results for the weighted (both edge-weighted and node-weighted) versions of the problem. Our algorithms use a non-linear rounding scheme, which might be of independent interest.     

Restricted arc-connectivity of digraphs

Since interconnection networks are often modeled by graphs or digraphs, the edge-connectivity of a graph or arc-connectivity of a digraph are important measurements for fault tolerance of networks.The restricted edge-connectivity λ^′(G) of a graph G is the minimum cardinality over all edge-cuts S in a graph G such that there are no isolated vertices in G−S. A connected graph G is called λ^′-connected, if λ^′(G) exists.In 1988, Esfahanian and Hakimi [A.H. Esfahanian, S.L. Hakimi, On computing a conditional edge-connectivity of a graph, Inform. Process. Lett. 27 (1988), 195-199] have shown that each connected graph G of order n?4, except a star, is λ^′-connected and satisfies λ^′(G)?ξ(G), where ξ(G) is the minimum edge-degree of G.If D is a strongly connected digraph, then we call in this paper an arc set S a restricted arc-cut of D if D−S has a non-trivial strong component D₁ such that D−V(D₁) contains an arc. The restricted arc-connectivity λ^′(D) is the minimum cardinality over all restricted arc-cuts S.We observe that the recognition problem, whether λ^′(D) exists for a strongly connected digraph D is solvable in polynomial time. Furthermore, we present some analogous results to the above mentioned theorem of Esfahanian and Hakimi for digraphs, and we show that this theorem follows easily from one of our results.     

Clique-perfectness and balancedness of some graph classes

A graph is clique-perfect if the maximum size of a clique-independent set (a set of pairwise disjoint maximal cliques) and the minimum size of a clique-transversal set (a set of vertices meeting every maximal clique) coincide for each induced subgraph. A graph is balanced if its clique-matrix contains no square submatrix of odd size with exactly two ones per row and column. In this work, we give linear-time recognition algorithms and minimal forbidden induced subgraph characterizations of clique-perfectness and balancedness of P₄-tidy graphs and a linear-time algorithm for computing a maximum clique-independent set and a minimum clique-transversal set for any P₄-tidy graph. We also give a minimal forbidden induced subgraph characterization and a linear-time recognition algorithm for balancedness of paw-free graphs. Finally, we show that clique-perfectness of diamond-free graphs can be decided in polynomial time by showing that a diamond-free graph is clique-perfect if and only if it is balanced.     

Bounds for the 2-domination number of toroidal grid graphs

A k-dominating set for a graph G(V, E) is a set of vertices D? V such that every vertex v∈V\ D is adjacent to at least k vertices in D. The k-domination number of G, denoted by γ _k (G), is the cardinality of a smallest k-dominating set of G. Here we establish lower and upper bounds of γ _k (C _m ×C _n ) for k=2. In some cases, these bounds agree so that the exact 2-domination number is obtained.     

Conditional connectivity of Cayley graphs generated by transposition trees

Given a graph G and a non-negative integer h, the Rh-(edge)connectivity of G is the minimum cardinality of a set of (edges)vertices of G, if any, whose deletion disconnects G, and every remaining component has minimum degree at least h. Similarly, given a non-negative integer g, the g-(edge)extraconnectivity of G is the minimum cardinality of a set of (edges)vertices of G, if any, whose deletion disconnects G, and every remaining component has more than g vertices. In this paper, we determine R₂-(edge)connectivity and 2-extra(edge)connectivity of Cayley graphs generated by transposition trees.     

The hub number of a graph

A hub set in a graph G is a set U⊆V(G) such that any two vertices outside U are connected by a path whose internal vertices lie in U. We prove that h(G)?hc(G)?γc(G)?h(G)+1, where h(G), hc(G), and γc(G), respectively, are the minimum sizes of a hub set in G, a hub set inducing a connected subgraph, and a connected dominating set. Furthermore, all graphs with γc(G)>hc(G)?4 are obtained by substituting graphs into three consecutive vertices of a cycle; this yields a polynomial-time algorithm to check whether hc(G)=γc(G).     

Parameterized complexity of connected even/odd subgraph problems

In 2011, Cai an Yang initiated the systematic parameterized complexity study of the following set of problems around Eulerian graphs: for a given graph G and integer k, the task is to decide if G contains a (connected) subgraph with k vertices (edges) with all vertices of even (odd) degrees. They succeed to establish the parameterized complexity of all cases except two, when we ask about:

•

a connected k-edge subgraph with all vertices of odd degrees, the problem known as k-Edge Connected Odd Subgraph; and     

Obtaining Online Ecological Colourings by Generalizing First-Fit

A colouring of a graph is ecological if every pair of vertices that have the same set of colours in their neighbourhood are coloured alike. We consider the following problem: if a graph G and an ecological colouring c of G are given, can further vertices added to G, one at a time, be coloured so that at each stage the current graph is ecologically coloured? If the answer is yes, then we say that the pair (G,c) is ecologically online extendible. By generalizing the well-known First-Fit algorithm, we are able to characterize when (G,c) is ecologically online extendible, and to show that deciding whether (G,c) is ecologically extendible can be done in polynomial time. We also describe when the extension is possible using only colours from a given finite set C. For the case where c is a colouring of G in which each vertex is coloured distinctly, we give a simple characterization of when (G,c) is ecologically online extendible using only the colours of c, and we also show that (G,c) is always online extendible using the colours of c plus one extra colour. We also study (off-line) ecological H-colourings (an H-colouring of G is a homomorphism from G to H). We study the problem of deciding whether G has an ecological H-colouring for some fixed H and give a characterization of its computational complexity in terms of the structure of H.     

On the cubicity of certain graphs

The boxicity of a graph G is the minimum dimension b such that G is representable as the intersection graph of axis-parallel boxes in the b-dimensional space. When the boxes are restricted to be axis-parallel b-dimensional cubes, the minimum dimension b required to represent G is called the cubicity of G. In this paper we show that cubicity(Hd)?2d, where Hd is the d-dimensional hypercube. (The d-dimensional hypercube is the graph on d² vertices which corresponds to the d²d-vectors whose components are either 0 or 1, two of the vertices being adjacent when they differ in just one coordinate.) We also show that cubicity(Hd)?(d−1)/(logd). We also show that (1) cubicity(G)?(logα)/(log(D+1)), (2) cubicity(G)?(logn−logω)/(logD), where α,ω,D and n denote the stability number, the clique number, the diameter and the number of vertices of G. As consequences of these lower bounds we provide lower bounds for the cubicity of planar graphs, bipartite graphs, triangle-free graphs, etc., in terms of their diameter and the number of vertices.     

Fault-diameter of Cartesian graph bundles

Cartesian graph bundles is a class of graphs that is a generalization of the Cartesian graph products. Let G be a kG-connected graph and Dc(G) denote the diameter of G after deleting any of its c<kG vertices. We prove that Da+b+1(G)?Da(F)+Db(B)+1 if G is a graph bundle with fibre F over base B, a<kF, and b<kB.     

On the complexity of some colorful problems parameterized by treewidth

In this paper, we study the complexity of several coloring problems on graphs, parameterized by the treewidth of the graph.

1.

The List Coloring problem takes as input a graph G, together with an assignment to each vertex v of a set of colors C_v. The problem is to determine whether it is possible to choose a color for vertex v from the set of permitted colors C_v, for each vertex, so that the obtained coloring of G is proper. We show that this problem is W[1]-hard, parameterized by the treewidth of G. The closely related Precoloring Extension problem is also shown to be W[1]-hard, parameterized by treewidth.

2.

An equitable coloring of a graph G is a proper coloring of the vertices where the numbers of vertices having any two distinct colors differs by at most one. We show that the problem is hard for W[1], parameterized by the treewidth plus the number of colors. We also show that a list-based variation, List Equitable Coloring is W[1]-hard for forests, parameterized by the number of colors on the lists.

3.

The list chromatic numberχ_l(G) of a graph G is defined to be the smallest positive integer r, such that for every assignment to the vertices v of G, of a list L_v of colors, where each list has length at least r, there is a choice of one color from each vertex list L_v yielding a proper coloring of G. We show that the problem of determining whether χ_l(G)?r, the List Chromatic Number problem, is solvable in linear time on graphs of constant treewidth.

     

On an infinite family of graphs with information ratio 2 − 1/k

In this paper we consider the secret sharing problem on special access structures with minimal qualified subsets of size two, i.e. secret sharing on graphs. This means that the participants are the vertices of the graph and the qualified subsets are the subsets of V(G) spanning at least one edge. The information ratio of a graph G is denoted by R(G) and is defined as the ratio of the greatest size of the shares a vertex has to remember and of the size of the secret. Since the determination of the exact information ratio is a non-trivial problem even for small graphs (i.e. for V(G) = 6), every construction can be of particular interest. Let k be the maximal degree in G. In this paper we prove that R(G) = 2 ? 1/k for every graph G with the following properties: (A) every vertex has at most one neighbour of degree one; (B) vertices of degree at least 3 are not connected by an edge; (C) the girth of the graph is at least 6. We prove this by using polyhedral combinatorics arguments and the entropy method.     

Pruning 2-Connected Graphs

Given an undirected graph G with edge costs and a specified set of terminals, let the density of any subgraph be the ratio of its cost to the number of terminals it contains. If G is 2-connected, does it contain smaller 2-connected subgraphs of density comparable to that of?G? We answer this question in the affirmative by giving an algorithm to pruneG and find such subgraphs of any desired size, incurring only a logarithmic factor increase in density (plus a small additive term). We apply our pruning techniques to give algorithms for two NP-Hard problems on finding large 2-vertex-connected subgraphs of low cost; no previous approximation algorithm was known for either problem. In the k-2VC problem, we are given an undirected graph G with edge costs and an integer k; the goal is to find a minimum-cost 2-vertex-connected subgraph of G containing at least k vertices. In the Budget-2VC problem, we are given a graph G with edge costs, and a budget B; the goal is to find a 2-vertex-connected subgraph H of G with total edge cost at most B that maximizes the number of vertices in H. We describe an O(log?nlog?k) approximation for the k-2VC problem, and a bicriteria approximation for the Budget-2VC problem that gives an $O(\frac{1}{\epsilon}\log^{2} n)$ approximation, while violating the budget by a factor of at most 2+ε.     

Enumerating Minimal Subset Feedback Vertex Sets

The Subset Feedback Vertex Set problem takes as input a pair (G,S), where G=(V,E) is a graph with weights on its vertices, and S?V. The task is to find a set of vertices of total minimum weight to be removed from G, such that in the remaining graph no cycle contains a vertex of S. We show that this problem can be solved in time O(1.8638 ⁿ ), where n=|V|. This is a consequence of the main result of this paper, namely that all minimal subset feedback vertex sets of a graph can be enumerated in time O(1.8638 ⁿ ).     

Finding a dominating set on bipartite graphs

Finding a dominating set of minimum cardinality is an NP-hard graph problem, even when the graph is bipartite. In this paper we are interested in solving the problem on graphs having a large independent set. Given a graph G with an independent set of size z, we show that the problem can be solved in time O^∗(²n−z), where n is the number of vertices of G. As a consequence, our algorithm is able to solve the dominating set problem on bipartite graphs in time O^∗(²n/2). Another implication is an algorithm for general graphs whose running time is O(n^1.7088).