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.     

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.     

A kind of conditional fault tolerance of alternating group graphs

A vertex subset F is a k-restricted vertex-cut of a connected graph G if G−F is disconnected and every vertex in G−F has at least k good neighbors in G−F. The cardinality of the minimum k-restricted vertex-cut of G is the k-restricted connectivity of G, denoted by κk(G). This parameter measures a kind of conditional fault tolerance of networks. In this paper, we show that for the n-dimensional alternating group graph AGn, κ²(AG₄)=4 and κ²(AGn)=6n−18 for n?5.     

Faster parameterized algorithms for minor containment

The H-Minor containment problem asks whether a graph G contains some fixed graph H as a minor, that is, whether H can be obtained by some subgraph of G after contracting edges. The derivation of a polynomial-time algorithm for H-Minor containment is one of the most important and technical parts of the Graph Minor Theory of Robertson and Seymour and it is a cornerstone for most of the algorithmic applications of this theory. H-Minor containment for graphs of bounded branchwidth is a basic ingredient of this algorithm. The currently fastest solution to this problem, based on the ideas introduced by Robertson and Seymour, was given by Hicks in [I.V. Hicks, Branch decompositions and minor containment, Networks 43 (1) (2004) 1-9], providing an algorithm that in time O(3^k2⋅(h+k−1)!⋅m) decides if a graph G with m edges and branchwidth k, contains a fixed graph H on h vertices as a minor. In this work we improve the dependence on k of Hicks’ result by showing that checking if H is a minor of G can be done in time O(2^{(2k+1)⋅logk}⋅h^2k⋅2^2h2⋅m). We set up an approach based on a combinatorial object called rooted packing, which captures the properties of the subgraphs of H that we seek in our dynamic programming algorithm. This formulation with rooted packings allows us to speed up the algorithm when G is embedded in a fixed surface, obtaining the first algorithm for minor containment testing with single-exponential dependence on branchwidth. Namely, it runs in time 2^O(k)⋅h^2k⋅2^O(h)⋅n, with n=∣V(G)∣. Finally, we show that slight modifications of our algorithm permit to solve some related problems within the same time bounds, like induced minor or contraction containment.     

The super-connected property of recursive circulant graphs

In a graph G, a k-container C_k(u,v) is a set of k disjoint paths joining u and v. A k-container C_k(u,v) is k∗-container if every vertex of G is passed by some path in C_k(u,v). A graph G is k∗-connected if there exists a k∗-container between any two vertices. An m-regular graph G is super-connected if G is k∗-connected for any k with 1?k?m. In this paper, we prove that the recursive circulant graphs G(2^m,4), proposed by Park and Chwa [Theoret. Comput. Sci. 244 (2000) 35-62], are super-connected if and only if m≠2.     

Optimal 1-edge fault-tolerant designs for ladders

A graph G∗ is 1-edge fault-tolerant with respect to a graph G, denoted by 1-EFT(G), if every graph obtained by removing any edge from G∗ contains G. A 1-EFT(G) graph is optimal if it contains the minimum number of edges among all 1-EFT(G) graphs. The kth ladder graph, L_k, is defined to be the cartesian product of the P_k and P₂ where P_n is the n-vertex path graph. In this paper, we present several 1-edge fault-tolerant graphs with respect to ladders. Some of these graphs are proven to be optimal.     

Bandwidth and pebbling

The main results of this paper establish relationships between the bandwidth of a graphG — which is the minimum over all layouts ofG in a line of the maximum distance between images of adjacent vertices ofG — and the ease of playing various pebble games onG. Three pebble games on graphs are considered: the well-known computational pebble game, the “progressive” (i.e., no recomputation allowed) version of the computational pebble game, both of which are played on directed acyclic graphs, and the quite different “breadth-first” pebble game, that is played on undirected graphs. We consider two costs of a play of a pebble game: the minimum number of pebbles needed to play the game on the graphG, and the maximumlifetime of any pebble in the game, i.e., the maximum number of moves that any pebble spends on the graph. The first set of results of the paper prove that the minimum lifetime cost of a play of either of the second two pebble games on a graphG is precisely the bandwidth ofG. The second set of results establish bounds on the pebble demand of all three pebble games in terms of the bandwidth of the graph being pebbled; for instance, the number of pebbles needed to pebble a graphG of bandwidthk is at most min (2k ²+k+1, 2k log₂|G|); and, in addition, there are bandwidth-k graphs that require 3k?1 pebbles. The third set of results relate the difficulty of deciding the cost of playing a pebble game on a given input graphG to the bandwidth ofG; for instance, the Pebble Demand problem forn-vertex graphs of bandwidthf(n) is in the class NSPACE (f(n) log² n); and the Optimal Lifetime Problem for either of the second two pebble games is NP-complete.     

Some results on acyclic edge coloring of plane graphs

An acyclic edge coloring of a graph is a proper edge coloring without bichromatic cycles. The acyclic chromatic index of a graph G, denoted by α^′(G), is the minimum number k such that G admits an acyclic edge coloring using k colors. Let G be a plane graph with maximum degree Δ and girth g. In this paper, we prove that α^′(G)=Δ(G) if one of the following conditions holds: (1) Δ?8 and g?7; (2) Δ?6 and g?8; (3) Δ?5 and g?9; (4) Δ?4 and g?10; (5) Δ?3 and g?14. We also improve slightly a result of A. Fiedorowicz et al. (2008) [7] by showing that every triangle-free plane graph admits an acyclic edge coloring using at most Δ(G)+5 colors.     

On the Grundy and b-Chromatic Numbers of a Graph

The Grundy number of a graph G, denoted by Γ(G), is the largest k such that G has a greedy k-colouring, that is a colouring with k colours obtained by applying the greedy algorithm according to some ordering of the vertexes of G. The b-chromatic number of a graph G, denoted by χ _b (G), is the largest k such that G has a b-colouring with k colours, that is a colouring in which each colour class contains a b-vertex, a vertex with neighbours in all other colour classes. Trivially χ _b (G),Γ(G)≤Δ(G)+1. In this paper, we show that deciding if Γ(G)≤Δ(G) is NP-complete even for a bipartite graph G. We then show that deciding if Γ(G)≥|V(G)|?k or if χ _b (G)≥|V(G)|?k are fixed parameter tractable problems with respect to the parameter k.     

Note on maximal bisection above tight lower bound

In a graph G=(V,E), a bisection (X,Y) is a partition of V into sets X and Y such that |X|?|Y|?|X|+1. The size of (X,Y) is the number of edges between X and Y. In the Max Bisection problem we are given a graph G=(V,E) and are required to find a bisection of maximum size. It is not hard to see that ⌈|E|/2⌉ is a tight lower bound on the maximum size of a bisection of G.We study parameterized complexity of the following parameterized problem called Max Bisection above Tight Lower Bound (Max-Bisec-ATLB): decide whether a graph G=(V,E) has a bisection of size at least ⌈|E|/2⌉+k, where k is the parameter. We show that this parameterized problem has a kernel with O(k²) vertices and O(k³) edges, i.e., every instance of Max-Bisec-ATLB is equivalent to an instance of Max-Bisec-ATLB on a graph with at most O(k²) vertices and O(k³) edges.     

Spanners of bounded degree graphs

A k-spanner of a graph G is a spanning subgraph of G in which the distance between any pair of vertices is at most k times the distance in G. We prove that for fixed k,w, the problem of deciding if a given graph has a k-spanner of treewidth w is fixed-parameter tractable on graphs of bounded degree. In particular, this implies that finding a k-spanner that is a tree (a tree k-spanner) is fixed-parameter tractable on graphs of bounded degree. In contrast, we observe that if the graph has only one vertex of unbounded degree, then Treek-Spanner is NP-complete for k?4.     

Super connectivity of line graphs

The super connectivity κ^′ and the super edge-connectivity λ^′ are more refined network reliability indices than connectivity κ and edge-connectivity λ. This paper shows that for a connected graph G with order at least four rather than a star and its line graph L(G), κ^′(L(G))=λ^′(G) if and only if G is not super-λ^′. As a consequence, we obtain the result of Hellwig et al. [Note on the connectivity of line graphs, Inform. Process. Lett. 91 (2004) 7] that κ(L(G))=λ^′(G). Furthermore, the authors show that the line graph of a super-λ^′ graph is super-λ if the minimum degree is at least three.     

A kind of conditional vertex connectivity of Cayley graphs generated by 2-trees

Let G be a graph. Then T ⊆ V(G) is called an R^k-vertex-cut if G − T is disconnected and each vertex in V(G) − T has at least k neighbors in G − T. The size of a smallest R^k-vertex-cut is the R^k-vertex-connectivity of G and is denoted by κ^k(G). In this paper, we determine the numbers κ¹ and κ² for Cayley graphs generated by 2-trees, including the popular alternating group graphs.     

Geometric Representation of Graphs in Low Dimension Using Axis Parallel Boxes

An axis-parallel k-dimensional box is a Cartesian product R ₁×R ₂×???×R _k where R _i (for 1≤i≤k) is a closed interval of the form [a _i ,b _i ] on the real line. For a graph G, its boxicity box?(G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a $\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1}An axis-parallel k-dimensional box is a Cartesian product R ₁×R ₂×⋅⋅⋅×R _k where R _i (for 1≤i≤k) is a closed interval of the form [a _i ,b _i ] on the real line. For a graph G, its boxicity box (G) is the minimum dimension k, such that G is representable as the intersection graph of (axis-parallel) boxes in k-dimensional space. The concept of boxicity finds applications in various areas such as ecology, operations research etc. A number of NP-hard problems are either polynomial time solvable or have much better approximation ratio on low boxicity graphs. For example, the max-clique problem is polynomial time solvable on bounded boxicity graphs and the maximum independent set problem for boxicity d graphs, given a box representation, has a ?1+\frac1clogn?^d-1\lfloor 1+\frac{1}{c}\log n\rfloor^{d-1} approximation ratio for any constant c≥1 when d≥2. In most cases, the first step usually is computing a low dimensional box representation of the given graph. Deciding whether the boxicity of a graph is at most 2 itself is NP-hard.     

The spanning connectivity of folded hypercubes

A k-container of a graph G is a set of k internally disjoint paths between u and v. A k-container of G is a k∗-container if it contains all vertices of G. A graph G is k∗-connected if there exists a k∗-container between any two distinct vertices, and a bipartite graph G is k∗-laceable if there exists a k∗-container between any two vertices u and v from different partite sets of G for a given k. A k-connected graph (respectively, bipartite graph) G is f-edge fault-tolerant spanning connected (respectively, laceable) if G − F is w∗-connected for any w with 1 ? w ? k − f and for any set F of f faulty edges in G. This paper shows that the folded hypercube FQ_n is f-edge fault-tolerant spanning laceable if n(?3) is odd and f ? n − 1, and f-edge fault-tolerant spanning connected if n (?2) is even and f ? n − 2.     

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.     

Boolean-width of graphs

We introduce the graph parameter boolean-width, related to the number of different unions of neighborhoods-Boolean sums of neighborhoods-across a cut of a graph. For many graph problems, this number is the runtime bottleneck when using a divide-and-conquer approach. For an n-vertex graph given with a decomposition tree of boolean-width k, we solve Maximum Weight Independent Set in time O(n²k2^2k) and Minimum Weight Dominating Set in time O(n²+nk2^3k). With an additional n² factor in the runtime, we can also count all independent sets and dominating sets of each cardinality.Boolean-width is bounded on the same classes of graphs as clique-width. boolean-width is similar to rank-width, which is related to the number of GF(2)-sums of neighborhoods instead of the Boolean sums used for boolean-width. We show for any graph that its boolean-width is at most its clique-width and at most quadratic in its rank-width. We exhibit a class of graphs, the Hsu-grids, having the property that a Hsu-grid on Θ(n²) vertices has boolean-width Θ(logn) and rank-width, clique-width, tree-width, and branch-width Θ(n).     

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.     

Structure and linear time recognition of 3-leaf powers

A graph G is the k-leaf power of a tree T if its vertices are leaves of T such that two vertices are adjacent in G if and only if their distance in T is at most k. Then T is the k-leaf root of G. This notion was introduced and studied by Nishimura, Ragde, and Thilikos motivated by the search for underlying phylogenetic trees. Their results imply a O(n³) time recognition algorithm for 3-leaf powers. Later, Dom, Guo, Hüffner, and Niedermeier characterized 3-leaf powers as the (bull, dart, gem)-free chordal graphs. We show that a connected graph is a 3-leaf power if and only if it results from substituting cliques into the vertices of a tree. This characterization is much simpler than the previous characterizations via critical cliques and forbidden induced subgraphs and also leads to linear time recognition of these graphs.     

On the cubicity of bipartite graphs

A unit cube in k-dimension (or a k-cube) is defined as the Cartesian product R₁×R₂×?×Rk, where each Ri is a closed interval on the real line of the form [ai,ai+1]. The cubicity of G, denoted as cub(G), is the minimum k such that G is the intersection graph of a collection of k-cubes. Many NP-complete graph problems can be solved efficiently or have good approximation ratios in graphs of low cubicity. In most of these cases the first step is to get a low dimensional cube representation of the given graph.It is known that for a graph G, . Recently it has been shown that for a graph G, cub(G)?4(Δ+1)lnn, where n and Δ are the number of vertices and maximum degree of G, respectively. In this paper, we show that for a bipartite graph G=(A∪B,E) with |A|=n₁, |B|=n₂, n₁?n₂, and Δ^′=min{ΔA,ΔB}, where ΔA=maxa∈Ad(a) and ΔB=maxb∈Bd(b), d(a) and d(b) being the degree of a and b in G, respectively, cub(G)?2(Δ^′+2)⌈lnn₂⌉. We also give an efficient randomized algorithm to construct the cube representation of G in 3(Δ^′+2)⌈lnn₂⌉ dimensions. The reader may note that in general Δ^′ can be much smaller than Δ.